Short Read Mapping: An Algorithmic Tour
Open accessThe DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Ultra-high-throughput next-generation sequencing (NGS) technology allows us to determine the sequence of nucleotides of many millions of DNA molecules in parallel. Accompanied by a dramatic reduction in cost since its introduction in 2004, NGS technology has provided a new way of addressing a wide range of biological and biomedical questions, from the study of human genetic disease to the analysis of gene expression, protein-DNA interactions, and patterns of DNA methylation. The data generated by NGS instruments comprise huge numbers of very short DNA sequences, or 'reads', that carry little information by themselves. These reads therefore have to be pieced together by well-engineered algorithms to reconstruct biologically meaningful measurments, such as the level of expression of a gene. To solve this complex, high-dimensional puzzle, reads must be mapped back to a reference genome to determine their origin Due to sequencing errors and to genuine differences between the reference genome and the individual being sequenced, this mapping process must be tolerant of mismatches, insertions, and deletions. Although optimal alignment algorithms to solve this problem have long been available, the practical requirements of aligning hundreds of millions of short reads to the 3 billion base pair long human genome have stimulated the development of new, more efficient methods, which today are used routinely throughout the world for the analysis of NGS data.
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
SOAP: Short oligonucleotide alignment program
Li, R., Li, Y., Kristiansen, K., & Wang, J. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn025 · Cited by 3,597
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
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 1×
“’’ Initially, read lengths were only 25 base pairs (bp), which although short is nonetheless long enough to map approximately 79% of the human genome [68]; i.”
BackgroundMapping 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
Rapid similarity searches of nucleic acid and protein data banks.
Wilbur, W. J., & Lipman, D. J. (1983) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.80.3.726 · Cited by 1,546 · cited 1×
“The need to efficiently align a query sequence against a database motivated a heuristic algorithm proposed by Wilbur and Lipman [116] and refined and implemented in the FASTA program suite [93].”
MethodStem cell transcriptome profiling via massive-scale mRNA sequencing
Cloonan, N., Forrest, A. R. R., Kolle, G., Gardiner, B. B. A., Faulkner, G. J., Brown, M. K., Taylor, D. F., Steptoe, A. L., Wani, S., Bethel, G., et al. (2008) · Nature Methods · doi:10.1038/nmeth.1223 · Cited by 1,035 · cited 1×
“Additional new techniques have 2511led to the widespread use of sequencing to study gene expression (RNA-seq [21], [72], [87]), protein– DNA interactions (ChIP-seq [45]), and DNA methylation (MeDIP-seq [27]).”
BackgroundStampy: A statistical algorithm for sensitive and fast mapping of Illumina sequence reads
Lunter, G., & Goodson, M. (2011) · Genome Research · doi:10.1101/gr.111120.110 · Cited by 1,016
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 · cited 1×
“Other methods for fast indexing also emerged at this time, such as the BLAT [49] and SSAHA [92] programs, both of which (similarly to FASTA) used a hash index based on k-tuples.”
MethodDelcher, A. L., Kasif, S., Fleischmann, R. D., Peterson, J., White, O., & Salzberg, S. L. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.11.2369 · Cited by 893 · cited 5×
“The first solution to this problem, the MUMmer program [24], used the suffix tree data”
BackgroundMethodInfluentialSelf-citationPersonalized copy number and segmental duplication maps using next-generation sequencing
Alkan, C., Kidd, J. M., Marques-Bonet, T., Aksay, G., Antonacci, F., Hormozdiari, F., Kitzman, J. O., Baker, C., Malig, M., Mutlu, O., et al. (2009) · Nature Genetics · doi:10.1038/ng.437 · Cited by 748 · cited 1×
“Tools that index the reads include Eland (AJ Cox, Illumina, unpublished), mrFAST/mrsFAST [6]/[39], MAQ [64], RMAP [106], ZOOM [70], SeqMap [44], and SHRiMP [97].”
Method
Cited by
Technology dictates algorithms: recent developments in read alignment
Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., et al. (2021) · Genome Biology · doi:10.1186/s13059-021-02443-7 · Cited by 144
Quantum computing algorithms: getting closer to critical problems in computational biology
Marchetti, L., Nifosì, R., Martelli, P. L., Da Pozzo, E., Cappello, V., Banterle, F., Trincavelli, M. L., Martini, C., & D’Elia, M. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac437 · Cited by 47
“The most efficient computational algorithms to date exploit the Ferragina– Manzini string index based on the Burrows–Wheeler transform (see [134] for a detailed survey of all short mapping read methods).”
MethodRevisiting CRISPR/Cas-mediated crop improvement: special focus on nutrition
Kaul, T., Sony, S. K., Verma, R., Motelb, K. F. A., Prakash, A. T., Eswaran, M., Bharti, J., Nehra, M., & Kaul, R. (2020) · Journal of Biosciences · doi:10.1007/s12038-020-00094-7 · Cited by 33
Metadata
- Authors
- Canzar, S., & Salzberg, S. L.
- Venue
- Proceedings of the IEEE
- Published
- 2017-03
- Volume
- 105
- Issue
- 3
- Pages
- 436-458
- ISSN
- 0018-9219 (ISSN-L)
- 1558-2256
- OpenAlex
- W2526975281
- Cited by
- 89
- References
- 12
- FWCI
- 1.93
- Type
- journal article
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Short Read Mapping: An Algorithmic Tour. https://app.cochat.ai/papers/10.1109/jproc.2015.2455551
- The paper
- Canzar, S., & Salzberg, S. L. (2017). Short Read Mapping: An Algorithmic Tour. Proceedings of the IEEE. https://doi.org/10.1109/jproc.2015.2455551
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.