UC Riverside

When sequencing a new genome, it is common practice to expect that 30-50× sequencing depth will be sufficient for a complete and highly contiguous assembly. 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. The optimal read selection problem for genome assembly is largely unexplored. Here 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.