An Eulerian Path Approach to DNA Fragment Assembly

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 c...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the National Academy of Sciences - PNAS 2001-08, Vol.98 (17), p.9748-9753
Main Authors: Pevzner, Pavel A., Tang, Haixu, Waterman, Michael S.
Format: Article
Language:English
Subjects:
Algorithms
Biological Sciences
Biology
Campylobacter jejuni - genetics
Contig Mapping - methods
Deoxyribonucleic acid
DNA
DNA, Bacterial - genetics
fragment assembly
Genetics
Genome, Bacterial
Genomes
Genomics
Informational error correction
Lactococcus lactis - genetics
Models, Theoretical
Neisseria meningitidis - genetics
Nucleotide sequences
Nucleotides
Peat
Physical Sciences
Sequence Alignment - methods
Sequence Analysis, DNA - methods
Sequencing
Software
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0027-8424
1091-6490
DOI:10.1073/pnas.171285098