title: An Eulerian path approach to DNA fragment assembly.
abstract: For the last 20 years, fragment assembly in DNA sequencing followed the "overlap-layout-consensus" paradigm that is used in all currently available assembly tools. Although this approach proved useful in assembling clones, it faces difficulties in genomic shotgun assembly. We abandon the classical "overlap-layout-consensus" approach in favor of a new euler algorithm that, for the first time, resolves the 20-year-old "repeat problem" in fragment assembly. Our main result is the reduction of the fragment assembly to a variation of the classical Eulerian path problem that allows one to generate accurate solutions of large-scale sequencing problems. euler, in contrast to the celera assembler, does not mask such repeats but uses them instead as a powerful fragment assembly tool.
authors.affiliation: Department of Computer Science and Engineering, University of California, San Diego, La Jolla, USA.
authors.forename: P A
authors.initials: PA
authors.lastname: Pevzner
authors.forename: H
authors.initials: H
authors.lastname: Tang
authors.forename: M S
authors.initials: MS
authors.lastname: Waterman
mesh_terms: D000465:Algorithms; D016123:Campylobacter jejuni / Q000235:genetics; D020451:Contig Mapping / Q000379:methods*; D004269:DNA, Bacterial / Q000235:genetics; D016680:Genome, Bacterial; D013294:Lactococcus lactis / Q000235:genetics; D008962:Models, Theoretical; D009345:Neisseria meningitidis / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
chemical_list: D004269:DNA, Bacterial