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 101–200 of 437
Strainberry: automated strain separation in low-complexity metagenomes using long reads
Vicedomini, R., Quince, C., Darling, A. E., & Chikhi, R. (2021) · Nature Communications · doi:10.1038/s41467-021-24515-9 · Cited by 60
Zhang, C., Shao, Z., Kong, Y., Du, H., Li, W., Yang, Z., Li, X., Ke, H., Sun, Z., Shao, J., et al. (2024) · Nature Genetics · doi:10.1038/s41588-024-01901-9 · Cited by 59
Evaluation of hybrid and non-hybrid methods for de novo assembly of nanopore reads
Sović, I., Križanović, K., Skala, K., & Šikić, M. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw237 · Cited by 55
Hernández, D., Tewhey, R., Veyrieras, J., Farinelli, L., Østerås, M., François, P., & Schrenzel, J. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt590 · Cited by 62
Kent, C. F., Dey, A., Patel, H., Tsvetkov, N., Tiwari, T., MacPhail, V. J., Gobeil, Y., Harpur, B. A., Gurtowski, J., Schatz, M. C., et al. (2018) · Frontiers in Genetics · doi:10.3389/fgene.2018.00316 · Cited by 56
“The Celera Assembler uses a string graph approach (Myers, 2005), where the long reads are overlapped to each other to form the initial graph, after which the graph was transformed and simplified to form the final contigs using the bogart unitigging algorithm (Koren et al., 2013).”
MethodOn the Complexity of Sequence-to-Graph Alignment
Jain, C., Zhang, H., Gao, Y. F., & Aluru, S. (2020) · Journal of Computational Biology · doi:10.1089/cmb.2019.0066 · Cited by 56
“Some of the most useful graph-based data structures are de-Bruijn graphs (Pevzner et al., 2001; Iqbal et al., 2012), variation graphs (Novak et al., 2017), string graphs (Myers, 2005), partial order graphs (Lee et al., 2002), and Wheeler graphs (Gagie et al., 2017).”
A de novo metagenomic assembly program for shotgun DNA reads
Lai, B., Ding, R., Li, Y., Duan, L., & Zhu, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts162 · Cited by 58
“Herein, MAP uses the transitive reduction algorithm to remove the transitive edges (Myers, 2005).”
A history of DNA sequence assembly
Myers, E. W. (2016) · it - Information Technology · doi:10.1515/itit-2015-0047 · Cited by 60
“Indeed, given that many compound edges can be confidently identified as being unitigs that must be traversed exactly once in any solution, one can further infer the copy number of other compound edges with a flow analysis [19] and then know that the correct assembly is a generalized Eulerian tour that respects the cop…”
BackgroundSelf-citationOverlap graphs and de Bruijn graphs: data structures for de novogenome assembly in the big data era
Rizzi, R., Beretta, S., Patterson, M., Pirola, Y., Previtali, M., Vedova, G. D., & Bonizzoni, P. (2019) · Quantitative Biology · doi:10.1007/s40484-019-0181-x · Cited by 55
Review of General Algorithmic Features for Genome Assemblers for Next Generation Sequencers
Wajid, B., & Serpedin, E. (2012) · Genomics Proteomics & Bioinformatics · doi:10.1016/j.gpb.2012.05.006 · Cited by 61
“The structure is presented as a bidirectional graph structure [71], where each read corresponds to a node and an edge represents an overlap between two reads/nodes.”
BackgroundDe-Bruijn graph with MapReduce framework towards metagenomic data classification
Kamal, M. S., Parvin, S., Ashour, A. S., Shi, F., & Dey, N. (2017) · International Journal of Information Technology · doi:10.1007/s41870-017-0005-z · Cited by 53
“Basically valvet [46] approach removed the tips in such two criteria.”
BackgroundMethodInfluentialYet another de novo genome assembler
Vaser, R., & Šikić, M. (2019) · International symposium on image and signal processing and analysis/ISPA ... · doi:10.1109/ispa.2019.8868909 · Cited by 49
“Transitive reduction is applied first, as described in [4].”
BackgroundMethodGene and Variant Annotation for Mendelian Disorders in the Era of Advanced Sequencing Technologies
Chakravorty, S., & Hegde, M. (2017) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-083115-022545 · Cited by 50
Parallel de novo assembly of large genomes from high-throughput short reads
Jackson, B. G., Regennitter, M., Yang, X., Schnable, P. S., & Aluru, S. (2010) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2010.5470397 · Cited by 46
“YAGA [9] X X X X X X ABySS [19] X X X X Medvedev [14] X X X X Myers [15] X X”
BackgroundMethodInfluentialSafe and Complete Contig Assembly Through Omnitigs
Tomescu, A. I., & Medvedev, P. (2016) · Journal of Computational Biology · doi:10.1089/cmb.2016.0141 · Cited by 59
“Here, we adopt a model that captures the most popular models: the node-centric de Bruijn graph, the edge-centric de Bruijn graph, and the string graph (Myers, 2005).”
InfluentialHCV Quasispecies Assembly Using Network Flows
Westbrooks, K., Astrovskaya, I., Campo, D. S., Khudyakov, Y. E., Berman, P., & Zelikovsky, A. (2008) · Springer eBooks · doi:10.1007/978-3-540-79450-9_15 · Cited by 46
Memory efficient minimum substring partitioning
Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., & Suri, S. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2535569.2448951 · Cited by 53
“Simpson and Durbin [22] adopted FMindex [9] to achieve compression in building the string graph [16], which is an alternative graph formulation used in sequence assembly (string graph is much more expensive to construct than de Bruijn graph, so it is not as popular as de Bruijn graph).”
MethodComparative analyses of bat genomes identify distinct evolution of immunity in Old World fruit bats
Tian, S., Zeng, J., Jiao, H., Zhang, D., Zhang, L., Lei, C., Rossiter, S. J., & Zhao, H. (2023) · Science Advances · doi:10.1126/sciadv.add0141 · Cited by 46
Cerulean: A Hybrid Assembly Using High Throughput Short and Long Reads
Deshpande, V., Fung, E. D. K., Pham, S., & Bafna, V. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40453-5_27 · Cited by 50
“Two approaches are broadly used by assembly tools to assemble the paired-end reads into complete genomes of genomic contigs: (i) Overlap-layout-consensus assembly was introduced by Staden [2], which was later improvised by the introduction of string graph by Myers [3] (Celera Assembler [4], SGA [5]); (ii) de Bruijn gr…”
MethodSketching and Sublinear Data Structures in Genomics
Marçais, G., Solomon, B., Patro, R., & Kingsford, C. (2019) · Annual Review of Biomedical Data Science · doi:10.1146/annurev-biodatasci-072018-021156 · Cited by 54
“Then S is said to have or admit an A different and more general definition is the gapped LSH (76).”
BackgroundFan, X., Chaisson, M., Nakhleh, L. K., & Chen, K. (2017) · Genome Research · doi:10.1101/gr.214767.116 · Cited by 48
Detecting and phasing minor single-nucleotide variants from long-read sequencing data
Feng, Z., Clemente, J. C., Wong, B. Y., & Schadt, E. E. (2021) · Nature Communications · doi:10.1038/s41467-021-23289-4 · Cited by 43
Parallel short sequence assembly of transcriptomes
Jackson, B. G., Schnable, P. S., & Aluru, S. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-s1-s14 · Cited by 40
“We follow Myers' and Medvedev's lead [3,11] and model the assembly problem as that of finding a tour of a bidirected string graph, which we consider a natural model.”
BackgroundMethodInfluentialNovak, A. M., Hickey, G., Garrison, E., Blum, S., Connelly, A., Dilthey, A., Eizenga, J., Elmohamed, M. A. S., Guthrie, S., Kahles, A., et al. (2017) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/101378 · Cited by 34
“The explicit use of graphs in biological sequence analysis has a long history, notably for sequence alignment 12 , sequence assembly 13,14 , assembly representation (as in FASTG and now GFA) 15,16 , substring indexes (which are often thought of in terms of suffix trees or similar data structures)…”
BackgroundChang, Y.-J., Chen, C.-C., Chen, C.-L., & Ho, J.-M. (2012) · BMC Genomics · doi:10.1186/1471-2164-13-s7-s28 · Cited by 42
“String graph-based approaches have the benefits of read coherence [11], less memory requirement, and successful experience in analyzing Sanger sequence data [23].”
BackgroundMethodDe novo diploid genome assembly using long noisy reads
Nie, F., Ni, P., Huang, N., Zhang, J., Wang, Z., Xiao, C., Luo, F., & Wang, J. (2024) · Nature Communications · doi:10.1038/s41467-024-47349-7 · Cited by 43
High-resolution metagenome assembly for modern long reads with myloasm
Shaw, J., Marin, M. G., & Li, H. (2026) · Nature Biotechnology · doi:10.1038/s41587-026-03053-z · Cited by 40
Zhang, Y., Sun, Y., & Cole, J. R. (2014) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1003737 · Cited by 41
“Our overlap graph is different from a standard overlap graph [48–50] in the edge creation criteria and graph construction procedure.”
The sequence and de novo assembly of Takifugu bimaculatus genome using PacBio and Hi-C technologies
Zhou, Z., Лю, Б., Chen, B., Shi, Y., Pu, F., Bai, H., Li, L., & Xu, P. (2019) · Scientific Data · doi:10.1038/s41597-019-0195-2 · Cited by 39
Hapsembler: An Assembler for Highly Polymorphic Genomes
Donmez, N., & Brudno, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20036-6_5 · Cited by 42
“These edges are removed from the graph using an operation called transitive edge reduction [7] as illustrated in Figure 2.”
MethodAccurate Binning of Metagenomic Contigs Using Composition, Coverage, and Assembly Graphs
Mallawaarachchi, V., & Lin, Y. (2022) · Journal of Computational Biology · doi:10.1089/cmb.2022.0262 · Cited by 39
Chen, Y., Nie, F., Xie, S., Zheng, Y., Bray, T., Dai, Q., Wang, Y.-X., Xing, J.-F., Huang, Z., Wang, D., et al. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.02.01.930107 · Cited by 38
Recent advances in sequence assembly: principles and applications
Chen, Q., Lan, C., Zhao, L., Wang, J., Chen, B., & Chen, Y. P. (2017) · Briefings in Functional Genomics · doi:10.1093/bfgp/elx006 · Cited by 40
Pan-Genome Storage and Analysis Techniques
Zekic, T., Holley, G., & Stoye, J. (2017) · Methods in molecular biology · doi:10.1007/978-1-4939-7463-4_2 · Cited by 40
Identification of Common Carp Innate Immune Genes with Whole-Genome Sequencing and RNA-Seq Data
Zhang, Y., Stupka, E., Henkel, C. V., Jansen, H. J., Spaink, H. P., & Verbeek, F. J. (2011) · Berichte aus der medizinischen Informatik und Bioinformatik/Journal of integrative bioinformatics · doi:10.1515/jib-2011-169 · Cited by 40
“A de Bruijn graph is a directed graph representing overlaps between sequences of symbols [8].”
BackgroundMaking sense of genomes of parasitic worms: Tackling bioinformatic challenges
Korhonen, P. K., Young, N. D., & Gasser, R. B. (2016) · Biotechnology Advances · doi:10.1016/j.biotechadv.2016.03.001 · Cited by 39
Huson, D. H., Tappu, R., Bazinet, A. L., Xie, C., Cummings, M. P., Nieselt, K., & Williams, R. B. H. (2017) · Microbiome · doi:10.1186/s40168-017-0233-2 · Cited by 36
“The algorithm is based on the concept of a string graph [11] and follows the overlap-layout-consensus paradigm [12].”
MethodExploring variation-aware contig graphs for (comparative) metagenomics using MaryGold
Nijkamp, J. F., Pop, M., Reinders, M. J. T., & de Ridder, D. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt502 · Cited by 39
Rakkammal, K., Priya, A., Pandian, S., Maharajan, T., Rathinapriya, P., Satish, L., Ceasar, S. A., Sohn, S.-I., & Ramesh, M. (2022) · Plants · doi:10.3390/plants11212852 · Cited by 35
Biological computation and computational biology: survey, challenges, and discussion
Dagdia, Z. C., Avdeyev, P., & Bayzid, M. S. (2021) · Artificial Intelligence Review · doi:10.1007/s10462-020-09951-1 · Cited by 36
Multiomics analysis provides insights into musk secretion in muskrat and musk deer
Wang, T., Yang, M., Shi, X., Tian, S., Li, Y., Xie, W., Zou, Z., Leng, D., Zhang, M., Zheng, C., et al. (2025) · GigaScience · doi:10.1093/gigascience/giaf006 · Cited by 33
Information-optimal genome assembly via sparse read-overlap graphs
Shomorony, I., Kim, S. H., Courtade, T. A., & Tse, D. N. C. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw450 · Cited by 35
Sequence Alignment on Directed Graphs
Vaddadi, K., Tayal, K., Srinivasan, R., & Sivadasan, N. (2018) · Journal of Computational Biology · doi:10.1089/cmb.2017.0264 · Cited by 35
Genovese, L. M., Geraci, F., & Pellegrini, M. (2008) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2008.67 · Cited by 31
“The average length of a sequenced DNA fragment (also called a read) ranges from 500 to 850 bps (see [15] and [ 17 ]).”
BackgroundAssembly of non-unique insertion content using next-generation sequencing
Parrish, N., Hormozdiari, F., & Eskin, E. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-s6-s3 · Cited by 31
Sequencing of plant genomes – a review
Türktaş, M., Kurtoğlu, K. Y., Dorado, G., Zhang, B., Hernández, P., & Ünver, T. (2015) · TURKISH JOURNAL OF AGRICULTURE AND FORESTRY · doi:10.3906/tar-1409-93 · Cited by 34
“On the other hand, the string graph method (Myers, 2005) is a variant of the OLC approach.”
MethodRyūtō: network-flow based transcriptome reconstruction
Gatter, T., & Stadler, P. F. (2019) · BMC Bioinformatics · doi:10.1186/s12859-019-2786-5 · Cited by 38
“Both transitive contained and overlap edges are removed by using an adaptation ofMyer’s approach for string graphs [30] in linear time.”
MethodFLAS: fast and high-throughput algorithm for PacBio long-read self-correction
Bao, E., Xie, F., Song, C., & Song, D. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz206 · Cited by 27
Rayamajhi, N., CHENG, C.-H. C., & Catchen, J. (2022) · G3 Genes Genomes Genetics · doi:10.1093/g3journal/jkac192 · Cited by 31
Comparing assembly strategies for third-generation sequencing technologies across different genomes
Espinosa, E., Bautista, R., Fernandez, I., Jiménez, R. L., Zapata, E. L., & Plata, Ó. (2023) · Genomics · doi:10.1016/j.ygeno.2023.110700 · Cited by 28
What is the difference between the breakpoint graph and the de Bruijn graph?
Lin, Y., Nurk, S., & Pevzner, P. A. (2014) · BMC Genomics · doi:10.1186/1471-2164-15-s6-s6 · Cited by 31
“It may also clarify the connection between the breakpoint graph, the de Bruijn graph, and the string graph introduced by Myers [30], another powerful paradigm for genome assembly.”
BackgroundResultDe novo co-assembly of bacterial genomes from multiple single cells
Movahedi, N. S., Forouzmand, E., & Chitsaz, H. (2012) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm.2012.6392618 · Cited by 29
Ab Initio Whole Genome Shotgun Assembly with Mated Short Reads
Medvedev, P., & Brudno, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78839-3_5 · Cited by 35
“Myers suggests a similar method to determine the copy-counts in the context of a string graph [15].”
MethodInfluentialApproaches for in silico finishing of microbial genome sequences
Kremer, F. S., McBride, A. J. A., & Pinto, L. D. S. (2017) · Genetics and Molecular Biology · doi:10.1590/1678-4685-gmb-2016-0230 · Cited by 31
Sutton, J. T., Helmkampf, M., Steiner, C., Bellinger, M. R., Korlach, J., Hall, R. J., Baybayan, P. A., Muehling, J., Gu, J., Kingan, S. B., et al. (2018) · Genes · doi:10.3390/genes9080393 · Cited by 26
From Pine Cones to Read Clouds: Rescaffolding the Megagenome of Sugar Pine (Pinus lambertiana)
Crepeau, M., Langley, C. H., & Stevens, K. (2017) · G3 Genes Genomes Genetics · doi:10.1534/g3.117.040055 · Cited by 28
“To create our new assembly we used the fragScaff program from Adey et al. (2014). fragScaff implements a modification of the classic overlap–layout–consensus paradigm (Myers 2005).”
MethodDetecting Alternative Gene Structures from Spliced ESTs: A Computational Approach
Bonizzoni, P., Mauri, G., Pesole, G., Picardi, E., Pirola, Y., & Rizzi, R. (2009) · Journal of Computational Biology · doi:10.1089/cmb.2008.0028 · Cited by 24
“In Myers (2005), an efficient transitive reduction is proposed to reduce the string graph.”
Improving ancient DNA genome assembly
Seitz, A., & Nieselt, K. (2017) · PeerJ · doi:10.7717/peerj.3126 · Cited by 28
Qu, M., Zhang, Y., Gao, Z., Zhang, Z., Liu, Y., Wan, S., Wang, X., Yu, H., Zhang, H., Liu, Y., et al. (2023) · Science China Life Sciences · doi:10.1007/s11427-022-2317-6 · Cited by 23
“The genome was assembled de novo into contigs based on PacBio long reads using FALCON (Li et al., 2012), string graph (Myers, 2005), and hifiasm (Cheng et al., 2021) with optimized parameters.”
MethodString graph construction using incremental hashing
Ben-Bassat, I., & Chor, B. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu578 · Cited by 21
Bloom Filter Trie – A Data Structure for Pan-Genome Storage
Holley, G., Wittler, R., & Stoye, J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48221-6_16 · Cited by 27
“PanCake [8] is an extension of string graphs, known from genome assembly [17], which achieves compression based on pairwise alignments.”
BackgroundFinIS: Improved in silico Finishing Using an Exact Quadratic Programming Formulation
Gao, S., Bertrand, D., & Nagarajan, N. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33122-0_25 · Cited by 24
“Furthermore, the graph can be simplified to encode essential information as a contig graph (or string graph [17]), where reads that assemble unambiguously are compressed into contig nodes (these contigs are in addition to those in the original scaffold) and edges represent contigs that overlap in their ends (Fig.”
BackgroundApproximate all-pairs suffix/prefix overlaps
Välimäki, N., Ladra, S., & Mäkinen, V. (2012) · Information and Computation · doi:10.1016/j.ic.2012.02.002 · Cited by 24
Parallel Construction of Bidirected String Graphs for Genome Assembly
Jackson, B. G., & Aluru, S. (2008) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2008.70 · Cited by 23
“Myers [9] proposed converting the overlap graph to a fragment assembly string graph, or a graph in which the edges are labeled with strings.”
Gelabert, P., Oberreiter, V., Straus, L. G., Morales, M. R. G., Sawyer, S., Marín-Arroyo, A. B., Geiling, J. M., Exler, F., Brück, F., Franz, S., et al. (2025) · Nature Communications · doi:10.1038/s41467-024-55740-7 · Cited by 21
“Filtered reads were processed with SGA 0.10.15 93 and FASTX-toolkit 0.0.14 94 to remove reads with low qualities (base quality lower than 30 in 25% or more of the read length) and exact duplicates (using SGA preprocess with – dust-threshold=1, followed by SGA index with -a ropebwt option, and SGA fi…”
InfluentialParallel String Graph Construction and Transitive Reduction for De Novo Genome Assembly
Guidi, G., Selvitopi, O., Ellis, M., Oliker, L., Yelick, K., & Buluç, A. (2021) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps49936.2021.00060 · Cited by 29
CHOP: haplotype-aware path indexing in population graphs
Mokveld, T., Linthorst, J., Al-Ars, Z., Holstege, H., & Reinders, M. (2020) · Genome Biology · doi:10.1186/s13059-020-01963-y · Cited by 20
“In other words, by extending and subsequently removing edges in G we introduce overlapping sequence as if we were converting G to the repeat-resolved string graph representation of a joint assembly of all genomes in G from all possible reads of length k [35].”
MethodImproving metagenomic binning results with overlapped bins using assembly graphs
Mallawaarachchi, V., Wickramarachchi, A., & Lin, Y. (2021) · Algorithms for Molecular Biology · doi:10.1186/s13015-021-00185-6 · Cited by 24
Approximate string matching for high-throughput sequencing
Siragusa, E. (2015) · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · doi:10.17169/refubium-15562 · Cited by 28
“Computational methods in plan A irst scaffold the reads by performing overlap alignments [Myers, 2005] or equivalently by constructing de Bruijn graphs [Pevzner et al.”
MethodGrigoreva, E., Ulianich, P. S., Ben, C., Gentzbittel, L., & Potokina, E. (2019) · Russian Journal of Genetics · doi:10.1134/s102279541911005x · Cited by 24
On the Complexity of Sequence to Graph Alignment
Jain, C., Zhang, H., Gao, Y. F., & Aluru, S. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17083-7_6 · Cited by 26
Sequence assembly using next generation sequencing data—challenges and solutions
Chin, F. Y. L., Leung, H. C. M., & Yiu, S. (2014) · Science China Life Sciences · doi:10.1007/s11427-014-4752-9 · Cited by 20
LOCAS – A Low Coverage Assembly Tool for Resequencing Projects
Klein, J. D., Ossowski, S., Schneeberger, K., Weigel, D., & Huson, D. H. (2011) · PLoS ONE · doi:10.1371/journal.pone.0023455 · Cited by 22
Multithread Multistring Burrows–Wheeler Transform and Longest Common Prefix Array
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2019) · Journal of Computational Biology · doi:10.1089/cmb.2018.0230 · Cited by 20
“This approach requires the efficient construction of a string graph (Myers, 2005), which is the result of finding all prefix–suffix matches (or overlaps) between reads.”
Strijk, J. S., Hinsinger, D. D., Zhang, F., & Cao, K. (2019) · GigaScience · doi:10.1093/gigascience/giz136 · Cited by 19
LightAssembler: fast and memory-efficient assembly algorithm for high-throughput sequencing reads
El‐Metwally, S., Zakaria, M., & Hamza, T. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw470 · Cited by 20
Medvedev, P., Pham, S., Chaisson, M., Tesler, G., & Pevzner, P. A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20036-6_22 · Cited by 24
Benchmarking of long-read assemblers for prokaryote whole genome sequencing
Wick, R. R., & Holt, K. E. (2020) · F1000Research · doi:10.12688/f1000research.21782.3 · Cited by 18
Safe and Complete Contig Assembly Via Omnitigs
Tomescu, A. I., & Medvedev, P. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-31957-5_11 · Cited by 19
“Or, for strings graphs, it can be broken if transitive edges are not removed from the graph [25].”
BackgroundMethodInfluentialPan, R., Hu, H., Xiao, Y., Xu, L., Xu, Y., Ouyang, K., Li, C., He, T., & Zhang, W. (2023) · Scientific Data · doi:10.1038/s41597-023-02434-2 · Cited by 21
Grigorev, K. A., Kliver, S. F., Dobrynin, P. V., Komissarov, A. S., Wolfsberger, W., Krasheninnikova, K., Afanador-Hernández, Y. M., Brandt, A. L., Paulino, L. A., León, R. C., et al. (2018) · GigaScience · doi:10.1093/gigascience/giy025 · Cited by 18
“This also helps reduce the probability of misassemblies; in theory, any path in a string graph represents a valid assembly [95, 96].”
Narayanan, S. S., Ramachandran, A., Aakur, S. N., & Bagavathi, A. (2020) · International Conference on Machine Learning and Applications · doi:10.1109/icmla51294.2020.00203 · Cited by 20
Metagenomic Chromosome Conformation Capture (3C): techniques, applications, and challenges
Liu, M., & Darling, A. E. (2015) · F1000Research · doi:10.12688/f1000research.7281.1 · Cited by 18
Higher recall in metagenomic sequence classification exploiting overlapping reads
Girotto, S., Comin, M., & Pizzi, C. (2017) · BMC Genomics · doi:10.1186/s12864-017-4273-6 · Cited by 17
“Ideally the overlap would be computed using a reads overlap graph [17], but this approach is highly demanding in terms of RAM.”
MethodCoLoRd: compressing long reads
Kokot, M., Gudyś, A., Li, H., & Deorowicz, S. (2022) · Nature Methods · doi:10.1038/s41592-022-01432-3 · Cited by 22
Viral quasispecies reconstruction from amplicon 454 pyrosequencing reads
Mancuso, N., Tork, B., Skums, P., Măndoiu, I., & Zelikovsky, A. (2011) · IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW) · doi:10.1109/bibmw.2011.6112360 · Cited by 17
Metagenomic reads binning with spaced seeds
Girotto, S., Comin, M., & Pizzi, C. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.05.023 · Cited by 17
“Ideally the overlap would be computed using a reads overlap graph [22], but this approach is highly demanding in terms of RAM.”
MethodA safe and complete algorithm for metagenomic assembly
Acosta, N. O., Mäkinen, V., & Tomescu, A. I. (2018) · Algorithms for Molecular Biology · doi:10.1186/s13015-018-0122-7 · Cited by 21
“Its most common mathematical formulations refer to an assembly (directed) graph built from the reads, such as a string graph [4, 5] or a de Bruijn graph [6, 7].”
BackgroundBuilding and Improving Reference Genome Assemblies
Steinberg, K. M., Schneider, V., Alkan, C., Montague, M. J., Warren, W. C., Church, D. M., & Wilson, R. K. (2017) · Proceedings of the IEEE · doi:10.1109/jproc.2016.2645402 · Cited by 20
“A secondary class of OLC-based assemblers use string graphs [18] The assembly problem on string graphs is formulated as minimum cost network flow problem [26].”
BackgroundFSG: Fast String Graph Construction for De Novo Assembly
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2017) · Journal of Computational Biology · doi:10.1089/cmb.2017.0089 · Cited by 16
“equivalent, to the one in [18] stated in [7] and which is quite useful when processing reads with their FM-index.”
BackgroundMethodInfluentialDinh, H., & Rajasekaran, S. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr321 · Cited by 16
“algorithm will be faster than the algorithms of [Gus97] and [OG10]. In the literature, exact-match overlap graphs should be distinguished from approximate-match overlap graphs which is considered in [Mye05], [MGMB07], [Pop09]. In the approximate-match overlap graph, there is an edge between two strings x and y if and…”
MethodCazaux, B., & Rivals, É. (2019) · Information Processing Letters · doi:10.1016/j.ipl.2019.105862 · Cited by 16
Discovering millions of plankton genomic markers from the Atlantic Ocean and the Mediterranean Sea
Arif, M., Gauthier, J., Sugier, K., Iudicone, D., Jaillon, O., Wincker, P., Peterlongo, P., & Madoui, M. (2018) · Molecular Ecology Resources · doi:10.1111/1755-0998.12985 · Cited by 19
“This step provides a way to remove non‐ coherent sequences (Myers, 2005) and to supply read coverage per variant and per input read set, whatever the number of input read set(s).”
BackgroundNew Generations: Sequencing Machines and Their Computational Challenges
Schwartz, D. C., & Waterman, M. S. (2010) · Journal of Computer Science and Technology · doi:10.1007/s11390-010-9300-x · Cited by 16
“Acknowledgement We are grateful to Frederick Sanger for his discoveries which laid the basis for knowing ourselves at the molecular level.”
BackgroundGeometric deep learning framework for de novo genome assembly
Vrček, L., Bresson, X., Laurent, T., Schmitz, M., Kawaguchi, K., & Šikić, M. (2024) · Genome Research · doi:10.1101/gr.279307.124 · Cited by 17
“Such a definition also ensures that the graph is directed instead of bidirected (Edmonds and Johnson 2003) as some representations are (Myers 2005), which would complicate training of the neural network.”
DIDA: Distributed Indexing Dispatched Alignment
Mohamadi, H., Vandervalk, B. P., Raymond, A., Jackman, S. D., Chu, J., Breshears, C. P., & Birol, İ. (2015) · PLoS ONE · doi:10.1371/journal.pone.0126409 · Cited by 15
Novo&Stitch: accurate reconciliation of genome assemblies via optical maps
Pan, W., Wanamaker, S. I., Ah‐Fong, A. M. V., Judelson, H. S., & Lonardi, S. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty255 · Cited by 16
“Assemblers for third generation sequencing data mainly use the overlap graph to store prefix-suffix overlaps between the long (noisy) reads in input (Hernandez et al. , 2008; Myers, 2005).”
BackgroundComputing the multi-string BWT and LCP array in external memory
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2020) · Theoretical Computer Science · doi:10.1016/j.tcs.2020.11.041 · Cited by 15
An update on bioinformatics resources for plant genomics research
Basantani, M. K., Gupta, D., Mehrotra, R., Mehrotra, S., Vaish, S., & Singh, A. (2017) · Current Plant Biology · doi:10.1016/j.cpb.2017.12.002 · Cited by 15
Comparative analysis of de novo assemblers for variation discovery in personal genomes
Tian, S., Yan, H., Klee, E. W., Kalmbach, M. T., & Slager, S. L. (2017) · Briefings in Bioinformatics · doi:10.1093/bib/bbx037 · Cited by 17
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.