The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote
Open accessThe DOI matches its Crossref record; 53 of the 55 references it cites were found in a registry or an index.
Abstract
Read alignment is an ongoing challenge for the analysis of data from sequencing technologies. This article proposes an elegantly simple multi-seed strategy, called seed-and-vote, for mapping reads to a reference genome. The new strategy chooses the mapped genomic location for the read directly from the seeds. It uses a relatively large number of short seeds (called subreads) extracted from each read and allows all the seeds to vote on the optimal location. When the read length is <160 bp, overlapping subreads are used. More conventional alignment algorithms are then used to fill in detailed mismatch and indel information between the subreads that make up the winning voting block. The strategy is fast because the overall genomic location has already been chosen before the detailed alignment is done. It is sensitive because no individual subread is required to map exactly, nor are individual subreads constrained to map close by other subreads. It is accurate because the final location must be supported by several different subreads. The strategy extends easily to find exon junctions, by locating reads that contain sets of subreads mapping to different exons of the same gene. It scales up efficiently for longer reads.
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
Figures
![Figure 1. Seed-and-vote mapping paradigm. (A) Schematic of the proposed mapping paradigm. Subreads (or seeds) are short continuous sequences extracted from each read. Substrings in green are uninformative subreads, and they are excluded from voting. Little red bars denote mismatched bases. Mapping location of the read is determined by the largest consensus set. The thin solid arrows point to the mapping location of each subread included in the largest consensus set. Mapping location of the read, as indicated by the black up-pointing triangle, is voted for by all the subreads in the largest consensus set. The dashed arrows indicate other mapping locations for the subreads, and these locations were disregarded due to insufficient number of votes. (B) Using an artificial example to illustrate the paradigm. Six subreads are extracted from the artificial read. Each square bracket denotes an extracted subread, which contains five continuous bases, and the number embedded in the blue cycle indicates the subread number. Base sequence of each subread is encoded into a string of 0’s and 1’s (each base is encoded into a 2-bit binary number). Encoded value for each subread is used as its key in the hash table. The key’s value gives the chromosomal location/s in the genome to which the corresponding subread is perfectly matched (no mismatches allowed). Four candidate mapping locations are found for this artificial read, which receive 2, 5, 1 and 2 votes (number of consensus subreads), respectively. The location that receives the largest number of votes, in this case the location with five votes, is selected as the final mapping location for this artificial read. (C) Indel detection performed under the seed-and-vote paradigm. (C1) shows the mapping results of subreads when there are no indels found in the reads (assuming no mismatches exist in the read for simplicity). (C2) and (C3) show respectively the schematic for detecting an insertion (Ins) and a deletion (Del) in the situation where insertion or deletion is found in the read and flanking subreads are found at both sides of insertion or deletion. (C4) gives the schematic for detecting indels when they occur at the locations close to the end of the reads where flanking subreads can be found at only one side. In (C2) and (C3), chromosomal locations pointed to by red arrows are the true mapping locations of subreads 8, 9 and 10, respectively, and chromosomal locations pointed to by dotted black arrows indicate the chromosomal locations to which they will be mapped if no indels exist before them. d is the indel length, equal to the difference between the location pointed to by the red arrow and the location pointed to by the dotted black arrow from the same subread. Regions encompassed by the dotted green lines are found to contain indels [(C2) and (C3)] or are candidate regions for searching indels (C4). Bases in these regions are not covered by subreads that have made successful votes, and their mapping locations will be determined by aligning to the corresponding regions (within the dotted green lines) in the reference genome. In (C4), a 4 bp window is moved along the uncovered bases to look for potential indels. When three or more bases in the window are found to be mismatches, the indel detection process is triggered for the search of indels.](https://figures.cochat.ai/paper-figures/2732577f79394edeae1b1ed02056f570/the-subread-aligner-fast-accurate-and-scalable-read-mapping-by-seed-and-vote-figure-1.jpg)



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
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
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
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
Fast gapped-read alignment with Bowtie 2
Langmead, B., & Salzberg, S. L. (2012) · Nature Methods · doi:10.1038/nmeth.1923 · Cited by 56,400 · cited 18×
“Similar to its performance in mapping the data set that does not contain indels, Bowtie2 had a high recall rate but low accuracy.”
BackgroundMethodInfluentialRobinson, M. D., McCarthy, D. J., & Smyth, G. K. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp616 · Cited by 41,364
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
Differential expression analysis for sequence count data
Anders, S., & Huber, W. (2010) · Genome Biology · doi:10.1186/gb-2010-11-10-r106 · Cited by 15,581
Trapnell, C., Williams, B. A., Pertea, G., Mortazavi, A., Kwan, G., van Baren, M. J., Salzberg, S. L., Wold, B. J., & Pachter, L. (2010) · Nature Biotechnology · doi:10.1038/nbt.1621 · Cited by 15,556
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
TopHat: discovering splice junctions with RNA-Seq
Trapnell, C., Pachter, L., & Salzberg, S. L. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp120 · Cited by 11,617
A framework for variation discovery and genotyping using next-generation DNA sequencing data
DePristo, M. A., Banks, E., Poplin, R., Garimella, K. V., Maguire, J. R., Hartl, C., Philippakis, A. A., del Angel, G., Rivas, M. A., Hanna, M., et al. (2011) · Nature Genetics · doi:10.1038/ng.806 · Cited by 11,456
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288 · cited 1×
“In general, the running time of dynamic programming increases quadratically with read length (11,12).”
Exploration, normalization, and summaries of high density oligonucleotide array probe level data
Irizarry, R. A. (2003) · Biostatistics · doi:10.1093/biostatistics/4.2.249 · Cited by 10,603
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,940
Bolstad, B. M., Irizarry, R. A., Åstrand, M., & Speed, T. P. (2003) · Bioinformatics · doi:10.1093/bioinformatics/19.2.185 · Cited by 8,266
A map of human genome variation from population-scale sequencing.
The 1000 Genomes Project Consortium (2010) · Nature · doi:10.1038/nature09534 · Cited by 7,877
McCarthy, D. J., Chen, Y., & Smyth, G. K. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks042 · Cited by 5,195
Self-citationMapping 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
MAQC Consortium, Shi, L., Shi, L., Reid, L. H., Jones, W. D., Shippy, R., Warrington, J. A., Baker, S. C., Collins, P. J., de Longueville, F., et al. (2006) · Nature Biotechnology · doi:10.1038/nbt1239 · Cited by 2,126 · cited 1×
“The SEQC project, which is the third stage of the wellknown MAQC project (31), is producing benchmark nextgen sequencing data.”
BackgroundFast 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
ART: a next-generation sequencing read simulator
Huang, W., Li, L., Myers, J. R., & Marth, G. T. (2012) · Bioinformatics · doi:10.1093/bioinformatics/btr708 · Cited by 1,596
MapSplice: Accurate mapping of RNA-seq reads for splice junction discovery
Wang, K., Singh, D., Zeng, Z., Coleman, S. J., Huang, Y., Savich, G. L., He, X., Mieczkowski, P., Grimm, S. A., Perou, C. M., et al. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq622 · Cited by 1,193
O'Connell, R. J., Thon, M. R., Hacquard, S., Amyotte, S. G., Kleemann, J., Torres, M. F., Damm, U., Buiate, E. A., Epstein, L., Alkan, N., et al. (2012) · Nature Genetics · doi:10.1038/ng.2372 · Cited by 1,047
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875 · cited 1×
“A survey of read aligners can be found in (10).”
BackgroundModerated statistical tests for assessing differences in tag abundance
Robinson, M. D., & Smyth, G. K. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm453 · Cited by 856
Self-citationbaySeq: Empirical Bayesian methods for identifying differential expression in sequence count data
Hardcastle, T. J., & Kelly, K. A. (2010) · BMC Bioinformatics · doi:10.1186/1471-2105-11-422 · Cited by 756
The GEM mapper: fast, accurate and versatile alignment by filtration
Marco-Sola, S., Sammeth, M., Guigó, R., & Ribeca, P. (2012) · Nature Methods · doi:10.1038/nmeth.2221 · Cited by 544
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 529
A fast bit-vector algorithm for approximate string matching based on dynamic programming
Myers, G. (1999) · Journal of the ACM · doi:10.1145/316542.316550 · Cited by 445
The External RNA Controls Consortium: a progress report
The External RNA Controls Consortium (2005) · Nature Methods · doi:10.1038/nmeth1005-731 · Cited by 373 · cited 1×
“The SEQC (MAQC III) project is now using Ambion(textregistered] ERCC spike-in control (36) to evaluate inter-laboratory concordance in using next-gen sequencing technologies.”
MethodSHRiMP2: Sensitive yet Practical Short Read Mapping
David, M., Dzamba, M., Lister, D., Ilie, L., & Brudno, M. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr046 · Cited by 348
Cloud-scale RNA-sequencing differential expression analysis with Myrna
Langmead, B., Hansen, K. D., & Leek, J. T. (2010) · Genome Biology · doi:10.1186/gb-2010-11-8-r83 · Cited by 311
mrsFAST: a cache-oblivious algorithm for short-read mapping
Hach, F., Hormozdiari, F., Alkan, C., Hormozdiari, F., Birol, I., Eichler, E. E., & Sahinalp, S. C. (2010) · Nature Methods · doi:10.1038/nmeth0810-576 · Cited by 274
Sun, T., Gao, Y., Tan, W., Ma, S., Shi, Y., Yao, J., Guo, Y., Yang, M., Zhang, X., Zhang, Q., et al. (2007) · Nature Genetics · doi:10.1038/ng2030 · Cited by 269
Optimizing the noise versus bias trade-off for Illumina Whole Genome Expression Beadchips
Shi, W., Oshlack, A., & Smyth, G. K. (2010) · Nucleic Acids Research · doi:10.1093/nar/gkq871 · Cited by 225 · cited 1×
“Spike-in data sets have proved effective for evaluating methods developed for the analysis of micro-array data (31,39–43).”
MethodSelf-citationZOOM! Zillions of oligos mapped
Lin, H., Zhang, Z., Zhang, M. Q., Ma, B., & Li, M. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn416 · Cited by 208
Holtgrewe, M. (2010) · PubMed · doi:10.17169/refubium-22374 · Cited by 191
q -gram based database searching using a suffix array (QUASAR)
Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H., Rivals, É., & Vingron, M. (1999) · Research in Computational Molecular Biology · doi:10.1145/299432.299460 · Cited by 167
RazerS 3: Faster, fully sensitive read mapping
Weese, D., Holtgrewe, M., & Reinert, K. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts505 · Cited by 158
Global Changes in the Mammary Epigenome Are Induced by Hormonal Cues and Coordinated by Ezh2
Pal, B., Bouras, T., Shi, W., Vaillant, F., Sheridan, J. M., Fu, N., Breslin, K., Jiang, K., Ritchie, M. E., Young, M., et al. (2013) · Cell Reports · doi:10.1016/j.celrep.2012.12.020 · Cited by 135
Self-citationEfficient q -Gram Filters for Finding All ε -Matches over a Given Length
Rasmussen, K. R., Stoye, J., & Myers, E. W. (2006) · Journal of Computational Biology · doi:10.1089/cmb.2006.13.296 · Cited by 115
Zhao, L., Glazov, E. A., Pattabiraman, D. R., Alowaidi, F., Zhang, P., Brown, M. A., Leo, P. J., & Gonda, T. J. (2011) · Nucleic Acids Research · doi:10.1093/nar/gkr024 · Cited by 107
GASSST: global alignment short sequence search tool
Rizk, G., & Lavenier, D. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq485 · Cited by 101
A novel and well-defined benchmarking method for second generation read mapping
Holtgrewe, M., Emde, A., Weese, D., & Reinert, K. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-210 · Cited by 96
Epigenetic regulation of normal human mammary cell type–specific miRNAs
Vrba, L., Garbe, J. C., Stampfer, M. R., & Futscher, B. W. (2011) · Genome Research · doi:10.1101/gr.123935.111 · Cited by 82
Efficient q-Gram Filters for Finding All ε-Matches over a Given Length
Rasmussen, K. R., Stoye, J., & Myers, E. W. (2005) · Lecture notes in computer science · doi:10.1007/11415770_15 · Cited by 72
STELLAR: fast and exact local alignments
Kehr, B., Weese, D., & Reinert, K. (2011) · BMC Bioinformatics · doi:10.1186/1471-2105-12-s9-s15 · Cited by 40
Copy-number-aware differential analysis of quantitative DNA sequencing data
Robinson, M. D., Strbenac, D., Stirzaker, C., Statham, A. L., Song, J. Z., Speed, T. P., & Clark, S. J. (2012) · Genome Research · doi:10.1101/gr.139055.112 · Cited by 39
Anatomy of a hash-based long read sequence mapping algorithm for next generation DNA sequencing
Misra, S., Agrawal, A., Liao, W., & Choudhary, A. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq648 · Cited by 35
Consolidated strategy for the analysis of microarray spike-in data
McCall, M. N., & Irizarry, R. A. (2008) · Nucleic Acids Research · doi:10.1093/nar/gkn430 · Cited by 34
q-gram Based Database Searching Using a Suffix Array (QUASAR)
Burkhardt, S., Crauser, A., Ferragina, P., Lenhof, H., Rivals, É., & Vingron, M. (1999) · Max Planck Institute for Plasma Physics · Cited by 34
Spike-in validation of an Illumina-specific variance-stabilizing transformation
Dunning, M., Ritchie, M. E., Barbosa‐Morais, N. L., Tavaré, S., & Lynch, A. G. (2008) · BMC Research Notes · doi:10.1186/1756-0500-1-18 · Cited by 14
Bi, X.-H., Lu, C.-M., Liu, Q., Zhang, Z., Zhao, H.-L., Yu, J., & Zhang, J. (2011) · Journal of Neural Transmission · doi:10.1007/s00702-011-0696-4 · Cited by 5
Cited by
limma powers differential expression analyses for RNA-sequencing and microarray studies
Ritchie, M. E., Phipson, B., Wu, D., Hu, Y., Law, C. W., Shi, W., & Smyth, G. K. (2015) · Nucleic Acids Research · doi:10.1093/nar/gkv007 · Cited by 40,458
Self-citationfeatureCounts: an efficient general purpose program for assigning sequence reads to genomic features
Liao, Y., Smyth, G. K., & Shi, W. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btt656 · Cited by 27,219
“…data input to featureCounts consists of (i) one or more files of aligned reads in either SAM or BAM format (Li et al. , 2009) and (ii) a list of genomic features in either General Feature Format (GFF) (Wellcome Trust Sanger Institute, 2013) or Simplified Annotation Format (SAF) (Shi and Liao, 2013b).”
BackgroundMethodInfluentialSelf-citationTwo new Later Stone Age sites from the Final Pleistocene in the Falémé Valley, eastern Senegal
Ndiaye, M., Lespez, L., Tribolo, C., Rassé, M., Hadjas, I., Davidoux, S., Huysecom, É., & Douze, K. (2024) · Monash University Research Portal (Monash University) · doi:10.3929/ethz-b-000667478 · Cited by 23,868
voom: precision weights unlock linear model analysis tools for RNA-seq read counts
Law, C. W., Chen, Y., Shi, W., & Smyth, G. K. (2014) · Genome Biology · doi:10.1186/gb-2014-15-2-r29 · Cited by 6,155
Self-citationLiao, Y., Smyth, G. K., & Shi, W. (2019) · Nucleic Acids Research · doi:10.1093/nar/gkz114 · Cited by 2,936
Self-citation
Metadata
- Authors
- Liao, Y., Smyth, G. K., & Shi, W.
- Affiliations
- The University of Melbourne (AU)
- Corresponding author
- Shi, Wei
- Venue
- Nucleic Acids Research
- Publisher
- Oxford University Press (OUP)
- Published
- 2013-04-03
- Volume
- 41
- Issue
- 10
- Pages
- e108-e108
- ISSN
- 0305-1048 (ISSN-L)
- 1362-4962
- PMC
- PMC3664803
- OpenAlex
- W2110905563
- Cited by
- 3,064
- References
- 55
- Citations by year
- 2026: 213 · 2025: 307 · 2024: 339 · 2023: 318 · 2022: 290 · 2021: 321 · 2020: 321 · 2019: 300 · 2018: 250 · 2017: 176 · 2016: 123 · 2015: 66 · 2014: 30 · 2013: 9
- FWCI
- 34.02
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- Nucleic Acids Research (publishedVersion, cc-by-nc)
- Europe PMC (PubMed Central) (publishedVersion, cc-by-nc)
- PubMed Central (publishedVersion, cc-by-nc)
- PubMed (publishedVersion)
- Minerva Access (University of Melbourne) (submittedVersion, cc-by-nc)
- Funders
- Australian Government
- Medical Research Council
- National Health and Medical Research Council (1023454)
- 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
- read mapping, reference genome mapping, long reads, alignment accuracy, scalability
- MeSH terms
- Exons, Software, Sequence Alignment, Genomics, INDEL Mutation, High-Throughput Nucleotide Sequencing
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.