Accelerating Genome Analysis: A Primer on an Ongoing Journey

Abstract

Genome analysis fundamentally starts with a process known as read mapping, where sequenced fragments of an organism's genome are compared against a reference genome. Read mapping is currently a major bottleneck in the entire genome analysis pipeline, because state-of-the-art genome sequencing technologies are able to sequence a genome much faster than the computational techniques employed to analyze the genome. We describe the ongoing journey in significantly improving the performance of read mapping. We explain state-of-the-art algorithmic methods and hardware-based acceleration approaches. Algorithmic approaches exploit the structure of the genome as well as the structure of the underlying hardware. Hardware-based acceleration approaches exploit specialized microarchitectures or various execution paradigms (e.g., processing inside or near memory). We conclude with the challenges of adopting these hardware-accelerated read mappers.

arXiv commentThis is an extended and updated version of a paper published in IEEE Micro, vol. 40, no. 5, pp. 65-75, 1 Sept.-Oct. 2020, https://doi.org/10.1109/MM.2020.3013728

References in corpus (7)

• Minimap2: pairwise alignment for nucleotide sequences
• Nanopore Sequencing Technology and Tools for Genome Assembly: Computational Analysis of the Current State, Bottlenecks and Future Directions
• GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies
• GateKeeper: A New Hardware Architecture for Accelerating Pre-Alignment in DNA Short Read Mapping
• Shouji: A Fast and Efficient Pre-Alignment Filter for Sequence Alignment
• SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
• ASAP: Accelerated Short-Read Alignment on Programmable Hardware

Cited by in corpus (9)

• Technology dictates algorithms: Recent developments in read alignment
• FPGA-Based Near-Memory Acceleration of Modern Data-Intensive Applications
• SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
• Hamming Distance Tolerant Content-Addressable Memory (HD-CAM) for Approximate Matching Applications
• Scrooge: A Fast and Memory-Frugal Genomic Sequence Aligner for CPUs, GPUs, and ASICs
• FiltPIM: In-Memory Filter for DNA Sequencing
• GateKeeper-GPU: Fast and Accurate Pre-Alignment Filtering in Short Read Mapping
• MARS: Processing-In-Memory Acceleration of Raw Signal Genome Analysis Inside the Storage Subsystem
• AirLift: A Fast and Comprehensive Technique for Remapping Alignments between Reference Genomes