title: Multiple sequence assembly from reads alignable to a common reference genome.
abstract: We describe a set of computational problems motivated by certain analysis tasks in genome resequencing. These are assembly problems for which multiple distinct sequences must be assembled, but where the relative positions of reads to be assembled are already known. This information is obtained from a common reference genome and is characteristic of resequencing experiments. The simplest variant of the problem aims at determining a minimum set of superstrings such that each sequenced read matches at least one superstring. We give an algorithm with time complexity O(N), where N is the sum of the lengths of reads, substantially improving on previous algorithms for solving the same problem. We also examine the problem of finding the smallest number of reads to remove such that the remaining reads are consistent with k superstrings. By exploiting a surprising relationship with the minimum cost flow problem, we show that this problem can be solved in polynomial time when nested reads are excluded. If nested reads are permitted, this problem of removing the minimum number of reads becomes NP-hard. We show that permitting mismatches between reads and their nearest superstrings generally renders these problems NP-hard.
authors.affiliation: Department of Computer Science & Engineering, University of California, San Diego, 9500 Gilman Drive, Mail Code 0404, La Jolla, CA 92093-0114, USA. qpeng@cs.ucsd.edu
authors.forename: Qian
authors.initials: Q
authors.lastname: Peng
authors.forename: Andrew D
authors.initials: AD
authors.lastname: Smith
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D023281:Genomics / Q000379:methods*; D006239:Haplotypes; D008957:Models, Genetic; D008969:Molecular Sequence Data; D011003:Ploidies; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*