The fragment assembly string graph
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes. Contact: gene@eecs.berkeley.edu
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“This problem is known to be NP-hard classically, [233,234] although efficient heuristic classical solutions to it have been developed over the years.[235,236]”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [233]
Citations
Cites
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
Self-citationNetwork Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034 · cited 4×
“Formally, a minimum cost network flow problem (Ahuja et al., 1993) is usually formulated as follows: In these terms our problem is as follows (where we have used a known transformation to convert the lower bounds into 0's by capturing them in the supply/demand values): The particularly simple…”
BackgroundInfluentialThe Genome Sequence of Drosophila melanogaster
Adams, M. D., Celniker, S. E., Holt, R. A., Evans, C. A., Gocayne, J. D., Amanatides, P. G., Scherer, S. E., Li, P. W., Hoskins, R. A., Galle, R. F., et al. (2000) · Science · doi:10.1126/science.287.5461.2185 · Cited by 5,929 · cited 1×
“…whole genome shotgun sequencing has become the prevailing paradigm for the first phase of sequencing an organism's genome (Weber and Myers, 1997; Adams et al., 2000; Venter et al., 2001) and routinely delivers 95–99% of the euchromatic sequence in large scaffolds of ordered and oriented contigs.”
BackgroundWhole-Genome Shotgun Assembly and Analysis of the Genome of Fugu rubripes
Aparicio, S., Chapman, J., Stupka, E., Putnam, N., Chia, J.-M., Dehal, P., Christoffels, A., Rash, S., Hoon, S., Smit, A., et al. (2002) · Science · doi:10.1126/science.1072104 · Cited by 1,591 · cited 1×
“…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
BackgroundA 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 · cited 1×
“…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
BackgroundSelf-citationAn Eulerian path approach to DNA fragment assembly
Pevzner, P. A., Tang, H., & Waterman, M. S. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.171285098 · Cited by 1,352 · cited 1×
“This approach was subsequently extended by Pevzner et al. (2001) of his research group giving rise to the Euler assembler.”
MethodGenomic mapping by fingerprinting random clones: A mathematical analysis
Lander, E. S., & Waterman, M. S. (1988) · Genomics · doi:10.1016/0888-7543(88)90007-9 · Cited by 961 · cited 2×
“For example, an assembler that takes a 97% reconstruction and improves it to 99% is reducing the amount of unresolved sequence by a factor of three (from 3% to 1%) and, typically, improving contig sizes by a factor of 10 or more (by resolving 90% of the gaps) according to the Poisson statistical theory of sampling (La…”
MethodA 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 · cited 1×
“In 1992 this author and Waterman–Idury presented two new ideas for fragment assembly in back to back talks at a DIMACs workshop on bioinformatics which were later published in the same volume of a journal (Myers, 1995; Idury and Waterman, 1995).”
BackgroundHuman Whole-Genome Shotgun Sequencing
Weber, J. L., & Myers, E. W. (1997) · Genome Research · doi:10.1101/gr.7.5.401 · Cited by 311 · cited 2×
“Paired-end whole genome shotgun sequencing has become the prevailing paradigm for the first phase of sequencing an organism’s genome (Weber and Myers, 1997; Adams et al., 2000; Venter et al., 2001) and routinely delivers 95–99% of the euchromatic sequence in large scaffolds of ordered and oriented contigs.”
BackgroundSelf-citationWhole-Genome Sequence Assembly for Mammalian Genomes: Arachne 2
Jaffe, D. B., Butler, J., Gnerre, S., Mauceli, E., Lindblad-Toh, K., Mesirov, J. P., Zody, M. C., & Lander, E. S. (2003) · Genome Research · doi:10.1101/gr.828403 · Cited by 307 · cited 1×
“…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
BackgroundPCAP: A Whole-Genome Assembly Program
Huang, X., Wang, J., Aluru, S., Yang, S.-P., & Hillier, L. (2003) · Genome Research · doi:10.1101/gr.1390403 · Cited by 288 · cited 1×
“…capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Huang et al., 2003).”
BackgroundToward Simplifying and Accurately Formulating Fragment Assembly
MYERS, E. W. (1995) · Journal of Computational Biology · doi:10.1089/cmb.1995.2.275 · Cited by 238 · cited 2×
“In 1992 this author and Waterman–Idury presented two new ideas for fragment assembly in back to back talks at a DIMACs workshop on bioinformatics which were later published in the same volume of a journal (Myers, 1995; Idury and Waterman, 1995).”
BackgroundMethodSelf-citationCombinatorial algorithms for DNA sequence assembly
Kececioglu, J. D., & Myers, E. W. (1995) · Algorithmica · doi:10.1007/bf01188580 · Cited by 225 · cited 2×
“This framework was first introduced by this author and Kececioglu ( Kececioglu and Myers, 1995 ).”
MethodSelf-citationMullikin, J. C., & Ning, Z. (2003) · Genome Research · doi:10.1101/gr.731003 · Cited by 222 · cited 2×
“There are currently a number of assemblers capable of wholegenome assembly that all perform comparably by employing variations on the basic paradigm of first finding and assembling unique stretches of DNA with high reliability (Myers et al., 2000; Aparicio et al., 2002; Mullikin and Ning, 2003; Jaffe et al., 2003; Hua…”
BackgroundA dataset generator for whole genome shotgun sequencing.
Myers, E. W. (1999) · PubMed · Cited by 74
Self-citationEfficient q-Gram Filters for Finding All ε-Matches over a Given Length
Rasmussen, K. R., Stoye, J., & Myers, E. W. (2005) · Lecture notes in computer science · doi:10.1007/11415770_15 · Cited by 72
Self-citation
Cited by
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
“The simplification of two nodes into one is analogous to the conventional concatenation of two character strings, and also to some string graph based methods (Myers 2005).”
BackgroundMethodCanu: scalable and accurate long-read assembly via adaptive k -mer weighting and repeat separation
Koren, S., Walenz, B. P., Berlin, K., Miller, J. R., Bergman, N. H., & Phillippy, A. M. (2017) · Genome Research · doi:10.1101/gr.215087.116 · Cited by 7,304
“Instead, Miniasm generates a string graph (Myers 2005) directly from approximate read overlaps and labels the edges of this graph with the raw read sequences.”
BackgroundAssembly of long, error-prone reads using repeat graphs
Kolmogorov, M., Yuan, J., Lin, Y., & Pevzner, P. A. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0072-8 · Cited by 5,986
Haplotype-resolved de novo assembly using phased assembly graphs with hifiasm
Cheng, H., Concepcion, G. T., Feng, X., Zhang, H., & Li, H. (2021) · Nature Methods · doi:10.1038/s41592-020-01056-5 · Cited by 5,859
The complete sequence of a human genome
Nurk, S., Koren, S., Rhie, A., Rautiainen, M., Bzikadze, A. V., Mikheenko, A., Vollger, M. R., Altemose, N., Uralsky, L., Gershman, A., et al. (2022) · Science · doi:10.1126/science.abj6987 · Cited by 3,136
“To enable assembly of the highly repetitive centromeric satellite arrays and closely related segmentalduplications,wedevelopedmethods Table 1.”
BackgroundSelf-citation
Metadata
- Authors
- Myers, E. W.
- Affiliations
- University of California, Berkeley (US)
- Corresponding author
- Myers, Eugene W.
- ORCID
- Myers, Eugene W.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2005-09-01
- Volume
- 21
- Issue
- suppl_2
- Pages
- ii79-ii85
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2156104322
- Cited by
- 424
- References
- 16
- Citations by year
- 2026: 8 · 2025: 14 · 2024: 16 · 2023: 19 · 2022: 19 · 2021: 27 · 2020: 28 · 2019: 37 · 2018: 28 · 2017: 34 · 2016: 37 · 2015: 22 · 2014: 24 · 2013: 22 · 2012: 28
- FWCI
- 2.27
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Bioinformatics (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 › Genetics › Genome Rearrangement Algorithms
- Keywords
- string graphs, DNA sequence assembly, transitive reduction, de Bruijn graph, unitigs, whole genome assembly, mammalian genomes
- MeSH terms
- Algorithms, Base Sequence, Chromosome Mapping, Molecular Sequence Data, Sequence Analysis, DNA, DNA Fragmentation
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.