Technology dictates algorithms: recent developments in read alignment

Mohammed Alser; Jeremy Rotman; Dhrithi Deshpande; Kodi Taraszka; Huwenbo Shi; Pelin Icer Baykal; Harry Taegyun Yang; Victor Xue; Sergey Knyazev; Benjamin D. Singer; Brunilda Balliu; David Koslicki; Pavel Skums; Alex Zelikovsky; Can Alkan; Onur Mutlu; Serghei Mangul

doi:10.1186/s13059-021-02443-7

Technology dictates algorithms: recent developments in read alignment

Mohammed Alser, Jeremy Rotman, Dhrithi Deshpande, Kodi Taraszka, Huwenbo Shi, Pelin Icer Baykal, Harry Taegyun Yang, Victor Xue, Sergey Knyazev, Benjamin D. Singer, Brunilda Balliu, David Koslicki, Pavel Skums, Alex Zelikovsky, Can Alkan, Onur Mutlu, Serghei Mangul^*

^*Corresponding author for this work

Research output: Contribution to journal › Review article › peer-review

72 Scopus citations

Abstract

Aligning sequencing reads onto a reference is an essential step of the majority of genomic analysis pipelines. Computational algorithms for read alignment have evolved in accordance with technological advances, leading to today’s diverse array of alignment methods. We provide a systematic survey of algorithmic foundations and methodologies across 107 alignment methods, for both short and long reads. We provide a rigorous experimental evaluation of 11 read aligners to demonstrate the effect of these underlying algorithms on speed and efficiency of read alignment. We discuss how general alignment algorithms have been tailored to the specific needs of various domains in biology.

Original language	English (US)
Article number	249
Journal	Genome biology
Volume	22
Issue number	1
DOIs	https://doi.org/10.1186/s13059-021-02443-7
State	Published - Dec 2021

Funding

B.D.S. is supported by NIH/NHLBI K08HL128867, P.S. is supported by NIH 1R01EB025022 and National Science Foundation grants 2047828, P.I.B. and S.K. are supported by the Molecular Basis of Disease (MBD), B.S. is supported by NIH R01HL149883 and NIH R01HL153122, O.M. is supported by Intel, VMware, and NIH HG006004, and S.M. is supported by National Science Foundation grant 2041984. The authors acknowledge the Computational Genomics Summer Institute (CGSI), funded by NIH GM112625, which fostered international collaboration among the groups involved in this project. We thank the authors of the tools surveyed in this work for providing helpful feedback and verifying the information related to their tool. We also thank Martin Frith (University of Tokyo), Heng Li (Harvard University), Cenk Sahinalp (National Cancer Institute), and Steven Salzberg (Johns Hopkins University) for their valuable feedback and discussion. Andrew Cosgrove was the primary editor of this article and managed its editorial process and peer review in collaboration with the rest of the editorial team. The peer review history is available as additional?file?2.

ASJC Scopus subject areas

Ecology, Evolution, Behavior and Systematics
Genetics
Cell Biology

Access to Document

10.1186/s13059-021-02443-7

Cite this

Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., Balliu, B., Koslicki, D., Skums, P., Zelikovsky, A., Alkan, C., Mutlu, O., & Mangul, S. (2021). Technology dictates algorithms: recent developments in read alignment. Genome biology, 22(1), Article 249. https://doi.org/10.1186/s13059-021-02443-7

@article{d9e8e7151594459d9ab28d2a699a4d8c,

title = "Technology dictates algorithms: recent developments in read alignment",

abstract = "Aligning sequencing reads onto a reference is an essential step of the majority of genomic analysis pipelines. Computational algorithms for read alignment have evolved in accordance with technological advances, leading to today{\textquoteright}s diverse array of alignment methods. We provide a systematic survey of algorithmic foundations and methodologies across 107 alignment methods, for both short and long reads. We provide a rigorous experimental evaluation of 11 read aligners to demonstrate the effect of these underlying algorithms on speed and efficiency of read alignment. We discuss how general alignment algorithms have been tailored to the specific needs of various domains in biology.",

author = "Mohammed Alser and Jeremy Rotman and Dhrithi Deshpande and Kodi Taraszka and Huwenbo Shi and Baykal, {Pelin Icer} and Yang, {Harry Taegyun} and Victor Xue and Sergey Knyazev and Singer, {Benjamin D.} and Brunilda Balliu and David Koslicki and Pavel Skums and Alex Zelikovsky and Can Alkan and Onur Mutlu and Serghei Mangul",

note = "Funding Information: B.D.S. is supported by NIH/NHLBI K08HL128867, P.S. is supported by NIH 1R01EB025022 and National Science Foundation grants 2047828, P.I.B. and S.K. are supported by the Molecular Basis of Disease (MBD), B.S. is supported by NIH R01HL149883 and NIH R01HL153122, O.M. is supported by Intel, VMware, and NIH HG006004, and S.M. is supported by National Science Foundation grant 2041984. The authors acknowledge the Computational Genomics Summer Institute (CGSI), funded by NIH GM112625, which fostered international collaboration among the groups involved in this project. Funding Information: We thank the authors of the tools surveyed in this work for providing helpful feedback and verifying the information related to their tool. We also thank Martin Frith (University of Tokyo), Heng Li (Harvard University), Cenk Sahinalp (National Cancer Institute), and Steven Salzberg (Johns Hopkins University) for their valuable feedback and discussion. Andrew Cosgrove was the primary editor of this article and managed its editorial process and peer review in collaboration with the rest of the editorial team. The peer review history is available as additional?file?2. Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2021",

month = dec,

doi = "10.1186/s13059-021-02443-7",

language = "English (US)",

volume = "22",

journal = "Genome biology",

issn = "1474-7596",

publisher = "BioMed Central",

number = "1",

}

