An Eulerian path approach to DNA fragment assembly
Open accessThe DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“This is in part due to the drawback to the de Bruijn graph approach [61], which is the algorithm used by SOAPdenovo.”
From De novo assembly and characterization of root transcriptome using Illumina paired-end sequencing and development of cSSR markers in sweetpotato (Ipomoea batatas) (2010) · cites this paper as [61]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“In de Bruijn approach, the reads are decomposed into k-mers, which maybe cause the loss of information.”
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Initial sequencing and analysis of the human genome
International Human Genome Sequencing Consortium, Whitehead Institute for Biomedical Research, C. F. G. R., Lander, E. S., Linton, L. M., Birren, B., Nusbaum, C., Zody, M. C., Baldwin, J., Devon, K., Dewar, K., et al. (2001) · Nature · doi:10.1038/35057062 · Cited by 24,216
The sequence of the human genome
Venter, J. C., Adams, M. D., Myers, E. W., Li, P. W., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., et al. (2001) · Science · doi:10.1126/science.1058040 · Cited by 13,909
Whole-Genome Random Sequencing and Assembly of Haemophilus influenzae Rd
Fleischmann, R. D., Adams, M. D., White, O., Clayton, R. A., Kirkness, E. F., Kerlavage, A. R., Bult, C. J., Tomb, J.-F., Dougherty, B. A., Merrick, J. M., et al. (1995) · Science · doi:10.1126/science.7542800 · Cited by 5,654
CAP3: A DNA Sequence Assembly Program
Huang, X., & Madan, A. (1999) · Genome Research · doi:10.1101/gr.9.9.868 · Cited by 5,261
Consed: A Graphical Tool for Sequence Finishing
Gordon, D., Abajian, C., & Green, P. (1998) · Genome Research · doi:10.1101/gr.8.3.195 · Cited by 3,302
The genome sequence of the food-borne pathogen Campylobacter jejuni reveals hypervariable sequences
Parkhill, J., Wren, B. W., Mungall, K., Ketley, J. M., Churcher, C., Basham, D., Chillingworth, T., Davies, R. M., Feltwell, T., Holroyd, S., et al. (2000) · Nature · doi:10.1038/35001088 · Cited by 1,976
The Sequence of the Human Genome
Venter, J. C., Smith, H. O., & Adams, M. D. (2015) · Clinical Chemistry · doi:10.1373/clinchem.2014.237016 · Cited by 1,648
A Whole-Genome Assembly of Drosophila
Myers, E. W., Sutton, G. G., Delcher, A. L., Dew, I. M., Fasulo, D. P., Flanigan, M. J., Kravitz, S. A., Mobarry, C. M., Reinert, K. H. J., Remington, K. A., et al. (2000) · Science · doi:10.1126/science.287.5461.2196 · Cited by 1,538
A new DNA sequence assembly program
Bonfield, J. K., Smith, K. F., & Staden, R. (1995) · Nucleic Acids Research · doi:10.1093/nar/23.24.4992 · Cited by 973
Complete DNA sequence of a serogroup A strain of Neisseria meningitidis Z2491
Parkhill, J., Achtman, M., James, K. D., Bentley, S. D., Churcher, C., Klee, S. R., Morelli, G., Basham, D., Brown, D., Chillingworth, T., et al. (2000) · Nature · doi:10.1038/35006655 · Cited by 704
Computational Molecular Biology: An Algorithmic Approach
Pevzner, P. A. (2000) · The MIT Press eBooks · doi:10.7551/mitpress/2022.001.0001 · Cited by 605
Self-citationTIGR Assembler: A New Tool for Assembling Large Shotgun Sequencing Projects
SUTTON, G. G., WHITE, O., ADAMS, M. D., & KERLAVAGE, A. R. (1995) · Genome Science and Technology · doi:10.1089/gst.1995.1.9 · Cited by 411
Sequencing of megabase plus DNA by hybridization: Theory of the method
Dramanac, R., Labat, I., Brukner, I., & Crkvenjakov, R. (1989) · Genomics · doi:10.1016/0888-7543(89)90290-5 · Cited by 354
A New Algorithm for DNA Sequence Assembly
IDURY, R. M., & WATERMAN, M. S. (1995) · Journal of Computational Biology · doi:10.1089/cmb.1995.2.291 · Cited by 342
Self-citationHuman Whole-Genome Shotgun Sequencing
Weber, J. L., & Myers, E. W. (1997) · Genome Research · doi:10.1101/gr.7.5.401 · Cited by 311
l-Tuple DNA Sequencing: Computer Analysis
Pevzner, P. A. (1989) · Journal of Biomolecular Structure and Dynamics · doi:10.1080/07391102.1989.10507752 · Cited by 286
Self-citationToward Simplifying and Accurately Formulating Fragment Assembly
MYERS, E. W. (1995) · Journal of Computational Biology · doi:10.1089/cmb.1995.2.275 · Cited by 238
Combinatorial algorithms for DNA sequence assembly
Kececioglu, J. D., & Myers, E. W. (1995) · Algorithmica · doi:10.1007/bf01188580 · Cited by 225
Eulerian Graphs and Related Topics
(1991) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)x7006-2 · Cited by 214
Low-redundancy sequencing of the entire Lactococcus lactis IL1403 genome
Bolotin, A., Mauger, S., Malarme, K., Ehrlich, S. D., & Sorokin, A. (1999) · Antonie van Leeuwenhoek · doi:10.1023/a:1002048720611 · Cited by 180
Assembly of the Working Draft of the Human Genome with GigAssembler
Kent, W. J., & Haussler, D. (2001) · Genome Research · doi:10.1101/gr.183201 · Cited by 145
Fragment assembly with double-barreled data
Pevzner, P. A., & Tang, H. (2001) · Bioinformatics · doi:10.1093/bioinformatics/17.suppl_1.s225 · Cited by 134
Self-citationProceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology
Bourne, P. E., Gribskov, M., Altman, R. B., Jensen, N. J., Hope, D. A., Lengauer, T., Mitchell, J. C., Scheeff, E. D., Smith, C., Strande, S. M., et al. (2000) · Medical Entomology and Zoology · Cited by 133
Pairwise end sequencing: a unified approach to genomic mapping and sequencing
Roach, J. C., Boysen, C., Wang, K., & Hood, L. (1995) · Genomics · doi:10.1016/0888-7543(95)80219-c · Cited by 128
Lysov, I. P., Vl, F., Khorlin, A. A., Khrapko, K., & Vv, S. (1988) · PubMed · Cited by 115
The accuracy of DNA sequences: Estimating sequence quality
Churchill, G. A., & Waterman, M. S. (1992) · Genomics · doi:10.1016/s0888-7543(05)80288-5 · Cited by 71
Self-citationSpectrum alignment: efficient resequencing by hybridization.
Pe’er, I., & Shamir, R. (2000) · PubMed · Cited by 18
Research works printed but not linked: 3
- Y Lysov, V Florent'ev, A Khorlin, K Khrapko, V Shik, A Mirzabekov Doklady Acad Nauk USSR 303, 1508–1511 (1988).
- Kent W. & Haussler D. (2001) Genome Res . in press.
- P A Pevzner, M S Waterman Proceedings of the Fifth International Conference on Computational Biology (RECOMB 2001, Montreal), pp. 256–265 (2001).
Cited by
SPAdes: A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing
Bankevich, A., Nurk, S., Antipov, D., Gurevich, A. A., Dvorkin, M., Kulikov, A. S., Lesin, V. M., Nikolenko, S. I., Pham, S., Prjibelski, A. D., et al. (2012) · Journal of Computational Biology · doi:10.1089/cmb.2012.0021 · Cited by 25,987
Self-citationFull-length transcriptome assembly from RNA-Seq data without a reference genome
Grabherr, M. G., Haas, B. J., Yassour, M., Levin, J. Z., Thompson, D. A., Amit, I., Adiconis, X., Fan, L., Raychowdhury, R., Zeng, Q., et al. (2011) · Nature Biotechnology · doi:10.1038/nbt.1883 · Cited by 21,039
TopHat: discovering splice junctions with RNA-Seq
Trapnell, C., Pachter, L., & Salzberg, S. L. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp120 · Cited by 11,617
QUAST: quality assessment tool for genome assemblies
Gurevich, A., Saveliev, V., Vyahhi, N., & Tesler, G. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt086 · Cited by 11,172
Velvet: Algorithms for de novo short read assembly using de Bruijn graphs
Zerbino, D. R., & Birney, E. (2008) · Genome Research · doi:10.1101/gr.074492.107 · Cited by 9,491
Metadata
- Authors
- Pevzner, P. A., Tang, H., & Waterman, M. S.
- Affiliations
- University of Southern California (US)
- Venue
- Proceedings of the National Academy of Sciences
- Publisher
- National Academy of Sciences
- Published
- 2001-08-14
- Volume
- 98
- Issue
- 17
- Pages
- 9748-9753
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- PMC
- PMC55524
- OpenAlex
- W2136651963
- Cited by
- 1,352
- References
- 27
- Citations by year
- 2026: 15 · 2025: 27 · 2024: 37 · 2023: 37 · 2022: 62 · 2021: 68 · 2020: 74 · 2019: 68 · 2018: 75 · 2017: 87 · 2016: 92 · 2015: 82 · 2014: 93 · 2013: 110 · 2012: 113
- FWCI
- 5.80
- Type
- journal article
- Language
- en
- Open access
- green
- europepmc.org
- Locations
- Proceedings of the National Academy of Sciences (publishedVersion)
- Europe PMC (PubMed Central) (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- DNA fragment assembly, Eulerian paths, overlap-layout-consensus, sequence assembly
- MeSH terms
- Algorithms, DNA, Bacterial, Models, Theoretical, Neisseria meningitidis, Software, Lactococcus lactis, Campylobacter jejuni, Sequence Alignment, Genome, Bacterial, Sequence Analysis, DNA, Contig Mapping
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.