The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Efficient construction of an assembly string graph using the FM-index
Open accessAbstract
Motivation: Sequence assembly is a difficult problem whose importance has grown again recently as the cost of sequencing has dramatically dropped. Most new sequence assembly software has started by building a de Bruijn graph, avoiding the overlap-based methods used previously because of the computational cost and complexity of these with very large numbers of short reads. Here, we show how to use suffix array-based methods that have formed the basis of recent very fast sequence mapping algorithms to find overlaps and generate assembly string graphs asymptotically faster than previously described algorithms. Results: Standard overlap assembly methods have time complexity O(N2), where N is the sum of the lengths of the reads. We use the Ferragina–Manzini index (FM-index) derived from the Burrows–Wheeler transform to find overlaps of length at least τ among a set of reads. As well as an approach that finds all overlaps then implements transitive reduction to produce a string graph, we show how to output directly only the irreducible overlaps, significantly shrinking memory requirements and reducing compute time to O(N), independent of depth. Overlap-based assembly methods naturally handle mixed length read sets, including capillary reads or long reads promised by the third generation sequencing technologies. The algorithms we present here pave the way for overlap-based assembly approaches to be developed that scale to whole vertebrate genome de novo assembly. Contact: js18@sanger.ac.uk
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
Self-citationUltrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-3-r25 · Cited by 21,849
Fast and accurate long-read alignment with Burrows-Wheeler transform.
Li, H., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp698 · Cited by 12,063
Self-citationVelvet: Algorithms for de novo short read assembly using de Bruijn graphs
Zerbino, D. R., & Birney, E. (2008) · Genome Research · doi:10.1101/gr.074492.107 · Cited by 9,491
SOAP2: an improved ultrafast tool for short read alignment
Li, R., Yu, C., Li, Y., Lam, T.-W., Yiu, S.-M., Kristiansen, K., & Wang, J. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp336 · Cited by 3,760
ABySS: A parallel assembler for short read sequence data
Simpson, J. T., Wong, K., Jackman, S. D., Schein, J. E., Jones, S. J. M., & Birol, İ. (2009) · Genome Research · doi:10.1101/gr.089532.108 · Cited by 3,608
Self-citationAlgorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
Gusfield, D. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511574931 · Cited by 3,078
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
An 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
Opportunistic data structures with applications
Ferragina, P., & Manzini, G. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892127 · Cited by 1,063
Cited by
An integrated map of genetic variation from 1,092 human genomes
The 1000 Genomes Project Consortium (2012) · Nature · doi:10.1038/nature11632 · Cited by 7,711
WGS500 Consortium, Rimmer, A., Phan, H., Mathieson, I., Iqbal, Z., Twigg, S. R. F., Wilkie, A. O. M., McVean, G., & Lunter, G. (2014) · Nature Genetics · doi:10.1038/ng.3036 · Cited by 1,057
Efficient de novo assembly of large genomes using compressed data structures
Simpson, J. T., & Durbin, R. (2012) · Genome Research · doi:10.1101/gr.126953.111 · Cited by 768
Self-citationDe novo assembly and genotyping of variants using colored de Bruijn graphs
Iqbal, Z., Caccamo, M., Turner, I., Flicek, P., & McVean, G. (2012) · Nature Genetics · doi:10.1038/ng.1028 · Cited by 634
Analysis of RNA-Seq Data Using TopHat and Cufflinks
Ghosh, S., & Chan, C.-K. K. (2016) · Methods in Molecular Biology · doi:10.1007/978-1-4939-3167-5_18 · Cited by 593
Assemblathon 1: A competitive assessment of de novo short read assembly methods
Earl, D., Bradnam, K., St. John, J., Darling, A., Lin, D., Fass, J., Yu, H. O. K., Buffalo, V., Zerbino, D. R., Diekhans, M., et al. (2011) · Genome Research · doi:10.1101/gr.126599.111 · Cited by 507
Self-citationOak genome reveals facets of long lifespan
Plomion, C., Aury, J.-M., Amselem, J., Leroy, T., Murat, F., Duplessis, S., Faye, S., Francillonne, N., Labadie, K., Le Provost, G., et al. (2018) · Nature Plants · doi:10.1038/s41477-018-0172-3 · Cited by 446
An Integrated Pipeline for de Novo Assembly of Microbial Genomes
Tritt, A., Eisen, J. A., Facciotti, M. T., & Darling, A. E. (2012) · PLoS ONE · doi:10.1371/journal.pone.0042304 · Cited by 437
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly
Li, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts280 · Cited by 398
Population genomics of post-vaccine changes in pneumococcal epidemiology
Croucher, N. J., Finkelstein, J. A., Pelton, S. I., Mitchell, P. K., Lee, G. M., Parkhill, J., Bentley, S. D., Hanage, W. P., & Lipsitch, M. (2013) · Nature Genetics · doi:10.1038/ng.2625 · Cited by 365
Trait Variation in Yeast Is Defined by Population History
Warringer, J., Zörgö, E., Cubillos, F. A., Zia, A., Gjuvsland, A., Simpson, J. T., Forsmark, A., Durbin, R., Omholt, S. W., Louis, E. J., et al. (2011) · PLoS Genetics · doi:10.1371/journal.pgen.1002111 · Cited by 348
Self-citationA comprehensive assessment of somatic mutation detection in cancer using whole-genome sequencing
Alioto, T. S., Buchhalter, I., Derdak, S., Hutter, B., Eldridge, M. D., Hovig, E., Heisler, L. E., Beck, T. A., Simpson, J. T., Tonon, L., et al. (2015) · Nature Communications · doi:10.1038/ncomms10001 · Cited by 306
Self-citationLi, Z., Chen, Y., Mu, D., Yuan, J., Shi, Y., Zhang, H., Gan, J., Li, N., Hu, X., Liu, B., et al. (2012) · Briefings in Functional Genomics · doi:10.1093/bfgp/elr035 · Cited by 274
Detection of Genomic Structural Variants from Next-Generation Sequencing Data
Tattini, L., D’Aurizio, R., & Magi, A. (2015) · Frontiers in Bioengineering and Biotechnology · doi:10.3389/fbioe.2015.00092 · Cited by 273
Revealing the genetic structure of a trait by sequencing a population under selection
Parts, L., Cubillos, F. A., Warringer, J., Jain, K., Salinas, F., Bumpstead, S. J., Molin, M., Zia, A., Simpson, J. T., Quail, M. A., et al. (2011) · Genome Research · doi:10.1101/gr.116731.110 · Cited by 267
Self-citationAn improved genome assembly uncovers prolific tandem repeats in Atlantic cod
Tørresen, O. K., Star, B., Jentoft, S., Reinar, W. B., Grove, H., Miller, J. R., Walenz, B. P., Knight, J., Ekholm, J. M., Peluso, P., et al. (2017) · BMC Genomics · doi:10.1186/s12864-016-3448-x · Cited by 137
Metadata
- Authors
- Simpson, J. T., & Durbin, R.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2010-06-01
- Volume
- 26
- Issue
- 12
- Pages
- i367-i373
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2161048357
- Cited by
- 254
- References
- 24
- FWCI
- 21.77
- Type
- journal article
- Language
- en
- Open access
- hybrid
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.