TY - JOUR

T1 - Technology dictates algorithms

T2 - recent developments in read alignment

AU - Alser, Mohammed

AU - Rotman, Jeremy

AU - Deshpande, Dhrithi

AU - Taraszka, Kodi

AU - Shi, Huwenbo

AU - Baykal, Pelin Icer

AU - Yang, Harry Taegyun

AU - Xue, Victor

AU - Knyazev, Sergey

AU - Singer, Benjamin D.

AU - Balliu, Brunilda

AU - Koslicki, David

AU - Skums, Pavel

AU - Zelikovsky, Alex

AU - Alkan, Can

AU - Mutlu, Onur

AU - Mangul, Serghei

N1 - Funding Information: B.D.S. is supported by NIH/NHLBI K08HL128867, P.S. is supported by NIH 1R01EB025022 and National Science Foundation grants 2047828, P.I.B. and S.K. are supported by the Molecular Basis of Disease (MBD), B.S. is supported by NIH R01HL149883 and NIH R01HL153122, O.M. is supported by Intel, VMware, and NIH HG006004, and S.M. is supported by National Science Foundation grant 2041984. The authors acknowledge the Computational Genomics Summer Institute (CGSI), funded by NIH GM112625, which fostered international collaboration among the groups involved in this project. Funding Information: We thank the authors of the tools surveyed in this work for providing helpful feedback and verifying the information related to their tool. We also thank Martin Frith (University of Tokyo), Heng Li (Harvard University), Cenk Sahinalp (National Cancer Institute), and Steven Salzberg (Johns Hopkins University) for their valuable feedback and discussion. Andrew Cosgrove was the primary editor of this article and managed its editorial process and peer review in collaboration with the rest of the editorial team. The peer review history is available as additional?file?2. Publisher Copyright: © 2021, The Author(s).

PY - 2021/12

Y1 - 2021/12

N2 - Aligning sequencing reads onto a reference is an essential step of the majority of genomic analysis pipelines. Computational algorithms for read alignment have evolved in accordance with technological advances, leading to today’s diverse array of alignment methods. We provide a systematic survey of algorithmic foundations and methodologies across 107 alignment methods, for both short and long reads. We provide a rigorous experimental evaluation of 11 read aligners to demonstrate the effect of these underlying algorithms on speed and efficiency of read alignment. We discuss how general alignment algorithms have been tailored to the specific needs of various domains in biology.

AB - Aligning sequencing reads onto a reference is an essential step of the majority of genomic analysis pipelines. Computational algorithms for read alignment have evolved in accordance with technological advances, leading to today’s diverse array of alignment methods. We provide a systematic survey of algorithmic foundations and methodologies across 107 alignment methods, for both short and long reads. We provide a rigorous experimental evaluation of 11 read aligners to demonstrate the effect of these underlying algorithms on speed and efficiency of read alignment. We discuss how general alignment algorithms have been tailored to the specific needs of various domains in biology.

UR - http://www.scopus.com/inward/record.url?scp=85113561622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85113561622&partnerID=8YFLogxK

U2 - 10.1186/s13059-021-02443-7

DO - 10.1186/s13059-021-02443-7

M3 - Review article

C2 - 34446078

AN - SCOPUS:85113561622

SN - 1474-7596

VL - 22

JO - Genome biology

JF - Genome biology

IS - 1

M1 - 249

ER -

Technology dictates algorithms: recent developments in read alignment

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this