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).”
Background
Cited by
Items 401–437 of 437
Correction: Bayesian Genome Assembly and Assessment by Markov Chain Monte Carlo Sampling
Staff, T. P. O. (2014) · PLoS ONE · doi:10.1371/journal.pone.0104331
Lavenier, D. D. (2022) · Wiley eBooks · doi:10.1002/9781394169641.ch4
Jochheim, A. (2022) · eDiss (Georg-August-Universität Göttingen) · doi:10.53846/goediss-9608
PAPerFly: Partial Assembly-based Peak Finder for ab initio binding site reconstruction
Faltejsková, K., & Vondrášek, J. (2023) · BMC Bioinformatics · doi:10.1186/s12859-023-05613-5
“Modern approaches to genome assembly translate the sequencing reads to a de Bruijn graph [19].”
MethodThe De Bruijn Graph Sequence Mapping Problem with Changes in the GraphPreprint
Rocha, L. B., Adi, S. S., & Araújo, E. (2024) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2024.02.15.580401
“To address this bias, one approach is to represent multiple sequences through a more robust structure, such as a sequence graph or De Bruijn graph [6], [7], [13], [14].”
BackgroundMethodNew approaches for exploitation of high throughput sequencing data
Limasset, A. (2017) · theses.fr (ABES)
Prjibelski, A. D., Korobeynikov, A., & Lapidus, A. L. (2019) · Elsevier eBooks · doi:10.1016/b978-0-323-95502-7.00376-6 · Cited by 1
Next Generation Sequence Analysis
Singh, P. (2025) · Elsevier eBooks · doi:10.1016/b978-0-323-95502-7.00207-4
Haplotype-aware long-read error correction
Barak, P., Gibney, D., & Jain, C. (2026) · Algorithms for Molecular Biology · doi:10.1186/s13015-026-00302-3
“However, we assume the availability of a collection of overlaps between reads, which is a common first step in most long-read assemblers [18].”
Methods for Chromosome-Scale Haplotype Reconstruction
Garg, S. (2025) · Methods in molecular biology · doi:10.1007/978-1-0716-4702-8_2
On the Coverage Required for Diploid Genome Assembly
Mahajan, D., Jain, C., & Kashyap, N. (2025) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbbio.2025.3594365
“The other approach includes building a read-overlap graph [9].”
Chromosome level genome assembly of tea tussock moth, Euproctis pseudoconspersa
Zhang, K., Long, Y., Qu, H., Wang, L., Li, M., Luo, Z., Cai, X., Bian, L., Fu, N., Chen, L., et al. (2025) · Scientific Data · doi:10.1038/s41597-025-06275-z
“19) 14–16 .”
Hierarchical Assembly of Pools
Vicedomini, R., Vezzi, F., Scalabrin, S., Arvestad, L., & Policriti, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-16480-9_21
“There are four kinds of edges and they correspond to the different types of overlaps [7].”
BackgroundMethodInfluentialFaltejsková, K., & Vondrášek, J. (2024) · Figshare · doi:10.6084/m9.figshare.26656465
Additional file 5 of Trycycler: consensus long-read assemblies for bacterial genomes
Wick, R. R., Judd, L. M., Cerdeira, L. T., Hawkey, J., Méric, G., Vezina, B., Wyres, K. L., & Holt, K. E. (2021) · Figshare · doi:10.6084/m9.figshare.16621068
Additional file 3 of Trycycler: consensus long-read assemblies for bacterial genomes
Wick, R. R., Judd, L. M., Cerdeira, L. T., Hawkey, J., Méric, G., Vezina, B., Wyres, K. L., & Holt, K. E. (2021) · Figshare · doi:10.6084/m9.figshare.16621062
Yang, L. (. (2023) · cIRcle (University of British Columbia) · doi:10.14288/1.0437700
Additional file 2 of Trycycler: consensus long-read assemblies for bacterial genomes
Wick, R. R., Judd, L. M., Cerdeira, L. T., Hawkey, J., Méric, G., Vezina, B., Wyres, K. L., & Holt, K. E. (2021) · Figshare · doi:10.6084/m9.figshare.16621059
Additional file 1 of Trycycler: consensus long-read assemblies for bacterial genomes
Wick, R. R., Judd, L. M., Cerdeira, L. T., Hawkey, J., Méric, G., Vezina, B., Wyres, K. L., & Holt, K. E. (2021) · Figshare · doi:10.6084/m9.figshare.16621056
Additional file 4 of Trycycler: consensus long-read assemblies for bacterial genomes
Wick, R. R., Judd, L. M., Cerdeira, L. T., Hawkey, J., Méric, G., Vezina, B., Wyres, K. L., & Holt, K. E. (2021) · Figshare · doi:10.6084/m9.figshare.16621065
Minimizer Sketches of Lyndon-Fingerprints: A Novel Approach to Compute Overlaps Among Long Reads
Masri, O., Pirola, Y., Borghi, C., Bonizzoni, P., & Rizzi, R. (2025) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm66473.2025.11356736
“Identifying common regions (overlaps) among genomic reads is fundamental for genome assembly [1], [2], as overlaps reveal which fragments come from adjacent genomic regions.”
Efficient algorithms for de novo assembly of alternative splicing events from RNA-seq data
Sacomoto, G. (2014) · theses.fr (ABES) · doi:10.70675/227c5353zd464z4032zac03z957ba1e3060a
Étude bioinformatique des génomes de Porphyromonas
Acuña-Amador, L. (2017) · theses.fr (ABES) · doi:10.70675/c279fa04z0158z4b22z83e9z15e653f91b25
Nouvelles approches pour l'exploitation des données de séquences génomique haut débit
Limasset, A. (2017) · theses.fr (ABES) · doi:10.70675/1e1d281ezc0f7z4f31z8e50zb22eb5be7746 · Cited by 1
Gravouil, K. (2019) · theses.fr (ABES) · doi:10.70675/d91a3321z646fz4691zb1f5z1e5039b15385
Novel components at the periphery of long read genome assembly tools
Marijon, P. (2019) · theses.fr (ABES) · doi:10.70675/e6155b25z6fd5z46b9z810bz866d4ffba178
Development of new algorithms to advance on the discovery of microRNAs
Moraga, C. (2020) · theses.fr (ABES) · doi:10.70675/665a0f0az6edfz4dedzbb07z4c5db14cdec5
Identification and quantification of microbial strains in metagenomic samples using variation graphs
Silva, K. D. (2022) · theses.fr (ABES) · doi:10.70675/2282f0fcz2e22z4011za382z46db1edca98f
Adu, A. F., Menkah, E. S., Amoako-Yirenkyi, P., & Salifu, S. P. (2026) · Research Square · doi:10.21203/rs.3.rs-8997819/v1
“Early methods based on overlap graphs [1], depict reads as nodes and represent the suffix-prefix overlaps as edges.”
COGRAM: Genome Assembly through Graph Neural NetworksPreprint
Coggins, W., & Ramasamy, V. (2026) · Research Square · doi:10.21203/rs.3.rs-9829976/v1
Sankar, N. G., Miliotis, G., & Caton, S. J. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.09.04.749434
“We replace the graph layout optimisation component within a Unicycler long-read assembly workflow [53], with a quantum optimisation approach (Figure 1): the assembly string graph [35] produced in Unicycler is framed as a variant of the TSP, and converted into a QUBO formulation similar to Ref [2].”
InfluentialChromosome-level genome assembly and annotation of the white trevally (Pseudocaranx dentex)
Liu, S., Wang, R., Yang, L., Wang, H., Jiang, C., Liu, S., & Zhuang, Z. (2026) · Scientific Data · doi:10.1038/s41597-026-08201-3
RapidAsm: Fast and Memory-efficient HiFi Read De Novo Assembly
Cheng, Y., Chen, Z., & Luo, Q. (2026) · International Conference on Bioinformatics and Biomedical Technology (ICBBT) · doi:10.1145/3822521.3822535
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.