The DOI matches its Crossref record; 73 of the 74 references it cites were found in a registry or an index.
A survey of sequence alignment algorithms for next-generation sequencing
Open accessAbstract
Rapidly evolving sequencing technologies produce data on an unparalleled scale. A central challenge to the analysis of this data is sequence alignment, whereby sequence reads must be compared to a reference. A wide variety of alignment algorithms and software have been subsequently developed over the past two years. In this article, we will systematically review the current development of these algorithms and introduce their practical applications on different types of experimental data. We come to the conclusion that short-read alignment is no longer the bottleneck of data analyses. We also consider future development of alignment algorithms with respect to emerging long sequence reads and the prospect of cloud computing.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
“When we examined the inter-site DEG false positive rates for several other analysis pipelines (WHAM34, Mapsplice35, Novoalign36, Cufflinks23, 37, 38 and HTSeq39) we found similarly high false positive rates, regardless of the analysis pipeline or read alignment methods used (Supplementary Fig. 1).”
From Detecting and correcting systematic variation in large-scale RNA sequencing data (2014) · cites this paper as [36]
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302
The Sequence Alignment/Map format and SAMtools
Li, H., Handsaker, B., Wysoker, A., Fennell, T., Ruan, J., Homer, N., Marth, G., Abecasis, G., Durbin, R., & 1000 Genome Project Data Processing Subgroup (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp352 · Cited by 62,041
Self-citationFast 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
Mapping and quantifying mammalian transcriptomes by RNA-Seq
Mortazavi, A., Williams, B. A., McCue, K., Schaeffer, L., & Wold, B. (2008) · Nature Methods · doi:10.1038/nmeth.1226 · Cited by 13,696
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-citationTopHat: discovering splice junctions with RNA-Seq
Trapnell, C., Pachter, L. S., & Salzberg, S. L. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp120 · Cited by 11,682
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,962
<tt>BLAT</tt> —The <tt>BLAST</tt> -Like Alignment Tool
Kent, W. J. (2002) · Genome Research · doi:10.1101/gr.229202 · Cited by 8,480
Sequencing technologies – the next generation
Metzker, M. L. (2010) · Nature Reviews Genetics · doi:10.1038/nrg2626 · Cited by 7,066
Versatile and open software for comparing large genomes
Kurtz, S., Phillippy, A., Delcher, A. L., Smoot, M., Shumway, M., Antonescu, C., & Salzberg, S. L. (2004) · Genome Biology · doi:10.1186/gb-2004-5-2-r12 · Cited by 5,254
SOAP2: an improved ultrafast tool for short read alignment
Li, R., Yu, C., Li, Y., Lam, T., Yiu, S., Kristiansen, K., & Wang, J. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp336 · Cited by 3,763
ABySS: A parallel assembler for short read sequence dataPreprint
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,658
SOAP: Short oligonucleotide alignment program
Li, R., Li, Y., Kristiansen, K., & Wang, J. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn025 · Cited by 3,597
Automated generation of heuristics for biological sequence comparison
Slater, G., & Birney, E. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-31 · Cited by 2,959
De novo assembly of human genomes with massively parallel short read sequencing
Li, R., Zhu, H., Ruan, J., Qian, W., Fang, X., Shi, Z., Li, Y., Li, S., Shan, G., Kristiansen, K., et al. (2010) · Genome Research · doi:10.1101/gr.097261.109 · Cited by 2,926 · cited 2×
“Given a query AGC, for example, the path matching the query is [0, 6]! [3, 3]![5, 5]![1, 1].”
BackgroundMethodA guided tour to approximate string matching
Navarro, G. (2001) · ACM Computing Surveys · doi:10.1145/375360.375365 · Cited by 2,661
Mapping short DNA sequencing reads and calling variants using mapping quality scores
Li, H., Ruan, J., & Durbin, R. (2008) · Genome Research · doi:10.1101/gr.078212.108 · Cited by 2,638
Self-citationA Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
Shotgun bisulphite sequencing of the Arabidopsis genome reveals DNA methylation patterning
Cokus, S. J., Feng, S.-H., Zhang, X.-Y., Chen, Z., Merriman, B., Haudenschild, C., Pradhan, S., Nelson, S., Pellegrini, M., & Jacobsen, S. (2008) · Nature · doi:10.1038/nature06745 · Cited by 2,278
Suffix Arrays: A New Method for On-Line String Searches
Manber, U., & Myers, E. W. (1993) · SIAM Journal on Computing · doi:10.1137/0222058 · Cited by 1,915
Fast and SNP-tolerant detection of complex variants and splicing in short reads
Wu, T. D., & Nacu, S. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq057 · Cited by 1,894
An improved algorithm for matching biological sequences
Gotoh, O. (1982) · Journal of Molecular Biology · doi:10.1016/0022-2836(82)90398-9 · Cited by 1,726
BreakDancer: an algorithm for high-resolution mapping of genomic structural variation
Chen, K., Wallis, J. W., McLellan, M. D., Larson, D. E., Kalicki, J. M., Pohl, C. S., McGrath, S. D., Wendl, M. C., Zhang, Q., Locke, D. P., et al. (2009) · Nature Methods · doi:10.1038/nmeth.1363 · Cited by 1,489
VarScan: variant detection in massively parallel sequencing of individual and pooled samples
Koboldt, D. C., Chen, K., Wylie, T., Larson, D. E., McLellan, M. D., Mardis, E. R., Weinstock, G. M., Wilson, R. K., & Ding, L. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp373 · Cited by 1,365
Opportunistic data structures with applications
Ferragina, P., & Manzini, G. (2000) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892127 · Cited by 1,325
BSMAP: whole genome bisulfite sequence MAPping program
Xi, Y., & Li, W. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-232 · Cited by 1,216
The Generic Genome Browser: A Building Block for a Model Organism System DatabasePreprint
Stein, L. D., Mungall, C., Shu, S., Caudy, M. A., Mangone, M., Day, A., Nickerson, E., Stajich, J., Harris, T. W., Arva, A., et al. (2002) · Genome Research · doi:10.1101/gr.403602 · Cited by 1,145
SSAHA: A Fast Search Method for Large DNA Databases
Ning, Z., Cox, A. J., & Mullikin, J. C. (2001) · Genome Research · doi:10.1101/gr.194201 · Cited by 965
AnO(ND) difference algorithm and its variations
Myers, E. W. (1986) · Algorithmica · doi:10.1007/bf01840446 · Cited by 936
PatternHunter: faster and more sensitive homology search
Ma, B., Tromp, J., & Li, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.440 · Cited by 837
Replacing suffix trees with enhanced suffix arrays
Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004) · Journal of Discrete Algorithms · doi:10.1016/s1570-8667(03)00065-0 · Cited by 676
Tablet-next generation sequence assembly visualization.
Milne, I., Bayer, M., Cardle, L., Shaw, P., Stephen, G., Wright, F., & Marshall, D. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp666 · Cited by 666
SHRiMP: Accurate Mapping of Short Color-space Reads
Rumble, S. M., Lacroute, P., Dalca, A. V., Fiume, M., Sidow, A., & Brudno, M. (2009) · PLoS Comput. Biol. · doi:10.1371/journal.pcbi.1000386 · Cited by 639
CloudBurst: highly sensitive read mapping with MapReduce
Schatz, M. C. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp236 · Cited by 630
Computation for ChIP-seq and RNA-seq studies
Pepke, S., Wold, B. J., & Mortazavi, A. (2009) · Nature Methods · doi:10.1038/nmeth.1371 · Cited by 568
BFAST: An Alignment Tool for Large Scale Genome Resequencing
Homer, N., Merriman, B., & Nelson, S. F. (2009) · PLoS ONE · doi:10.1371/journal.pone.0007767 · Cited by 541
Self-citationFast Mapping of Short Sequences with Mismatches, Insertions and Deletions Using Index Structures
Hoffmann, S., Otto, C., Kurtz, S., Sharma, C. M., Khaitovich, P., Vogel, J., Stadler, P. F., & Hackermüller, J. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000502 · Cited by 535
Searching for SNPs with cloud computing
Langmead, B., Schatz, M. C., Lin, J., Pop, M., & Salzberg, S. L. (2009) · Genome biology · doi:10.1186/gb-2009-10-11-r134 · Cited by 490
SeqMap: mapping massive amount of oligonucleotides to the genome
Jiang, H., & Wong, W. H. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn429 · Cited by 479
Sequencing of natural strains of Arabidopsis thaliana with short readsPreprint
Ossowski, S., Schneeberger, K., Clark, R. M., Lanz, C., Warthmann, N., & Weigel, D. (2008) · Genome Research · doi:10.1101/gr.080200.108 · Cited by 465
Striped Smith–Waterman speeds database searches six times over other SIMD implementations
Farrar, M. S. (2006) · Bioinformatics · doi:10.1093/bioinformatics/btl582 · Cited by 417
The Smallest Automaton Recognizing the Subwords of a Text
Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.-T., & Seiferas, J. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90157-4 · Cited by 379
Sense from sequence reads: methods for alignment and assembly
Flicek, P., & Birney, E. (2009) · Nature Methods · doi:10.1038/nmeth.1376 · Cited by 357
Using quality scores and longer reads improves accuracy of Solexa read mapping
Smith, A. D., Xuan, Z., & Zhang, M. Q. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-128 · Cited by 336
Building the sequence map of the human pan-genome
Li, R., Li, Y., Zheng, H., Luo, R., Zhu, H., Li, Q., Qian, W., Ren, Y., Tian, G., Li, J., et al. (2009) · Nature Biotechnology · doi:10.1038/nbt.1596 · Cited by 261
Simultaneous alignment of short reads against multiple genomes
Schneeberger, K., Hagmann, J., Ossowski, S., Warthmann, N., Gesing, S., Kohlbacher, O., & Weigel, D. (2009) · Genome biology · doi:10.1186/gb-2009-10-9-r98 · Cited by 238
ZOOM! Zillions of oligos mapped
Lin, H., Zhang, Z., Zhang, M. Q., Ma, B., & Li, M. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn416 · Cited by 210
RazerS--fast read mapping with sensitivity control.Preprint
Weese, D., Emde, A., Rausch, T., Döring, A., & Reinert, K. (2009) · Genome Research · doi:10.1101/gr.088823.108 · Cited by 178
Updates to the RMAP short-read mapping software
Smith, A. D., Chung, W., Hodges, E. C., Kendall, J., Hannon, G. J., Hicks, J. B., Xuan, Z., & Zhang, M. Q. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp533 · Cited by 164
Compressed indexing and local alignment of DNA
Lam, T.-W., Sung, W.-K., Tam, S.-L., Wong, C., & Yiu, S.-M. (2008) · Bioinform. · doi:10.1093/bioinformatics/btn032 · Cited by 159
Two algorithms for approxmate string matching in static texts
Jokinen, P., & Ukkonen, E. (1991) · Lecture notes in computer science · doi:10.1007/3-540-54345-7_67 · Cited by 157
Better Filtering with Gapped q-Grams
Burkhardt, S., & Kärkkäinen, J. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48194-x_6 · Cited by 143
PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds
Chen, Y., Souaiaia, T., & Chen, T. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp486 · Cited by 122
Automatic reconstruction of 3D neuron structures using a graph-augmented deformable model
Peng, H., Ruan, Z., Atasoy, D., & Sternson, S. M. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq212 · Cited by 120
Optimal spliced alignments of short sequence reads
Bona, F. D., Ossowski, S., Schneeberger, K., & Rätsch, G. (2008) · BMC Bioinformatics · doi:10.1186/1471-2105-9-s10-o7 · Cited by 109
Microindel detection in short-read sequence data
Krawitz, P. M., Rödelsperger, C., Jäger, M., Jostins, L., Bauer, S., & Robinson, P. N. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq027 · Cited by 108
OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences
Meek, C., Patel, J. M., & Kasetty, S. (2003) · Very Large Data Bases Conference · doi:10.1016/b978-012722442-8/50085-9 · Cited by 107
Munro, J. I., Raman, V., & Satti, S. R. (2001) · Journal of Algorithms · doi:10.1006/jagm.2000.1151 · Cited by 102
Fast and practical approximate string matching
Baeza-Yates, R. A., & Perleberg, C. H. (1992) · Lecture notes in computer science · doi:10.1007/3-540-56024-6_15 · Cited by 97
Optimal spliced alignments of short sequence reads
Bona, F. D., Ossowski, S., Schneeberger, K., & Rätsch, G. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn300 · Cited by 94
Munro, I., Raman, V., & Satti, S. R. (1998) · Lecture notes in computer science · doi:10.1007/978-3-540-49382-2_17 · Cited by 88
Clement, N. L., Snell, Q. O., Clement, M., Hollenhorst, P. C., Purwar, J., Graves, B. J., Cairns, B. R., & Johnson, W. E. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp614 · Cited by 82
BamView: viewing mapped read alignment data in the context of the reference sequence
Carver, T. J., Böhme, U., Otto, T. D., Parkhill, J., & Berriman, M. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq010 · Cited by 71
Genome variation discovery with high-throughput sequencing data
Dalca, A. V., & Brudno, M. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbp058 · Cited by 71
LookSeq: A browser-based viewer for deep sequencing dataPreprint
Manske, M., & Kwiatkowski, D. P. (2009) · Genome Research · doi:10.1101/gr.093443.109 · Cited by 63
ReAligner: A Program for Refining DNA Sequence Multi-Alignments
Anson, E. L., & Myers, E. W. (1997) · Journal of Computational Biology · doi:10.1089/cmb.1997.4.369 · Cited by 63
Malhis, N., Butterfield, Y. S. N., Ester, M., & Jones, S. J. M. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn565 · Cited by 56
High quality SNP calling using Illumina data at shallow coverage
Malhis, N., & Jones, S. J. M. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq092 · Cited by 55
Storage and Retrieval of Individual Genomes
Mäkinen, V., Navarro, G., Sirén, J., & Välimäki, N. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02008-7_9 · Cited by 45
Local alignment of two-base encoded DNA sequence
Homer, N., Merriman, B., & Nelson, S. F. (2009) · BMC Bioinformatics · doi:10.1186/1471-2105-10-175 · Cited by 40
Self-citationIndexing DNA Sequences Using q-Grams
Cao, X., Li, S. C., & Tung, A. K. H. (2005) · Lecture notes in computer science · doi:10.1007/11408079_4 · Cited by 37
Research works printed but not linked: 1
- 1985, THEORETICAL COMPUTER SCIENCE, 40, 31
Cited by
Sorted by citations
Trimmomatic: a flexible trimmer for Illumina sequence data
Bolger, A. M., Lohse, M., & Usadel, B. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu170 · Cited by 65,548
Fast gapped-read alignment with Bowtie 2
Langmead, B., & Salzberg, S. L. (2012) · Nature Methods · doi:10.1038/nmeth.1923 · Cited by 56,400
The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote
Liao, Y., Smyth, G. K., & Shi, W. (2013) · Nucleic Acids Research · doi:10.1093/nar/gkt214 · Cited by 3,064
Adaptive seeds tame genomic sequence comparisonPreprint
Kiełbasa, S. M., Wan, R., Sato, K., Horton, P., & Frith, M. C. (2011) · Genome Research · doi:10.1101/gr.113985.110 · Cited by 1,287
The Ensembl gene annotation system
Aken, B. L., Ayling, S., Barrell, D., Clarke, L., Curwen, V., Fairley, S., Fernandez Banet, J., Billis, K., García Girón, C., Hourlier, T., et al. (2016) · Database · doi:10.1093/database/baw093 · Cited by 1,086
Metadata
- Authors
- Li, H., & Homer, N.
- Affiliations
- Broad Institute (US)
- ORCID
- Li, H.
- Venue
- Briefings in Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2010-05-11
- Volume
- 11
- Issue
- 5
- Pages
- 473-483
- ISSN
- 1467-5463 (ISSN-L)
- 1477-4054
- PMC
- PMC2943993
- OpenAlex
- W2093931624
- Cited by
- 875
- References
- 74
- Citations by year
- 2026: 11 · 2025: 21 · 2024: 22 · 2023: 21 · 2022: 20 · 2021: 37 · 2020: 41 · 2019: 41 · 2018: 69 · 2017: 52 · 2016: 74 · 2015: 88 · 2014: 118 · 2013: 105 · 2012: 83
- FWCI
- 7.25
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Briefings in Bioinformatics (publishedVersion)
- Europe PMC (PubMed Central) (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Institutes of Health
- National Human Genome Research Institute (U01HG005210, U01HG005208)
- 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 › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- sequence alignment, next-generation sequencing, short-read alignment, long-read sequencing, alignment algorithms, reference genome mapping, cloud computing, bioinformatics software
- MeSH terms
- Algorithms, Base Sequence, Humans, Software, Genome, Human, Sequence Alignment, Sequence Analysis, DNA
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
