Concepedia

An Eulerian path approach to DNA fragment assembly

Pavel A. Pevzner, Haixu Tang, Michael S. Waterman

Proceedings of the National Academy of Sciences · 2001 · 1.4K citations · 24 references

Open access

Concepts

Life SciencesBiologyGenome AssemblyGenomic Data AnalysisGenomicsContig ConstructionDna AssemblyDna SequencingOverlap-layout-consensus AssemblyRepeat ResolutionSequencingAssembly Of RepeatsConsensus AssemblyDna Fragment AssemblyEulerian Path AlgorithmsEulerian PathsFragment AssemblyGenomic RepeatsShotgun Sequencing

TL;DR

Fragment assembly has traditionally relied on the overlap–layout–consensus paradigm, which works for clone assembly but struggles with genomic shotgun data. The study introduces a new Eulerian algorithm to overcome the long‑standing repeat problem in DNA fragment assembly. The method employs an Eulerian path algorithm that exploits repeats instead of masking them, enabling accurate assembly. This approach reduces fragment assembly to a variant of the Eulerian path problem, yielding accurate solutions for large‑scale sequencing.

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.