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
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-citationPhased diploid genome assembly with single-molecule real-time sequencing
Chin, C.-S., Peluso, P., Sedlazeck, F. J., Nattestad, M., Concepcion, G. T., Clum, A., Dunn, C., O'Malley, R., Figueroa-Balderas, R., Morales-Cruz, A., et al. (2016) · Nature Methods · doi:10.1038/nmeth.4035 · Cited by 1,904
Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
Li, H. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw152 · Cited by 1,508
Oases:robust de novo RNA-seq assembly across the dynamic range of expression levels
Schulz, M. H., Zerbino, D. R., Vingron, M., & Birney, E. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts094 · Cited by 1,424
“Scaffold construction takes place in two stages similarly to the approach described by Butler et al. (2008).”
MethodAssembly algorithms for next-generation sequencing data
Miller, J. R., Koren, S., & Sutton, G. (2010) · Genomics · doi:10.1016/j.ygeno.2010.03.001 · Cited by 1,154
“Network flowanalysis has been described for resolution of repeat copy number during genome assembly [52,66].”
TransRate: reference-free quality assessment of de novo transcriptome assemblies
Smith-Unna, R., Boursnell, C., Patro, R., Hibberd, J. M., & Kelly, S. (2016) · Genome Research · doi:10.1101/gr.196469.115 · Cited by 837
Variation graph toolkit improves read mapping by representing genetic variation in the reference
Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4227 · Cited by 821
Efficient de novo assembly of large genomes using compressed data structures
Simpson, J. T., & Durbin, R. (2012) · Genome Research · doi:10.1101/gr.126953.111 · Cited by 768
“Previously, we described a space and time efficient algorithm (Simpson and Durbin 2010) to construct an assembly string graph (Myers 2005) from an FM-index (full-text minute-spaceindex,FerraginaandManzini2000).”
MethodIntegrating Hi-C links with assembly graphs for chromosome-scale assembly
Ghurye, J., Rhie, A., Walenz, B. P., Schmitt, A., Selvaraj, S., Pop, M., Phillippy, A. M., & Koren, S. (2019) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1007273 · Cited by 723
“Most approaches are based on either a de Bruijn (Pevzner et al. , 2001) or a string graph (Myers, 2005) formulation.”
BackgroundMethodWooley, J. C., Godzik, A., & Friedberg, I. (2010) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000667 · Cited by 688
“). Other variations have since been published, adapting to short (100–200)”
BackgroundDe novo assembly and genotyping of variants using colored de Bruijn graphs
Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., & McVean, G. (2012) · Nature Genetics · doi:10.1038/ng.1028 · Cited by 634
De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer
Hernandez, D., François, P., Farinelli, L., Østerås, M., & Schrenzel, J. (2008) · Genome Research · doi:10.1101/gr.072033.107 · Cited by 629
“This application is based on a k -mer graph representation (Idury and Waterman 1995; Pevzner et al. 2001) that structures all k -mers observed in the reads.”
MethodAdvancements in Next-Generation Sequencing
Levy, S. E., & Myers, R. M. (2016) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-083115-022413 · Cited by 599
Nanopore sequencing and the Shasta toolkit enable efficient de novo assembly of eleven human genomes
Shafin, K., Pesout, T., Lorig-Roach, R., Haukness, M., Olsen, H. E., Bosworth, C., Armstrong, J., Tigyi, K., Maurer, N., Koren, S., et al. (2020) · Nature Biotechnology · doi:10.1038/s41587-020-0503-6 · Cited by 567
“How to use this type of information for assembly is a classical problem with a standard solution 62 , the string graph.”
MethodTrycycler: 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) · Genome Biology · doi:10.1186/s13059-021-02483-z · Cited by 531
Piercing the dark matter: bioinformatics of long-range sequencing and mapping
Sedlazeck, F. J., Lee, H., Darby, C. A., & Schatz, M. C. (2018) · Nature Reviews Genetics · doi:10.1038/s41576-018-0003-4 · Cited by 530
“The FALCON assembler and the new MARVEL assembler for PacBio reads operate similarly to Canu, although they both use DALIGNER 43 instead of MHAP to compute the overlaps between reads for error correction and assembly, and form a string graph 44 rather than an overlap graph.”
MethodAssemblathon 1: A competitive assessment of de novo short read assembly methods
Earl, D., Bradnam, K., St. John, J., Darling, A., Lin, D., Fass, J., Yu, H. O. K., Buffalo, V., Zerbino, D. R., Diekhans, M., et al. (2011) · Genome Research · doi:10.1101/gr.126599.111 · Cited by 507
Assembly of large genomes using second-generation sequencing
Schatz, M. C., Delcher, A. L., & Salzberg, S. L. (2010) · Genome Research · doi:10.1101/gr.101360.109 · Cited by 499
Assembly and diploid architecture of an individual human genome via single-molecule technologies
Pendleton, M., Sebra, R., Pang, A. W. C., Ummat, A., Franzen, O., Rausch, T., Stütz, A. M., Stedman, W., Anantharaman, T., Hastie, A., et al. (2015) · Nature Methods · doi:10.1038/nmeth.3454 · Cited by 474
Efficient assembly of nanopore reads via highly accurate and intact error correction
Chen, Y., Nie, F., Xie, S.-Q., Zheng, Y.-F., Dai, Q., Bray, T., Wang, Y.-X., Xing, J.-F., Huang, Z.-J., Wang, D.-P., et al. (2021) · Nature Communications · doi:10.1038/s41467-020-20236-7 · Cited by 446
“Next, we constructed a directed string graph and removed transitive edges using Mayer ’ s algorithm 33 .”
MethodShort read fragment assembly of bacterial genomes
Chaisson, M. J., & Pevzner, P. A. (2008) · Genome Research · doi:10.1101/gr.7088808 · Cited by 441
“A similar approach was recently described by Myers (2005) and Medvedev et al. (2007).”
MethodExploiting sparseness in de novo genome assembly
Ye, C., Ma, Z. S., Cannon, C. H., Pop, M., & Yu, D. W. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-s6-s1 · Cited by 412
“For the OverlapLayout-Consensus [2-5], and the related string graph approach [6,7], each node of the graph represents a sequencing read in the input and an edge connects two nodes if the corresponding sequences ‘overlap’ (the prefix of one sequence matches the suffix of the other with sufficient similarity).”
BackgroundExploring single-sample SNP and INDEL calling with whole-genome de novo assembly
Li, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts280 · Cited by 398
“ABSTRACT Motivation: Eugene Myers in his string graph paper (Myers, 2005)”
BackgroundMinimus: a fast, lightweight genome assembler
Sommer, D. D., Delcher, A. L., Salzberg, S. L., & Pop, M. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-64 · Cited by 398
“2. tigger – a unitigger, i.e. tool that identifies clusters of reads which can be uniquely assembled based on algorithms developed by Myers [28,29]; in graph theoretic terms a unitigger identifies maximal interval subgraphs of the overlap graph.”
MethodGenome assembly reborn: recent computational challenges
Pop, M. (2009) · Briefings in Bioinformatics · doi:10.1093/bib/bbp026 · Cited by 387
“In fact, simple transformations of the overlap graph from the OLC paradigm leads to a graph structure (string graph) that is functionally equivalent to the deBruijn graph of a genome [33], hinting at the equivalence between these assembly paradigms.”
MethodAssembly of long error-prone reads using de Bruijn graphs
Lin, Y., Yuan, J., Kolmogorov, M., Shen, M. W., Chaisson, M., & Pevzner, P. A. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1604560113 · Cited by 382
Genetic variation and the de novo assembly of human genomes
Chaisson, M. J. P., Wilson, R. K., & Eichler, E. E. (2015) · Nature Reviews Genetics · doi:10.1038/nrg3933 · Cited by 336
Long-read sequence assembly of the gorilla genome
Gordon, D., Huddleston, J., Chaisson, M. J. P., Hill, C. M., Kronenberg, Z. N., Munson, K. M., Malig, M., Raja, A., Fiddes, I., Hillier, L. W., et al. (2016) · Science · doi:10.1126/science.aae0344 · Cited by 333
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
Ye, C., Hill, C. M., Wu, S., Ruan, J., & Ma, Z. (2016) · Scientific Reports · doi:10.1038/srep31900 · Cited by 304
Scaffolding of long read assemblies using long range contact information
Ghurye, J., Pop, M., Koren, S., Bickhart, D., & Chin, C.-S. (2017) · BMC Genomics · doi:10.1186/s12864-017-3879-z · Cited by 304
“We use an idea similar to the string graph formulation in [43] to construct the scaffold graph.”
MethodIDBA – A Practical Iterative de Bruijn Graph De Novo Assembler
Peng, Y., Leung, H. C. M., Yiu, S. M., & Chin, F. Y. L. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-12683-3_28 · Cited by 293
“String graph algorithms [9, 14] represent each read by a vertex and there is a directed edge from vertex u to vertex v if the suffix of at least x nucleotides of read u is the same as the prefix of read v.”
BackgroundDe novo fragment assembly with short mate-paired reads: Does the read length matter?
Chaisson, M. J., Brinza, D., & Pevzner, P. A. (2009) · Genome Research · doi:10.1101/gr.079053.108 · Cited by 279
Benchmarking of long-read assemblers for prokaryote whole genome sequencing
Wick, R. R., & Holt, K. E. (2021) · F1000Research · doi:10.12688/f1000research.21782.4 · Cited by 278
Detection of Genomic Structural Variants from Next-Generation Sequencing Data
Tattini, L., D’Aurizio, R., & Magi, A. (2015) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2015.00092 · Cited by 273
“, collapsing simple paths without branches) (Myers, 2005).”
BackgroundEfficient construction of an assembly string graph using the FM-index
Simpson, J. T., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq217 · Cited by 254
“Published by Oxford University Press. by-nc/2.5), which permits unrestricted non-commercial use, distribution, and”
InfluentialGraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Vollmers, J., Wiegand, S., & Kaster, A.-K. (2017) · PLoS ONE · doi:10.1371/journal.pone.0169662 · Cited by 240
“By employing the string graph approach [49] it can cope with short Illumina read lengths and the related repeat resolution problems in a similar way as de Bruijn graph approaches, but with the advantage of preserving the complete sequence context information for every read.”
MethodBenchmarking of long-read assemblers for prokaryote whole genome sequencing
Wick, R. R., & Holt, K. E. (2019) · F1000Research · doi:10.12688/f1000research.21782.1 · Cited by 230
New approaches for metagenome assembly with short reads
Ayling, M., Clark, M. D., & Leggett, R. M. (2020) · Briefings in Bioinformatics · doi:10.1093/bib/bbz020 · Cited by 218
“A bi-directed graph [47, 48] is built up by matching reads to one another, and this is simplified by removing transitive edges (reads that are completely contained within a larger contiguous structure).”
BackgroundErrors in long-read assemblies can critically affect protein prediction
Watson, M., & Warr, A. (2019) · Nature Biotechnology · doi:10.1038/s41587-018-0004-z · Cited by 224
Genome assembly in the telomere-to-telomere era
Li, H., & Durbin, R. (2024) · Nature Reviews Genetics · doi:10.1038/s41576-024-00718-w · Cited by 224
“Modern long-read assemblers are graph-based; in other words, they construct an assembly graph, either an overlap graph 92,93 (HiCanu and hifiasm) or a de Bruijn graph (DBG 94,95 ; Verkko and LJA), from input reads.”
Zerbino, D. R., McEwen, G. K., Margulies, E. H., & Birney, E. (2009) · PLoS ONE · doi:10.1371/journal.pone.0008407 · Cited by 223
“but in its current implementation, Velvet only relies on contig coverage values, using a statistic derived from the A-statistic”
MethodScalable telomere-to-telomere assembly for diploid and polyploid genomes with double graph
Cheng, H., Asri, M., Lucas, J., Koren, S., & Li, H. (2024) · Nature Methods · doi:10.1038/s41592-024-02269-8 · Cited by 222
“Practical implementations of the string graph remove all contained reads when building graphs, since the edges in the string graph correspond to the prefix-to-suffix or suffix-to-prefix overlaps between reads 12 .”
Meraculous: De Novo Genome Assembly with Short Paired-End Reads
Chapman, J. A., Ho, I., Sunkara, S., Luo, S., Schroth, G. P., & Rokhsar, D. S. (2011) · PLoS ONE · doi:10.1371/journal.pone.0023501 · Cited by 212
Next Generation Sequence Assembly with AMOS
Treangen, T. J., Sommer, D. D., Angly, F. E., Koren, S., & Pop, M. (2011) · Current Protocols in Bioinformatics · doi:10.1002/0471250953.bi1108s33 · Cited by 212
Long-read sequence and assembly of segmental duplications
Vollger, M. R., Dishuck, P. C., Sorensen, M., Welch, A. E., Dang, V., Dougherty, M. L., Graves-Lindsay, T. A., Wilson, R. K., Chaisson, M. J. P., & Eichler, E. E. (2019) · Nature Methods · doi:10.1038/s41592-018-0236-3 · Cited by 200
The present and future of de novo whole-genome assembly
Sohn, J.-I., & Nam, J.-W. (2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbw096 · Cited by 196
High-quality metagenome assembly from long accurate reads with metaMDBG
Benoit, G., Raguideau, S., James, R., Phillippy, A. M., Chikhi, R., & Quince, C. (2024) · Nature Biotechnology · doi:10.1038/s41587-023-01983-6 · Cited by 195
“…paradigms for sequence assembly: string graph methods that operate with individual reads, which consider pair-wise overlaps and construct graphs to represent them 12 , and de Bruijn graph (DBG) assemblers, in which reads are first decomposed into short, fixed-length sequences ( k -mers) 13 .”
Advancements in long-read genome sequencing technologies and algorithms
Espinosa, E., Bautista, R., Larrosa, R., & Plata, O. (2024) · Genomics · doi:10.1016/j.ygeno.2024.110842 · Cited by 189
A hybrid approach for the automated finishing of bacterial genomes
Bashir, A., Klammer, A. A., Robins, W. P., Chin, C.-S., Webster, D., Paxinos, E., Hsu, D., Ashby, M., Wang, S., Peluso, P., et al. (2012) · Nature Biotechnology · doi:10.1038/nbt.2288 · Cited by 186
Lang, D., Zhang, S., Ren, P., Liang, F., Sun, Z., Meng, G., Tan, Y., Li, X., Lai, Q., Han, L., et al. (2020) · GigaScience · doi:10.1093/gigascience/giaa123 · Cited by 168
“Repetitive elements with such lengths exceed the typical length generated by PacBio CCS; therefore the right path can hardly be disentangled from complicated string graphs [22, 31].”
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. (2021) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2021.05.26.445798 · Cited by 164
Self-citationAssembly complexity of prokaryotic genomes using short reads
Kingsford, C., Schatz, M. C., & Pop, M. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-21 · Cited by 155
“The more general formulation of the de Bruijn graph used in this paper, and the closely related string graph, are commonly used in the sequence assembly literature [23-26] under the same name, and we follow the same convention.”
MethodComputability of Models for Sequence Assembly
Medvedev, P., Georgiou, K., Myers, G., & Brudno, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74126-8_27 · Cited by 160
“Bidirected graphs were further used for sequence assembly in [9, 10] and to model breakpoint graphs in [7].”
BackgroundMethodInfluentialSelf-citationReptile: representative tiling for short read error correction
Yang, X., Dorman, K. S., & Aluru, S. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq468 · Cited by 158
“In this context, de Bruijn graph (Idury and Waterman, 1995) and string graph (Myers, 2005) based formulations that reconstruct the genome as a path in a graph perform better due to their more global analysis and ability to naturally accommodate paired read information.”
BackgroundNext-Generation Sequence Assembly: Four Stages of Data Processing and Computational Challenges
El‐Metwally, S., Hamza, T., Zakaria, M., & Helmy, M. (2013) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003345 · Cited by 181
“Another alternative representation of a classical overlap graph is a string graph, which is a simplified version constructed from only irreducible (nontransitive) edges [67].”
BackgroundMethodNext-Generation Sequencing and Large Genome Assemblies
Henson, J., Tischler, G., & Ning, Z. (2012) · Pharmacogenomics · doi:10.2217/pgs.12.72 · Cited by 134
HiTEC: accurate error correction in high-throughput sequencing data
Ilie, L., Fazayeli, F., & Ilie, S. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq653 · Cited by 158
“If not, then L can be estimated by a biological experiment or an expectation-maximization procedure (such as in (Myers, 2005)).”
MethodChromosome assembly of large and complex genomes using multiple references
Kolmogorov, M., Armstrong, J., Raney, B. J., Streeter, I., Dunn, M., Yang, F., Odom, D., Flicek, P., Keane, T. M., Thybert, D., et al. (2018) · Genome Research · doi:10.1101/gr.236273.118 · Cited by 128
Parametric Complexity of Sequence Assembly: Theory and Applications to Next Generation Sequencing
Nagarajan, N., & Pop, M. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2009.0005 · Cited by 148
Estimation of rearrangement phylogeny for cancer genomes
Greenman, C. D., Pleasance, E. D., Newman, S., Yang, F., Fu, B., Nik-Zainal, S., Jones, D., Lau, K. W., Carter, N., Edwards, P. A. W., et al. (2012) · Genome Research · doi:10.1101/gr.118414.110 · Cited by 121
“Subsequently, each end of an edge either points in a leftward or a rightward direction, resulting in a bidirectional graph, a type of graph that has seen utility in assembly problems (Myers 2005; Medvedev et al. 2007).”
BackgroundThe Theory and Practice of Genome Sequence Assembly
Simpson, J. T., & Pop, M. (2015) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-090314-050032 · Cited by 109
Error correction and assembly complexity of single molecule sequencing reads
Lee, H., Gurtowski, J., Yoo, S., Marcus, S., McCombie, W. R., & Schatz, M. (2014) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/006395 · Cited by 113
“ECTools requires the low-error rate short reads be pre-assembled into high quality ”unitigs” [Myers, 2005] as the basis for the long read correction.”
Computational methods for chromosome-scale haplotype reconstruction
Garg, S. (2021) · Genome Biology · doi:10.1186/s13059-021-02328-9 · Cited by 116
Maximum Likelihood Genome Assembly
Medvedev, P., & Brudno, M. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2009.0047 · Cited by 110
“Through this process, Myers (2005) classifies all edges as either unique, required, or optional, and the goal of the assembly is to find the shortest walk that respects all the edge constraints.”
InfluentialInferring viral quasispecies spectra from 454 pyrosequencing reads
Astrovskaya, I., Tork, B., Mangul, S., Westbrooks, K., Măndoiu, I., Balfe, P., & Zelikovsky, A. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-s6-s1 · Cited by 113
Centromere evolution and CpG methylation during vertebrate speciation
Ichikawa, K., Tomioka, S., Suzuki, Y., Nakamura, R., Doi, K., Yoshimura, J., Kumagai, M., Inoue, Y., Uchida, Y., Irie, N., et al. (2017) · Nature Communications · doi:10.1038/s41467-017-01982-7 · Cited by 110
“We enumerated structural variants (SVs) between two genomes according to the following steps: (1) used generic markers to identify reciprocally best matching pairs of contigs in the genomes, (2) listed local alignments between the genomes using LAST, (3) chained the local alignments using the idea of dynamic programmi…”
MethodMultiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads
Bankevich, A., Bzikadze, A. V., Kolmogorov, M., Antipov, D., & Pevzner, P. A. (2022) · Nature Biotechnology · doi:10.1038/s41587-022-01220-6 · Cited by 116
Kourami: graph-guided assembly for novel human leukocyte antigen allele discovery
Lee, H., & Kingsford, C. (2018) · Genome Biology · doi:10.1186/s13059-018-1388-2 · Cited by 93
Omega: an Overlap-graph de novo Assembler for Metagenomics
Haider, B., Ahn, T.-H., Bushnell, B., Chai, J., Copeland, A., & Pan, C. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu395 · Cited by 96
“After inserting all edges of read r , all transitive edges incident on read r are removed using a linear algo-rithm as described (Haider, 2012; Myers, 2005).”
MethodInfluentialGraphBin: refined binning of metagenomic contigs using assembly graphs
Mallawaarachchi, V., Wickramarachchi, A., & Lin, Y. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa180 · Cited by 110
Assembly of chromosome-scale contigs by efficiently resolving repetitive sequences with long reads
Du, H., & Liang, C. (2019) · Nature Communications · doi:10.1038/s41467-019-13355-3 · Cited by 103
Quantum Computing for Molecular Biology**
Baiardi, A., Christandl, M., & Reiher, M. (2023) · ChemBioChem · doi:10.1002/cbic.202300120 · Cited by 93
HINGE: long-read assembly achieves optimal repeat resolution
Kamath, G. M., Shomorony, I., Xia, F., Courtade, T. A., & Tse, D. N. (2017) · Genome Research · doi:10.1101/gr.216465.116 · Cited by 91
Superbubbles, Ultrabubbles, and Cacti
Paten, B., Eizenga, J. M., Rosen, Y. M., Novak, A. M., Garrison, E., & Hickey, G. (2018) · Journal of Computational Biology · doi:10.1089/cmb.2017.0251 · Cited by 75
“…especially prominent for sequence representation, in particular the de Bruijn graph (de Bruijn, 1946; Pevzner et al., 2001), the string graph (Myers, 2005), the breakpoint graph (Pevzner, 2000; Alekseyev and Pevzner, 2009), and the bidirected graph (aka sequence graph; Edmonds and Johnson,…”
Unzipping haplotypes in diploid and polyploid genomes
Zhang, X., Wu, R., Wang, Y., Yu, J., & Tang, H. (2019) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2019.11.011 · Cited by 105
Efficient hybrid de novo assembly of human genomes with WENGAN
Genova, A. D., Buena‐Atienza, E., Ossowski, S., & Sagot, M. (2020) · Nature Biotechnology · doi:10.1038/s41587-020-00747-w · Cited by 97
“Regardless of the sequencing technology, the goals of a genome assembler are to reconstruct the complete genome in (1) the fewest possible consecutive pieces (ideally chromosomes) with (2) the highest base accuracy while (3) minimizing the computational resources (the 1–2–3 goals).”
BackgroundCGAL: computing genome assembly likelihoods
Rahman, A., & Pachter, L. (2013) · Genome Biology · doi:10.1186/gb-2013-14-1-r8 · Cited by 85
Optimal assembly for high throughput shotgun sequencing
Bresler, G., Bresler, M., & Tse, D. N. C. (2013) · BMC Bioinformatics · doi:10.1186/1471-2105-14-s5-s18 · Cited by 100
“Note that this objective of reconstructing the original DNA sequence from the reads contrasts with the many optimizationbased formulations of assembly, such as shortest common superstring (SCS) [5], maximum-likelihood [6], [7], and various graph-based formulations [8], [9].”
BackgroundBloom Filter Trie: an alignment-free and reference-free data structure for pan-genome storage
Holley, G., Wittler, R., & Stoye, J. (2016) · Algorithms for Molecular Biology · doi:10.1186/s13015-016-0066-8 · Cited by 97
“PanCake [11] is an extension of string graphs, known from genome assembly [12], which achieves compression based on pairwise alignments.”
BackgroundData compression for sequencing data
Deorowicz, S., & Grabowski, S. (2013) · Algorithms for Molecular Biology · doi:10.1186/1748-7188-8-25 · Cited by 96
De novo detection of copy number variation by co-assembly
Nijkamp, J. F., van den Broek, M. A., Geertman, J.-M. A., Reinders, M. J. T., Daran, J.-M. G., & de Ridder, D. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts601 · Cited by 83
“The graph is subsequently simplified by transitive reduction, which removes redundant edges, followed by unitigging, a process of collapsing simple paths without branches (Myers, 2005).”
BackgroundMethodInfluentialMemory-Efficient Assembly Using Flye
Freire, B., Ladra, S., & Paramá, J. R. (2021) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2021.3108843 · Cited by 91
“The first attempts of long error-prone assemblers were based on Overlap-Layout-Consensus or on similar string graph approaches [28], but these methods have quadratic complexity.”
MethodRead mapping on de Bruijn graphs
Limasset, A., Cazaux, B., Rivals, E., & Peterlongo, P. (2016) · BMC Bioinformatics · doi:10.1186/s12859-016-1103-9 · Cited by 74
“…most assemblers rely on two types of graphs: either the de Bruijn graph (DBG) for the short reads produced by the second generation of sequencing technologies [3], or for long reads the overlap graph (which was introduced in the Celera Assembler [4]) and variants thereof, like the string graph [5].”
BackgroundWang, T., Wang, B., Hua, X., Tang, H., Zhang, Z., Gao, R., Qi, Y., Zhang, Q., Wang, G., Yu, Z., et al. (2023) · Nature Plants · doi:10.1038/s41477-023-01378-0 · Cited by 82
Medvedev, P., Pham, S., Chaisson, M., Tesler, G., & Pevzner, P. A. (2011) · Journal of Computational Biology · doi:10.1089/cmb.2011.0151 · Cited by 94
Homer, N., & Nelson, S. F. (2010) · Genome biology · doi:10.1186/gb-2010-11-10-r99 · Cited by 83
“Read re-alignment methods also have been developed [2,18] for finishing fragment assembly but have not been applied to the short reads produced by next generation sequencing technologies.”
MethodGenome-wide diversity in the California condor tracks its prehistoric abundance and decline
Robinson, J. A., Bowie, R. C. K., Dudchenko, O., Aiden, E. L., Hendrickson, S. L., Steiner, C., Ryder, O. A., Mindell, D. P., & Wall, J. D. (2021) · Current Biology · doi:10.1016/j.cub.2021.04.035 · Cited by 74
Computational graph pangenomics: a tutorial on data structures and their applications
Baaijens, J. A., Bonizzoni, P., Boucher, C. A., Vedova, G. D., Pirola, Y., Rizzi, R., & Sirén, J. (2022) · Natural Computing · doi:10.1007/s11047-022-09882-6 · Cited by 92
Integrating long-range connectivity information into de Bruijn graphs
Turner, I., Garimella, K. V., Iqbal, Z., & McVean, G. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty157 · Cited by 67
A graph-based approach to diploid genome assembly
Garg, S., Rautiainen, M., Novak, A. M., Garrison, E., Durbin, R., & Marschall, T. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty279 · Cited by 66
“In the past decades, a multitude of heuristic approaches to haploid de novo assembly have been proposed (Idury and Waterman, 1995; Myers, 1995, 2005; Nagarajan and Pop, 2009, 2013; Pevzner et al. , 2001; Sovi (cid:2) c et al. , 2013).”
BackgroundChen, B., Zhou, Z., Ke, Q., Wu, Y., Bai, H., Pu, F., & Xu, P. (2019) · Scientific Data · doi:10.1038/s41597-019-0194-3 · Cited by 64
Genome assembly using quantum and quantum-inspired annealing
Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinsky, V. V., Kiktenko, E. O., & Fedorov, A. K. (2021) · Scientific Reports · doi:10.1038/s41598-021-88321-5 · Cited by 63
“[12] E.”
Chin, C.-S., Behera, S., Khalak, A., Sedlazeck, F. J., Sudmant, P. H., Wagner, J., & Zook, J. M. (2023) · Nature Methods · doi:10.1038/s41592-023-01914-y · Cited by 54
“This is analogous to identifying the contigs 51,52 in genome assembly algorithms.”
BackgroundMethodReadjoiner: a fast and memory efficient string graph-based sequence assembler
Gonnella, G., & Kurtz, S. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-82 · Cited by 65
“Myers EW: Toward simplifying and accurately formulating fragment assembly.”
BackgroundMethodInfluential
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.