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
De novo bacterial genome sequencing: Millions of very short reads assembled on a desktop computer
Hernandez, D., François, P., Farinelli, L., Østerås, M., & Schrenzel, J. (2008) · Genome Research · doi:10.1101/gr.072033.107 · Cited by 629
(2005) · Lecture Notes in Computer Science · doi:10.1007/11557067 · Cited by 495
Short read fragment assembly of bacterial genomes
Chaisson, M. J., & Pevzner, P. A. (2008) · Genome Research · doi:10.1101/gr.7088808 · Cited by 441
The fragment assembly string graph
Myers, E. W. (2005) · Bioinformatics · doi:10.1093/bioinformatics/bti1114 · Cited by 424
Genome assembly reborn: recent computational challenges
Pop, M. (2009) · Briefings in Bioinformatics · doi:10.1093/bib/bbp026 · Cited by 387
A taxonomy of suffix array construction algorithms
Puglisi, S. J., Smyth, W. F., & Turpin, A. H. (2007) · ACM Computing Surveys · doi:10.1145/1242471.1242472 · Cited by 312
Suffix arrays: a new method for on-line string searches
Manber, U., & Myers, E. W. (1990) · doi:10.5555/320176.320218 · Cited by 293
Space efficient linear time construction of suffix arrays
Ko, P., & Aluru, S. (2005) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2004.08.002 · Cited by 180
Computability of Models for Sequence Assembly
Medvedev, P., Georgiou, K., Myers, G., & Brudno, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74126-8_27 · Cited by 160
Linear Suffix Array Construction by Almost Pure Induced-Sorting
Nong, G., Zhang, S., & Chan, W. H. (2009) · DCC · doi:10.1109/dcc.2009.42 · Cited by 143
High Throughput Short Read Alignment via Bi-directional BWT
Lam, T., Li, R., Tam, A., Wong, S., Wu, E., & Yiu, S. (2009) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm.2009.42 · Cited by 125
Compressed Suffix Arrays for Massive Data
Sirén, J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03784-9_7 · Cited by 51
Lightweight Data Indexing and Compression in External Memory
Ferragina, P., Gagie, T., & Manzini, G. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-12200-2_60 · Cited by 24
(1997)
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
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.