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 201–300 of 437
Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time
Cairo, M., Rizzi, R., Tomescu, A. I., & Zirondelli, E. C. (2023) · ACM Transactions on Algorithms · doi:10.1145/3632176 · Cited by 15
“They start by building an assembly graph encoding the overlaps of the reads, such as a de Bruijn graph [52] or an overlap graph [47] (graphs are directed in this paper).”
BackgroundPASQUAL: Parallel Techniques for Next Generation Genome Sequence Assembly
Liu, X., Pande, P. R., Meyerhenke, H., & Bader, D. A. (2012) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2012.190 · Cited by 16
“With the index we can search for overlaps between reads and construct a string graph [19] to store these overlaps.”
BackgroundMethodLSG: An External-Memory Tool to Compute String Graphs for Next-Generation Sequencing Data Assembly
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2016) · Journal of Computational Biology · doi:10.1089/cmb.2015.0172 · Cited by 14
“Alternative approaches have been developed recently, mostly based on the idea of string graph , initially proposed by Myers (2005) before the advent of NGS technologies and further developed by Simpson and Durbin (2010, 2012) to incorporate some advances in text indexing, such as the FM-index…”
InfluentialGPU-Euler: Sequence Assembly Using GPGPU
Mahmood, S. F., & Rangwala, H. (2011) · IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS) · doi:10.1109/hpcc.2011.29 · Cited by 17
“Examples include, greedy approaches like VCAKE [1], graph oriented approach that find Eulerian tours [2], and bidirected string graph representations [3].”
MethodPartial DNA assembly: A rate-distortion perspective
Shomorony, I., Kamath, G. M., Xia, F., Courtade, T. A., & Tse, D. N. C. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541609 · Cited by 16
“, string graphs [8]) are better suited to long-read, high-error sequencing.”
BackgroundPrjibelski, A. D., Korobeynikov, A., & Lapidus, A. L. (2018) · Elsevier eBooks · doi:10.1016/b978-0-12-809633-8.20106-4 · Cited by 15
A fast algorithm for the all-pairs suffix–prefix problem
Lim, J., & Park, K. (2017) · Theoretical Computer Science · doi:10.1016/j.tcs.2017.07.013 · Cited by 13
Integration of string and de Bruijn graphs for genome assembly
Huang, Y., & Liao, C.-F. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw011 · Cited by 13
GPU-Accelerated Large-Scale Genome Assembly
Goswami, S. C., Lee, K., Shams, S., & Park, S. (2018) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2018.00091 · Cited by 15
“De novo assembly is performed using either a de Bruijn graph-based approach [17] or a string graph-based approach [18].”
MethodChromosome-level genome assembly of the cashmere goat
Wang, Z., Lv, Q., Li, W., Huang, W., Gong, G., Yan, X., Liu, B., Chen, O., Wang, N., Zhang, Y., et al. (2024) · Scientific Data · doi:10.1038/s41597-024-03932-7 · Cited by 13
“This local assembly strategy can effectively circumvent the false overlap relationships that may be induced by the genome’s repetitive sequences during the construction of the string graph in the assembly process 24 .”
BackgroundChang, Y.-J., Chen, C.-C., Ho, J.-M., & Chen, C.-L. (2012) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud.2012.123 · Cited by 12
GAML: genome assembly by maximum likelihood
Boža, V., Brejová, B., & Vinař, T. (2015) · Algorithms for Molecular Biology · doi:10.1186/s13015-015-0052-6 · Cited by 12
ScaffoldScaffolder: solving contig orientation via bidirected to directed graph reduction
Bodily, P., Fujimoto, M., Snell, Q. O., Ventura, D. A., & Clement, M. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv548 · Cited by 12
Carletti, V., Foggia, P., Garrison, E. P., Greco, L., Ritrovato, P., & Vento, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-20081-7_23 · Cited by 14
Coverage-preserving sparsification of overlap graphs for long-read assembly
Jain, C. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad124 · Cited by 12
“Edge uv l , i.e. the edge from vertex u to vertex v of weight l can be safely removed from graph O 0 L EMMA 7 (Myers 2005).”
BackgroundMethodInfluentialHaplotype-resolved assembly of diploid and polyploid genomes using quantum computing
Chen, Y., Huang, J.-H., Sun, Y., Zhang, Y., Li, Y., & Xu, X. (2024) · Cell Reports Methods · doi:10.1016/j.crmeth.2024.100754 · Cited by 11
“Moreover, the string graph, an advanced OLC variant, 11 simplifies the overlap graph and enhances efficiency in managing complex regions with repetitive sequences.”
Arapan-S: a fast and highly accurate whole-genome assembly software for viruses and small genomes
Sahli, M., & Shibuya, T. (2012) · BMC Research Notes · doi:10.1186/1756-0500-5-243 · Cited by 12
“It was the pillar of the first assemblers that appeared on the market, such as: TIGR [1], CAP3 [2], PCAP [3], the string graph of Myers [4] and MIRA [5].”
MethodMetagenome SNP calling via read-colored de Bruijn graphs
Alipanahi, B., Muggli, M. D., Jundi, M. A., Noyes, N. R., & Boucher, C. A. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa081 · Cited by 11
“As we previously discussed, de Bruijn graph approaches for SNP calling lose read information when the reads are fragmented into k - mers, which introduces the possibility of the sequences containing the SNP not being read coherent (Myers, 2005).”
BackgroundGraphBin2: Refined and Overlapped Binning of Metagenomic Contigs Using Assembly Graphs
Mallawaarachchi, V., Wickramarachchi, A., & Lin, Y. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.wabi.2020.8 · Cited by 14
“There are two dominant paradigms for genome assembly: overlap-layout-consensus (or string graphs) [21] and de Bruijn graphs [24].”
BackgroundMethodCartney, A. M. M., Hilario, E., Choi, S., Guhlin, J. G., Prebble, J. M., Houliston, G. J., Buckley, T. R., & Chagné, D. (2021) · Molecular Ecology Resources · doi:10.1111/1755-0998.13406 · Cited by 13
BASE: a practical de novo assembler for large genomes using long NGS reads
Liu, B., Liu, C.-M., Li, D., Li, Y., Ting, H., Yiu, S., Luo, R., & Lam, T. (2016) · BMC Genomics · doi:10.1186/s12864-016-2829-5 · Cited by 11
“An alternative representation named string graph was proposed by Mayer a decade ago [6], which has been implemented in assemblers such as SGA [7], Fermi [8], and Readjoiner [9].”
MethodTelomere-to-telomere assembly by preserving contained readsPreprint
Kamath, S. S., Bindra, M., Pal, D., & Jain, C. (2024) · Genome Research · doi:10.1101/gr.279311.124 · Cited by 13
Pu, L., & Shamir, R. (2022) · Bioinformatics · doi:10.1093/bioinformatics/btac468 · Cited by 11
An External-Memory Algorithm for String Graph Construction
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2016) · Algorithmica · doi:10.1007/s00453-016-0165-4 · Cited by 11
“The original definition of overlap graph [26] differs from ours since the label of the arc (ri , r j ) consists of the right extension r xi, j instead of the left extension lxi, j .”
BackgroundMethodInfluentialBayesian Genome Assembly and Assessment by Markov Chain Monte Carlo Sampling
Howison, M., Zapata, F., Edwards, E. J., & Dunn, C. W. (2014) · PLoS ONE · doi:10.1371/journal.pone.0099497 · Cited by 11
Overlap-based genome assembly from variable-length reads
Hui, J., Shomorony, I., Ramchandran, K., & Courtade, T. A. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541453 · Cited by 11
“Motivated by this nearcharacterization of the information limits for perfect assembly and the advantages of overlap-based assembly for long-read technologies, we describe an overlap-based algorithm with the same performance guarantees.”
MethodPositional bias in variant calls against draft reference assemblies
Briskine, R. V., & Shimizu, K. K. (2017) · BMC Genomics · doi:10.1186/s12864-017-3637-2 · Cited by 10
Long-read reconstruction of many diverse haplotypes with devider
Shaw, J., Boucher, C. A., Yu, Y. W., Noyes, N. R., & Li, H. (2025) · Genome Research · doi:10.1101/gr.280510.125 · Cited by 11
“1B, bottom) (Myers 2005).”
Lam, K.-K., Hall, R. J., Clum, A., & Rao, S. B. (2016) · BMC Bioinformatics · doi:10.1186/s12859-016-1288-y · Cited by 9
“Contig-read string graph is a string graph [10] with both the contigs and the reads associated with their endpoints as nodes.”
BackgroundMethodOn Algorithmic Complexity of Biomolecular Sequence Assembly Problem
Narzisi, G., Mishra, B., & Schatz, M. C. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-07953-0_15 · Cited by 9
“The string graph is a particular graph where all the contained string and transitively inferable edges are removed [17].”
BackgroundMethodResultInfluentialZhao, P., Xin, G., Yan, F., Wang, H., Ren, X., Woeste, K., & Liu, W. (2020) · Horticulture Research · doi:10.1038/s41438-020-00414-w · Cited by 9
SAGE: String-overlap Assembly of GEnomes
Ilie, L., Haider, B., Molnar, M., & Solis-Oba, R. (2014) · BMC Bioinformatics · doi:10.1186/1471-2105-15-302 · Cited by 13
“For m = 1, this log-odds ratio gives the A-statistics of Myers [20].”
BackgroundMethodInfluentialAccurate haplotype-resolved assembly reveals the origin of structural variants for human trios
Xu, M., Guo, L., Du, X., Li, L., Peters, B. A., Deng, L., Wang, O., Chen, F., Wang, J., Jiang, Z., et al. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab068 · Cited by 9
“One solution to this problem would be to de novo assemble the complete sequence of each haplotype (Myers, 2005).”
BackgroundWhole-Genome Sequencing for Rapid and Accurate Identification of Bacterial Transmission Pathways
Harris, S. R., & Okoro, C. K. (2014) · Methods in microbiology · doi:10.1016/bs.mim.2014.07.003 · Cited by 9
Parallel methods for short read assembly
Jackson, B. G. (2009) · Iowa State University Digital Repository (Iowa State University) · doi:10.31274/etd-180810-1382 · Cited by 19
“17 Both Myers and Medvedev et al. propose that the assembly should be a tour of the overlap string graph that conforms to some traversal constraints.”
BackgroundMethodInfluentialLJA: Assembling Long and Accurate Reads Using Multiplex de Bruijn GraphsPreprint
Bankevich, A., Bzikadze, A. V., Kolmogorov, M., Antipov, D., & Pevzner, P. A. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.12.10.420448 · Cited by 10
“…2008, Simpson et al., 2009, Peng et al., 2010, Bankevich et al., 2012), the problem of constructing large de Bruijn graphs remains open and the existing HiFi assemblers HiCanu (Nurk et al., 2020) and hifiasm (Cheng et al., 2021) are based on the alternative string graph approach (Myers, 2005).”
BackgroundAn improved maximum likelihood formulation for accurate genome assembly
Varma, A. P., Ranade, A., & Aluru, S. (2011) · IEEE International Conference on Computational Advances in Bio and Medical Sciences · doi:10.1109/iccabs.2011.5729873 · Cited by 11
“However, it has not seen much use in large genome sequencing efforts primarily due to its memory-intensive nature.”
BackgroundMethodInfluentialSuperbubbles, Ultrabubbles and Cacti
Paten, B., Novak, A. M., Garrison, E. P., & Hickey, G. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56970-3_11 · Cited by 8
Fast Short Read De-Novo Assembly Using Overlap-Layout-Consensus Approach
Bayat, A., Deshpande, N., Wilkins, M. R., & Parameswaran, S. (2018) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2018.2875479 · Cited by 9
“Thus,Miniasm constructs the graph and removes transitive edges after the graph has been constructed using the method proposed in [18].”
MethodInformatics for PacBio Long Reads
Suzuki, Y. (2019) · Advances in experimental medicine and biology · doi:10.1007/978-981-13-6037-4_8 · Cited by 8
Improving the sensitivity of long read overlap detection using grouped short k-mer matches
Du, N., Chen, J., & Sun, Y. (2019) · BMC Genomics · doi:10.1186/s12864-019-5475-x · Cited by 8
“However, the two figures are generated using overlaps between two adjacent reads, which define an “irreducible” edge [27] in an overlap graph.”
BackgroundOn the complexity of approximately matching a string to a directed graph
Dondi, R., Mauri, G., & Zoppis, I. F. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104748 · Cited by 8
Assembly of Large Genomes from Paired Short Reads
Jackson, B. G., Schnable, P. S., & Aluru, S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00727-9_5 · Cited by 10
“The result of this process is a bidirected string graph [ 15 ].”
BackgroundMethodA Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
Park, S., Park, S. G., Cazaux, B., Park, K., & Rivals, É. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.cpm.2021.22 · Cited by 11
The Hydrostructure: a Universal Framework for Safe and Complete Algorithms for Genome AssemblyPreprint
Cairo, M., Khan, S., Rizzi, R., Schmidt, S., Tomescu, A. I., & Zirondelli, E. C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.12635 · Cited by 10
“…[49], whose formulations range from a shortest common superstring of the reads [49, 30, 29], to various models of node-or arc-covering walks in different assembly graphs , encoding the overlaps between the reads (such as de Bruijn graphs [50], or overlap graphs [43]) [51, 41, 42, 28, 26, 46, 44].”
BackgroundGenome assembly with variable order de Bruijn graphsPreprint
Diaz-Domínguez, D., Martinello, P., Onodera, T., Puglisi, S. J., & Salmela, L. (2022) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2022.09.06.506758 · Cited by 9
Eizenga, J. M., Lorig-Roach, R., Meredith, M., & Paten, B. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-80049-9_15 · Cited by 8
Benchmarking multi-platform sequencing technologies for human genome assembly
Wang, J., Veldsman, W. P., Fang, X., Huang, Y., Xie, X., Lü, A., & Zhang, L. (2023) · Briefings in Bioinformatics · doi:10.1093/bib/bbad300 · Cited by 7
RGFA: powerful and convenient handling of assembly graphs
Gonnella, G., & Kurtz, S. (2016) · PeerJ · doi:10.7717/peerj.2681 · Cited by 7
Zhong, C., Yang, Y., & Yooseph, S. (2019) · BMC Bioinformatics · doi:10.1186/s12859-019-2818-1 · Cited by 7
Graph mining for next generation sequencing: leveraging the assembly graph for biological insights
Warnke-Sommer, J. D., & Ali, H. (2016) · BMC Genomics · doi:10.1186/s12864-016-2678-2 · Cited by 9
“The subgraph is then transitively reduced following the approach in [16].”
BackgroundMethodGraph analysis of fragmented long-read bacterial genome assemblies
Marijon, P., Chikhi, R., & Varré, J. (2019) · Bioinformatics · doi:10.1093/bioinformatics/btz219 · Cited by 7
Resistome SNP Calling via Read Colored de Bruijn GraphsPreprint
Alipanahi, B., Muggli, M. D., Jundi, M. A., Noyes, N. R., & Boucher, C. A. (2017) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/156174 · Cited by 7
“Sequences and variants assembled from such graphs are composed and supported from collections of reads, rather than k-mers—an attribute of overlap graphs known as read coherence [33].”
BackgroundSteyaert, A., Audenaert, P., & Fostier, J. (2020) · BMC Bioinformatics · doi:10.1186/s12859-020-03740-x · Cited by 6
Constructing String Graphs in External Memory
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44753-6_23 · Cited by 6
“The resulting graph is called string graph [9].”
BackgroundMethodInfluentialInferring the global structure of chromosomes from structural variations
Yasuda, T., & Miyano, S. (2015) · BMC Genomics · doi:10.1186/1471-2164-16-s2-s13 · Cited by 6
“[18] used alternating paths, their formulation can be represented by using a bidirected graph whose edges have directions at both ends [19,32].”
MethodA comprehensive review of the de Bruijn graph and its interdisciplinary applications in computing
Huang, S., Hang, H., & Bao, E. (2023) · Engineered Science · doi:10.30919/es1061 · Cited by 8
An Efficient Algorithm for Chinese Postman Walk on Bi-directed de Bruijn Graphs
Kundeti, V., Rajasekaran, S., & Dinh, H. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17458-2_16 · Cited by 11
“Directed de Bruijn graph based sequence assembly algorithms such as [3] and [4] seem to handle these short read data efficiently compared to the string graph based algorithms (see e.g., [5]).”
BackgroundPaKman: Scalable Assembly of Large Genomes on Distributed Memory Machines
Ghosh, P., Krishnamoorthy, S., & Kalyanaraman, A. (2019) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2019.00067 · Cited by 9
“For this reason, our PaK-Graph can be viewed as an enhanced version of the string graph data structure originally introduced by Myers [6].”
MethodCerulean: A hybrid assembly using high throughput short and long readsPreprint
Deshpande, V., Fung, E. D. K., Pham, S., & Bafna, V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.7933 · Cited by 10
“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…”
MethodAssembly of repetitive regions using next-generation sequencing dataPreprint
Nowak, R. M. (2016) · Cited by 6
Rawsamble: overlapping raw nanopore signals using a hash-based seeding mechanism
Fırtına, C., Mordig, M., Mustafa, H., Goswami, S., Ghiasi, N. M., Mercogliano, S., Eris, F., Lindegger, J., Kahles, A., & Mutlu, O. (2026) · Bioinformatics · doi:10.1093/bioinformatics/btag087 · Cited by 6
“It should be noted that the golden standard assembly for D4 E.coli dataset was limited in terms of assembly coverage, using --asm-coverage 50 , as Flye raised an error regarding an otherwise too high coverage level.”
On the Readability of Overlap Digraphs
Chikhi, R., Medvedev, P., Milanič, M., & Raskhodnikova, S. (2015) · Discrete Applied Mathematics · doi:10.1016/j.dam.2015.12.009 · Cited by 5
Using the Sadakane Compressed Suffix Tree to Solve the All-Pairs Suffix-Prefix Problem
Rachid, M. H., Malluhi, Q. M., & Abouelhoda, M. I. (2014) · BioMed Research International · doi:10.1155/2014/745298 · Cited by 5
“We also investigated the space and time consumed in the overlap stage of a recent string graph-based sequence assembler called SGA [15].”
Assembly of repetitive regions using next-generation sequencing data
Nowak, R. M. (2015) · Journal of Applied Biomedicine · doi:10.1016/j.bbe.2014.12.001 · Cited by 5
“Computer programs use the de Bruijn graphs [3; 4] as well as greedy extensions of overlap-consensus-layout graphs [5] to process the volume of data.”
MethodDivide and Conquer Computation of the Multi-string BWT and LCP Array
Bonizzoni, P., Vedova, G. D., Nicosia, S., Pirola, Y., Previtali, M., & Rizzi, R. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-94418-0_11 · Cited by 5
Duitama, J. (2022) · Methods in molecular biology · doi:10.1007/978-1-0716-2819-5_16 · Cited by 6
Zhang, S., Chen, J., Zhang, C., Zhang, S., Zhang, X., Gao, L., & Yang, W. (2023) · Genomics · doi:10.1016/j.ygeno.2023.110617 · Cited by 5
The Progression in Developing Genomic Resources for Crop Improvement
Ruperao, P., Rangan, P., Shah, T. M., Thakur, V., Kalia, S., Mayes, S., & Rathore, A. (2023) · Life · doi:10.3390/life13081668 · Cited by 6
“…assemblers were developed based on overlap–layout–consensus These assemblers were developed based on overlap–lay-out–consensus on an overlap graph [120] in which the nodes were the reads and the edges represented the shared sequence between reads. an overlap graph [120] in which the nodes were…”
BackgroundMethodSafely Filling Gaps with Partial Solutions Common to All Solutions
Salmela, L., & Tomescu, A. I. (2018) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2017.2785831 · Cited by 6
PaKman: A Scalable Algorithm for Generating Genomic Contigs on Distributed Memory Machines
Ghosh, P., Krishnamoorthy, S., & Kalyanaraman, A. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.3043241 · Cited by 8
“For this reason, our PaK-Graph can be viewed as an enhanced version of the string graph data structure originally introduced by Myers [7].”
MethodLazyB: fast and cheap genome assembly
Gatter, T., von Löhneysen, S., Fallmann, J., Drozdova, P. B., Hartmann, T., & Stadler, P. F. (2021) · Algorithms for Molecular Biology · doi:10.1186/s13015-021-00186-5 · Cited by 5
ViQUF: De Novo Viral Quasispecies Reconstruction Using Unitig-Based Flow Networks
Freire, B., Ladra, S., Paramá, J. R., & Salmela, L. (2022) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2022.3190282 · Cited by 5
“Pevzner et al. [14] and Myers [15] first suggested using network flows to solve genome assembly.”
BackgroundMethodDetecting Repeat Families in Incompletely Sequenced Genomes
Quitzau, J. A. A., & Stoye, J. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87361-7_29 · Cited by 5
Aligning Sequences by Minimum Description Length
Conery, J. S. (2007) · EURASIP Journal on Bioinformatics and Systems Biology · doi:10.1155/2007/72936 · Cited by 5
“…variety of applications ranging from genome assembly, which requires exact or nearly exact matches between ends of small fragments of DNA sequences [1], to homology search in sequence databases, which involves pairwise local alignment of DNA or protein sequences [2], to phylogenetic inference and…”
BackgroundA space-efficient solution to find the maximum overlap using a compressed suffix array
Rachid, M. H., Malluhi, Q. M., & Abouelhoda, M. I. (2014) · Middle East Conference on Biomedical Engineering · doi:10.1109/mecbme.2014.6783270 · Cited by 5
An Algorithm to Build a Multi-genome ReferencePreprint
Rabbani, L., Müller, J., & Weigel, D. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.04.11.036871 · Cited by 8
Optimal Construction of Hierarchical Overlap Graphs
Khan, S. (2021) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.cpm.2021.17 · Cited by 5
Genome sequence assembly evaluation using long-range sequencing dataPreprint
Guan, D., McCarthy, S., Wood, J. M. D., Sims, Y., Chow, W., Ning, Z., Howe, K., Wang, G., Wang, Y., & Durbin, R. M. (2022) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2022.05.10.491304 · Cited by 5
“This has stimulated the development of new genome assembly tools such as Falcon [4], which is a string graph-based assembler[5], and Canu [6], an overlap graph-based assembly tool.”
MethodEfficient Restricted‐Case Algorithms for Problems in Computational Biology
Evans, P., & Wareham, H. T. (2010) · Wiley eBooks · doi:10.1002/9780470892107.ch2 · Cited by 4
Tørresen, O. K., Star, B., Jentoft, S., Jakobsen, K. S., & Nederbragt, A. J. (2016) · Elsevier eBooks · doi:10.1016/b978-0-12-801418-9.00001-9 · Cited by 4
Using Apache Spark on genome assembly for scalable overlap-graph reduction
Paul, A. J., Lawrence, D., Song, M., Lim, S., Pan, C., & Ahn, T.-H. (2019) · Human Genomics · doi:10.1186/s40246-019-0227-1 · Cited by 4
“The general transitive edge reduction algorithm takes O ( ED ) time where E is the number of edges and D is the maximum out degree for the read, but Myer proposed a linear O ( E ) expected time transitive reduction algorithm shown in Algorithm 1 [25].”
MethodSuffix-Prefix Queries on a Dictionary
Loukides, G., Pissis, S. P., Thankachan, S. V., & Zuba, W. (2023) · HAL · doi:10.4230/lipics.cpm.2023.21 · Cited by 4
“APSP finds numerous applications in bioinformatics because it is the first step in sequence assembly [26, 37, 46, 8, 11].”
BackgroundTick genomics through a Nanopore: a low-cost approach for tick genomics
Meiring, C., Eygelaar, M., Fourie, J., & Labuschagné, M. (2025) · BMC Genomics · doi:10.1186/s12864-025-11733-4 · Cited by 4
GAML: Genome Assembly by Maximum Likelihood
Boža, V., Brejová, B., & Vinař, T. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44753-6_10 · Cited by 4
Zhong, C., Yang, Y., & Yooseph, S. (2016) · BMC Bioinformatics · doi:10.1186/s12859-016-1119-1 · Cited by 4
“…of GRASP shares conceptual similarities with sequence overlap-based approaches (e.g. using data structures such as overlap-graph [16], string graph [17], or de bruijn graph [18]), except that the graph is not explicitly built in GRASP but that the overlap information is resolved through…”
BackgroundComplexity Issues of String to Graph Approximate Matching
Dondi, R., Mauri, G., & Zoppis, I. F. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-40608-0_17 · Cited by 4
“Indeed in computational biology a representation of variants of related sequences is often provided by a labeled graph [11,17] and the query of a string in a labeled graph has found application in computational pan-genomics [13,18].”
BackgroundEfficient Construction of Hierarchical Overlap Graphs
Park, S. G., Cazaux, B., Park, K., & Rivals, É. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-59212-7_20 · Cited by 4
“The development of DNA sequencing goes along with several proposals of overlap encoding graphs, usually classified into two categories of digraphs: – Overlap Graph [25] and its variants (like String Graph [22]), in which each input read is a node and an arc connecting a pair of reads represents the longest overlap bet…”
BackgroundPaul, A. J., Lawrence, D., Song, M., Lim, S., Pan, C., & Ahn, T.-H. (2018) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm.2018.8621546 · Cited by 4
“The DERCEC algorithm completed the reduction of the graph using 5 cluster nodes in 1.35 hours, while fast completing with 15 cluster nodes in 0.4 hours.”
MethodInfluentialLOGAN: A framework for LOssless Graph-based ANalysis of high throughput sequence dataPreprint
Bolger, A., Denton, A. K., Bolger, M., & Usadel, B. (2017) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/175976 · Cited by 5
Warnke-Sommer, J. D., Pawaskar, S., & Ali, H. (2012) · International Conference on High Performance Computing & Simulation (HPCS) · doi:10.1109/hpcsim.2012.6266905 · Cited by 3
“The second step maps each read that forms a containment overlap with one or more other reads to a suitable representative read following a hierarchical clustering scheme introduced by CD-Hit [13].”
Genome Assembler for Repetitive Sequences
Nowak, R. M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31196-3_42 · Cited by 3
A Real-Time de novo DNA Sequencing Assembly Platform Based on an FPGA Implementation
Hu, Y., & Georgiou, P. (2015) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2015.2442974 · Cited by 6
Graph Theoretical Strategies in De Novo Assembly
Behizadi, K., Jafarzadeh, N., & Iranmanesh, A. (2022) · IEEE Access · doi:10.1109/access.2022.3144113 · Cited by 4
“The string graph proposed by Myers et al. [29] is built by constructing a graph of the pairwise overlaps between sequence reads and transforming it into a string graph by removing transitive edges [30].”
MethodApproximate Suffix-Prefix Dictionary Queries
Zuba, W., Loukides, G., Pissis, S. P., & Thankachan, S. V. (2024) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.4230/lipics.mfcs.2024.85 · Cited by 3
“APSP is a classic problem in string algorithms [18] with numerous applications in sequence assembly [18, 26, 31, 7, 10].”
BackgroundLIPIcs, Volume 259, CPM 2023, Complete Volume
Bulteau, L., & Lipták, Z. (2023) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.cpm.2023 · Cited by 3
A Graph Theoretical Approach to DNA Fragment Assembly
Kaptcianos, J. (2008) · American Journal of Undergraduate Research · doi:10.33697/ajur.2008.008 · Cited by 5
“This includes, but is certainly not limited to, the following articles: Alekseyev and Pevzner [20], Myers [21], and Raphael, Zhi, Tang, and Pevzner [22].”
BackgroundFSG: Fast String Graph Construction for De Novo Assembly of Reads Data
Bonizzoni, P., Vedova, G. D., Pirola, Y., Previtali, M., & Rizzi, R. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-38782-6_3 · Cited by 3
Assembly Algorithms for Deep Sequencing Data: Basics and Pitfalls
Kol, N., & Shomron, N. (2013) · Methods in molecular biology · doi:10.1007/978-1-62703-514-9_5 · Cited by 3
Detecting and Analyzing Genomic Structural Variation Using Distributed Computing
Whelan, C. W. (2014) · doi:10.6083/m43x85c3 · Cited by 3
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.