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 301–400 of 437
GAMS: Genome Assembly on Multi-GPU Using String Graph
Jain, G., Rathore, L., & Paul, K. (2016) · 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-smartcity-dss.2016.0057 · Cited by 4
“To demonstrate the performance of SGA and its scalability on large genomes we performed assemblies on variety of genome sizes with different coverage.”
MethodAN EFFICIENT ALGORITHM FOR CHINESE POSTMAN WALK ON BI-DIRECTED DE BRUIJN GRAPHS
Kundeti, V. K., Rajasekaran, S., & Dinh, H. (2012) · Discrete Mathematics Algorithms and Applications · doi:10.1142/s179383091250019x · Cited by 3
Memory Efficient De Bruijn Graph ConstructionPreprint
Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., & Suri, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.3532 · Cited by 4
“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).”
MethodNext-generation nematode genomes
Kumar, S. (2013) · ERA · Cited by 4
Genomeless Genomics in Crop Improvement
Lim, K., Junttila, S., Fey, V., & Rudd, S. A. (2007) · Springer eBooks · doi:10.1007/978-1-4020-6295-7_7 · Cited by 4
“(Jaffe et al. 2003; Myers 2005; Myers et al. 2000; Myers et al. 2002) While approaches have been optimised to allow for assembly with significant repetitive content, the process is not trivial.”
BackgroundA New Lightweight Algorithm to compute the BWT and the LCP array of a Set of StringsPreprint
Bonizzoni, P., Vedova, G. D., Nicosia, S., Previtali, M., & Rizzi, R. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.08342 · Cited by 3
“l comparison among the input strings is needed, especially to nd all prex-sux matches (or overlaps) between reads in the context of the Overlap Layout Consensus (OLC) approach based on string graph [18]. This fact justies to search for extremely time and space ecient algorithms to compute the BWT on a collection of st…”
MethodMethods for De-novo Genome AssemblyPreprint
Bayat, A., Gamaarachchi, H., Deshpande, N., Wilkins, M. R., & Parameswaran, S. (2020) · Preprints.org · doi:10.20944/preprints202006.0324.v1 · Cited by 3
Kalyanaraman, A. (2011) · Springer eBooks · doi:10.1007/978-0-387-09766-4_402 · Cited by 4
A Novel Methodology for a Comprehensive Analysis of Genomic Sequence-to-Graph Alignment Tools
Coggi, M., Donato, G. W. D., & Santambrogio, M. D. (2025) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbbio.2024.3515469 · Cited by 3
“These include De Bruijn graphs [25], A-Bruijn graphs [26], and String graphs [27] for the assembly, Cactus graphs [28] for genomes comparison, and Enredo graphs [29] and Variation graphs [14] for the alignment.”
Devider: Long-Read Reconstruction of Many Diverse Haplotypes
Shaw, J., Boucher, C. A., Yu, Y. W., Noyes, N. R., & Li, H. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-90252-9_24 · Cited by 2
Zhang, F., Liao, X., Peng, S., Cui, Y., Wang, B., Zhu, X., & Liu, J. (2015) · Interdisciplinary Sciences Computational Life Sciences · doi:10.1007/s12539-015-0127-6 · Cited by 2
Binning metagenomic reads with probabilistic sequence signatures based on spaced seeds
Girotto, S., Comin, M., & Pizzi, C. (2017) · IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB) · doi:10.1109/cibcb.2017.8058538 · Cited by 2
“Ideally the overlap would be computed using a reads overlap graph [16], but this approach is highly demanding in terms of RAM.”
MethodBipartite graphs of small readability
Chikhi, R., Jovičić, V., Kratsch, S., Medvedev, P., Milanič, M., Raskhodnikova, S., & Varma, N. M. (2019) · Theoretical Computer Science · doi:10.1016/j.tcs.2019.07.022 · Cited by 2
Ugya, A. Y., & Meguellati, K. (2022) · Egyptian Journal of Basic and Applied Sciences · doi:10.1080/2314808x.2022.2082133 · Cited by 5
Finding Hamiltonian Cycles with Graph Neural Networks
Bosnić, F., & Šikić, M. (2023) · International symposium on image and signal processing and analysis/ISPA ... · doi:10.1109/ispa58351.2023.10278690 · Cited by 4
GeneTEK: Low-power and high-performance FPGA scalable architecture for exact unit-cost edit distance
Espinosa, E., Álvarez, R. R., Miranda, J., Larrosa, R., Peón-Quirós, M., Plata, Ó., & Atienza, D. (2026) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2026.111709 · Cited by 2
A CMOS architecture allowing parallel DNA comparison for on-chip assembly
Hu, Y., Liu, Y., Toumazou, C., & Georgiou, P. (2012) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2012.6271545 · Cited by 2
“A transitive reduction algorithm can be applied to reduce the graph to the minimum necessary elements, and it has a linear solution [14] implementable.”
MethodGenome Assembly on a Multicore System
Biswas, A. G., Ranjan, D., & Zubair, M. (2013) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom.2013.148 · Cited by 2
“The other genome assembly models include greedy algorithms [9], the de-Bruijn graph model [10] and the string graph model [11].”
MethodError Correction and Clustering Algorithms for Next Generation Sequencing
Yang, X. F. (2011) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdps.2011.387 · Cited by 2
Cautionary Tales of Inapproximability
Budden, D., & Jones, M. (2016) · Journal of Computational Biology · doi:10.1089/cmb.2016.0097 · Cited by 2
Algorithmic and computational comparison of metagenome assemblers
Sharma, A., Mishra, D. C., Budhlakoti, N., Rai, A. K., Lal, S. B., & KUMAR, S. (2020) · The Indian Journal of Agricultural Sciences · doi:10.56093/ijas.v90i5.104327 · Cited by 2
DRAGoM: Classification and Quantification of Noncoding RNA in Metagenomic Data
Liu, B., Thippabhotla, S., Zhang, J., & Zhong, C. (2021) · Frontiers in Genetics · doi:10.3389/fgene.2021.669495 · Cited by 2
“By hybrid assembly graph, we mean the assembly graph resulting from merging a string graph (Myers, 2005) and a de Bruijn graph (Idury and Waterman, 1995), the two main computational models used in sequence assembly.”
MethodZhong, H., Loukides, G., & Pissis, S. P. (2022) · Data & Knowledge Engineering · doi:10.1016/j.datak.2022.101981 · Cited by 2
“The goal is then to assemble these fragments into a candidate genome represented by some trail in the graph [9].”
BackgroundIdentifying Taxonomic Units in Metagenomic DNA Streams on Mobile Devices
Zheng, V., Sarıyüce, A. E., & Żola, J. (2022) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2022.3172661 · Cited by 2
“For example, in [24], Myers discusses DNA string graphs in which vertices represent prefixes and suffixes of reads, and edges represent non-matching substrings between two overlapping reads.”
Backgroundde Peer, Y. V. (2018) · Nature Plants · doi:10.1038/s41477-018-0293-8 · Cited by 2
Cairo, M., Khan, S., Rizzi, R., Schmidt, S., Tomescu, A. I., & Zirondelli, E. C. (2020) · arXiv (Cornell University) · Cited by 2
López‐Delgado, J., Carr, I., Paradiso, C., Gratton, P., Colosimo, G., van den Burg, M. P., Debrot, A. O., Sevilla, C. R., Isa, M. N. M., Bayliss, R. W., et al. (2025) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2025.04.13.648612 · Cited by 3
Chromosome-level genome assembly of the big-footed bat (Myotis pilosus)Preprint
Tian, S., Zhang, L., & Zhao, H. (2025) · Research Square · doi:10.21203/rs.3.rs-7561642/v1 · Cited by 2
A space efficient representation for sparse de Bruijn subgraphs
Quitzau, J. A. A., & Stoye, J. (2008) · PUB – Publications at Bielefeld University (Bielefeld University) · Cited by 3
Flowtigs: Safety in flow decompositions for assembly graphs
Sena, F., Eliel, I., Khan, S., Prjibelski, A. D., Schmidt, S., & Tomescu, A. I. (2024) · iScience · doi:10.1016/j.isci.2024.111208 · Cited by 1
“Metagenomic assemblers usually employ overlap graphs [34] or de Bruijn graphs [12], from which they compute unitigs [3, 8, 23, 24, 35] as maximal safe paths and then extend them using possibly unsafe heuristics.”
MethodSama: a contig assembler with correctness guarantee
Salmela, L. (2025) · Algorithms for Molecular Biology · doi:10.1186/s13015-025-00280-y · Cited by 1
“Med-vedev and Brudno [6] and Myers [7] have proposed to report the sequence with maximum likelihood given the reads as the assembled genome and Boža et al. [8] have developed a probabilistic framework to produce an assembly with high likelihood using simulated annealing.”
agtools : a software framework to manipulate assembly graphs
Mallawaarachchi, V., Bouras, G. S., Wick, R. R., Grigson, S. R., Papudeshi, B. N., & Edwards, R. A. (2026) · Bioinformatics Advances · doi:10.1093/bioadv/vbag126 · Cited by 1
“2001, Myers 2005, GFA Format Specification Working Group 2014, Nurk et al .”
DipGNNome: Diploid de Novo Genome Assembly with Geometric Deep Learning and Beam-Search
Schmitz, M., Vrček, L., Kawaguchi, K., & Šikić, M. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-26891-4_15 · Cited by 1
Moosman, O. W., Kelley, J. L., & Bogan, S. N. (2025) · Heredity · doi:10.1038/s41437-025-00803-8 · Cited by 1
From contiguity to accuracy: Validation-centered perspectives on bacterial genome assembly
Kim, M., Cho, Y., & Kim, O.-S. (2026) · The Journal of Microbiology · doi:10.71150/jm.2604004 · Cited by 1
“The overlap–layout–consensus (OLC) methods reconstruct genomes by identifying pairwise overlaps between reads and generating a consensus sequence, making them well suited for long-read data (Miller et al., 2010; Myers, 2005).”
Challenges in the detection and assembly of virus integration structures in human genomes
Deng, X., Du, X., Gensterblum‐Miller, E., Currie, J., Majchrowski, B. K., Lialios, P., Bhangale, A. D., Spector, M. E., Boyle, A. P., Brenner, J. C., et al. (2026) · Frontiers in Oncology · doi:10.3389/fonc.2026.1925720 · Cited by 1
“Instead, string graph formulations eliminate transitive edges and signi fi cantly reduce graph density while preserving assembly information, thereby improving scalability and repeat resolution (89, 90).”
Approaches and Challenges of Next-Generation Sequence Assembly Stages
El‐Metwally, S., Ouda, O. M., & Helmy, M. (2014) · SpringerBriefs in systems biology · doi:10.1007/978-1-4939-0715-1_9 · Cited by 1
Structural variation discovery: the easy, the hard and the ugly
Hormozdiari, F. (2011) · Summit (Simon Fraser University) · Cited by 1
Big data challenges for estimating genome assembler quality
Biswas, A. G., Gauthier, D. T., Ranjan, D., & Zubair, M. (2014) · ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB) · doi:10.1145/2649387.2660821 · Cited by 1
“A memory efficient representation of the OLC graph model uses string graphs [33].”
MethodKumari, P., Mazumder, R., Simonyan, V. V., & Krampis, K. (2015) · F1000Research · doi:10.12688/f1000research.6016.1 · Cited by 1
Learning pair-wise gene functional similarity by multiplex gene expression maps
An, L., Ling, H., Zoran Obradovic, A., Smith, D., & Megalooikonomou, V. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-s3-s1 · Cited by 1
Human Analysts at Superhuman Scales: What Has Friendly Software To Do?
Godzaridis, É., Boisvert, S., Xia, F., Kandel, M. E., Behling, S., Long, B., Sosa, C. P., Laviolette, F., & Corbeil, J. (2013) · Big Data · doi:10.1089/big.2013.0031 · Cited by 9
Effective Utilization of Paired Reads to Improve Length and Accuracy of Contigs in Genome Assembly
Nihalani, R., & Aluru, S. (2016) · ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB) · doi:10.1145/2975167.2975204 · Cited by 2
“String graphs [13] were used by SGA [18] to achieve memory efficiency and parallelizability in genome assembly.”
MethodParallel NGS Assembly Using Distributed Assembly Graphs Enriched with Biological Knowledge
Warnke-Sommer, J. D., & Ali, H. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.143 · Cited by 1
“String graphs [4] are an extension of the basic overlap graph formed by removing transitive edges and other redundant information.”
BackgroundMethodA new algorithm for de novo genome assembly
Haider, M. B. (2012) · Scholarship@Western (Western University) · Cited by 3
ArrOW: Experiencing a Parallel Cloud-Based De Novo Assembler Workflow
Ocaña, K., Guedes, T., & de Oliveira, D. (2019) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2019.00039 · Cited by 1
“Layout tries to generate unitigs (collections of reads assembled) [16].”
BackgroundMethodSOF: An Efficient String Graph Construction Algorithm
Morshed, M. S., & Yooseph, S. (2019) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm47256.2019.8983393 · Cited by 1
“An alternative approach for genome assembly, introduced by Myers [2], is based on the concept of a string graph which is constructed by removing transitive edges from the overlap graph.”
MethodA survey on de novo assembly methods for single‐molecular sequencing
Chen, Y., & Xiao, C. (2020) · Quantitative Biology · doi:10.1007/s40484-020-0214-5 · Cited by 1
HGGA: hierarchical guided genome assembler
Walve, R., & Salmela, L. (2022) · BMC Bioinformatics · doi:10.1186/s12859-022-04701-2 · Cited by 1
“The resulting graph is called the string graph [13].”
BackgroundHeuristics for the de Bruijn Graph Sequence Mapping Problem
Rocha, L. B., Adi, S. S., & Araújo, E. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-36805-9_11 · Cited by 1
Fernández, L. A., Martín-Mayor, V., & Yllanes, D. (2024) · Physical review. E · doi:10.1103/physreve.109.014133 · Cited by 3
“Alternative approaches to assembly have been proposed, for instance the string-graph representation [8], but this model has also been shown to be NP-hard, by reduction from the Hamiltonian-cycle problem [7].”
On the Coverage Required for Diploid Genome Assembly
Mahajan, D., Jain, C., & Kashyap, N. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619586 · Cited by 1
“All this machinery is required because of the fundamental barrier of long repeats in a genome that cannot be bridged by a single read.”
Practical Algorithms for Hierarchical Overlap Graphs
Talera, S., Bansal, P., Khan, S., & Khan, S. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-05228-5_21 · Cited by 1
Um algoritmo para a construção de vetores de sufixo generalizados em memória externa
da Louza, F. A. (2013) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/d.55.2013.tde-26032014-100626 · Cited by 1
Theoretical Bounds on Mate-Pair Information for Accurate Genome AssemblyPreprint
Lin, H. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.1653 · Cited by 1
“y still be ambiguous, as multiple solutions may yield the same optimal likelihood score. Alternate formulations of the assembly problem utilizing the concepts of overlap graphs [4, 11], string graphs [12], or de Bruijn graphs [13] can also be shown to be NP-hard [14, 15], or may not always yield the correct assembly.…”
BackgroundSolving repeat problems in shotgun sequencing
Arner, P. (2006) · Figshare · Cited by 2
Polymorphism and Genome Assembly
Donmez, N. (2012) · TSpace (University of Toronto) · Cited by 2
Statistical Methods for Genome Assembly
Bresler, M. (2014) · UC Berkeley · Cited by 1
Comprehensive sequencing of the genome and transcriptome of the Xishuangbanna game fowl
Qiu, H., Ning, T., Gong, W., Sun, H., Mu, G., & Li, J. (2024) · Scientific Data · doi:10.1038/s41597-024-04014-4 · Cited by 1
“Misalignments were filtered out, and local assembly was conducted to resolve false overlaps caused by repetitive sequences 14 .”
MethodComputer Architecture-Aware Optimisation of DNA Analysis Systems
Gamaarachchi, H. (2020) · arXiv (Cornell University) · doi:10.26190/unsworks/22238 · Cited by 1
Hash functions in nucleotide sequence analysisPreprint
Chen, K., Li, X., Shi, Q., Shao, M., & Medvedev, P. (2026) · Genome Research · doi:10.1101/gr.281453.125 · Cited by 1
“Anotherexampleistheconstructionof the overlap graph during genome assembly, where a critical step is identifying overlaps between long error-prone reads (Myers 2005).”
A Method for Reference-Free Genome Assembly Quality Assessment
Burkhart, J. G. (2013) · Scholars' Bank (University of Oregon)
Algorithms and Data Structures for Next‐Generation Sequences
Vezzi, F., Lancia, G., & Policriti, A. (2013) · Wiley eBooks · doi:10.1002/9781118617151.ch10
GPU based Eulerian Assembly of Genomes
Mahmood, S. F. (2013) · doi:10.13021/mars/4830
De Bruijn Graph-Based Whole-Genomic Sequence Assembly Algorithms and Applications
Kang, X., Tang, S., Ma, Y., Liu, R., & Wang, Y. (2013) · IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) · doi:10.1109/greencom-ithings-cpscom.2013.393
Laboratory Directed Research and Development Program FY 2005
Hansen, T. C. (2006) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.2172/882733
Dinh, H., & Rajasekaran, S. (2012) · IEEE International Conference on Computational Advances in Bio and Medical Sciences · doi:10.1109/iccabs.2012.6182668
“, [2] and [3]).”
A de novo assembly method for metagenomic DNA reads with mate pairs
Lai, B., Ding, R., & Zhu, H. (2011) · International Conference on Biomedical Engineering and Informatics (BMEI) · doi:10.1109/bmei.2011.6098547
Fundamental limits and insights: from wireless communication to DNA sequencing
Bresler, G. (2012) · eScholarship (California Digital Library)
Maretty, L., Sibbesen, J. A., & Krogh, A. (2014)
Statistical Models for Genome Assembly and Analysis
Rahman, A. H. (2015) · UC Berkeley
Constructing a genome assembly that has the maximum likelihoodPreprint
Ghodsi, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.4391
“(Or not!) The important point is to note that there is a subtle difference between this and the traditional path collapsing heuristic[3].”
BackgroundMethodReference Graph Construction and Merging for Human Genomic Sequences
Schiller, T. W. (2016) · Skemman
graphsAlgorithms for de novo short read assembly using de Bruijn
Zerbino, D. R., & Birney, E. (2010)
Tabrizi, M., & Sadat, N. (2015)
Clustering of Short Read Sequences for de novo Transcriptome Assembly
Saadat, S., Safikhani, Z., Badie, K., & Sadeghi, M. (2014) · مجله علوم دانشگاه تهران (منتشر نمی شود) · doi:10.22059/pbs.2014.50305
“Recent algorithms of genome assembly are mostly based on de Bruijn graphs (8-10).”
MethodAnnotation Pipelines for Next-Generation Sequencing Projects
Axelson-Fisk, M. (2015) · Computational biology · doi:10.1007/978-1-4471-6693-1_8
Efficient Algorithms for Prokaryotic Whole Genome Assembly and Finishing
Biswas, A. G. (2015) · ODU Digital Commons (Old Dominion University) · doi:10.25777/znmw-nt79
“A memory efficient representation of the OLC graph model uses string graphs (Myers, 2005).”
MethodAlgorithms for dna sequence assembly and motif search
Rajasekaran, S., & Dinh, H. (2012)
Computational methods for the analysis of next generation viral sequences
Lamzin, S. (2016) · UEA Digital Repository (University of East Anglia)
Assembly and Application to the Tomato Genome
Tang, J., Datema, E., Janssen, A., & van Ham, R. C. H. J. (2016) · Compendium of plant genomes · doi:10.1007/978-3-662-53389-5_8
The Contig Assembly Problem and Its Algorithmic Solutions
Jean, G., Radulescu, A., & Rusu, I. (2017) · Springer eBooks · doi:10.1007/978-3-319-59826-0_12
Algorithms for de novo genome assembly from third generation sequencing data
Sović, I. (2016) · Institutional Repository of the Ruđer Bošković Institute (Ruđer Bošković Institute)
Assemblage adaptatif de génomes et de méta-génomes par passage de messages
Boisvert, S. (2014) · Corpus Université Laval (Université Laval)
Safe solutions for walks on graphs
Acosta, N. O. (2018) · Työväentutkimus Vuosikirja
An integrated approach to comparative assembly
Healy, J., & Chambers, D. (2014) · Research@THEA
Algorithms for structural variation discovery using multiple sequence signatures
Söylev, A. (2018) · Bilkent University Institutional Repository (Bilkent University)
Holley, G. (2018) · PUB – Publications at Bielefeld University (Bielefeld University)
Repetitive DNA sequence assembly
Jiang, Y. (2018) · Figshare
Hari, R. (2017) · University of Malaya Students Repository
Identification Of Genetic Variation In Highly Divergent Regions Using Whole Exome Sequencing
Tian, S. (2016) · University of Minnesota Digital Conservancy (University of Minnesota)
Efficient String Graph Construction Algorithm
Morshed, M. S. (2019) · Journal of International Crisis and Risk Communication Research
Bipartite Graphs of Small Readability
Chikhi, R., Jovičić, V., Kratsch, S., Medvedev, P., Milanič, M., Raskhodnikova, S., & Varma, N. M. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-94776-1_39
Fuzzy k-mers and their application to comparative genome assembly
Healy, J. (2013) · Arrow@dit (Dublin Institute of Technology) · doi:10.13025/17203
PMSGA: A FAST DNA FRAGMENT ASSEMBLER
Mäkinen, J., Tarhio, J., & Khuri, S. (2010) · International Conference on Bioinformatics · doi:10.5220/0002580800770082
“Another option would be to let the researcher manually perform additional tests to decide the final path in the graph, as suggested by Myers (2005).”
BackgroundMethodInfluentialSalzberg, S. L. (2008) · Faculty Opinions – Post-Publication Peer Review of the Biomedical Literature · doi:10.3410/f.1115043.571013
Guigó, R. (2018) · Faculty Opinions – Post-Publication Peer Review of the Biomedical Literature · doi:10.3410/f.726853154.793554179
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.