Technology dictates algorithms: recent developments in read alignment.

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

Journal: Genome biology 2022;22(1):249

PMID: 34446078

Free Full Text on BioMed Central View on PubMed

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.

Address: Computer Science Department, ETH Zürich, 8092, Zürich, Switzerland.; Computer Engineering Department, Bilkent University, 06800 Bilkent, Ankara, Turkey.; Information Technology and Electrical Engineering Department, ETH Zürich, Zürich, 8092, Switzerland.; Department of Computer Science, University of California Los Angeles, Los Angeles, CA, 90095, USA.; Department of Clinical Pharmacy, School of Pharmacy, University of Southern California, Los Angeles, CA, 90089, USA.; Department of Epidemiology, Harvard T.H. Chan School of Public Health, Boston, MA, 02115, USA.; Program in Medical and Population Genetics, Broad Institute of MIT and Harvard, Cambridge, MA, 02142, USA.; Department of Computer Science, Georgia State University, Atlanta, GA, 30302, USA.; Bioinformatics Interdepartmental Ph.D. Program, University of California Los Angeles, Los Angeles, CA, 90095, USA.; Division of Pulmonary and Critical Care Medicine, Northwestern University Feinberg School of Medicine, Chicago, IL, 60611, USA.; Department of Biochemistry & Molecular Genetics, Northwestern University Feinberg School of Medicine, Chicago, USA.; Simpson Querrey Institute for Epigenetics, Northwestern University Feinberg School of Medicine, Chicago, IL, 60611, USA.; Department of Computational Medicine, University of California Los Angeles, Los Angeles, CA, 90095, USA.; Computer Science and Engineering, Pennsylvania State University, University Park, PA, 16801, USA.; Biology Department, Pennsylvania State University, University Park, PA, 16801, USA.; The Huck Institutes of the Life Sciences, Pennsylvania State University, University Park, PA, 16801, USA.; The Laboratory of Bioinformatics, I.M. Sechenov First Moscow State Medical University, Moscow, 119991, Russia.; Bilkent-Hacettepe Health Sciences and Technologies Program, Ankara, Turkey.; Department of Clinical Pharmacy, School of Pharmacy, University of Southern California, Los Angeles, CA, 90089, USA. [email protected].

DOI: 10.1186/s13059-021-02443-7

Link outs

Free resources

Full Text Sources:

MeSH Terms: Algorithms, Computational Biology, Genome, Human, HIV, Humans, Metagenomics, Sequence Alignment, Sulfites