Research Projects

AWinK (Adaptive Window-based read selection using UniKmers)

With the rapid decrease in the cost of sequencing DNA, on small genomes it is not uncommon to have excessive sequencing data, sometimes exceeding 1000× sequencing depth (which we call ultra-deep). Because ultra-deep sequencing data significantly degrades the quality of the final assembly (for reasons not entirely clear to us), one faces the problem of how to select a subsample of the data for optimal assembly which is largely unexplored.

In this work, we first show that this problem is related to the minimum tiling path (MTP) problem which is known to be NP-hard. Then, we propose a heuristic (called AWinK) based on single-copy k-mer to select a subset of ultra-deep sequencing reads that maximizes the genomic coverage. Our experiments on both synthetic and real ultra-deep sequencing data demonstrate that AWinK can approximate the minimum tiling path in obtaining highly contiguous, accurate, and complete genome assembly. Compared to other six read selection strategies, subsets of reads chosen with AWinK produced assemblies that had the highest genome fraction and sequence identity.

GitHub: https://github.com/sakshar/AWinK