Shouji: A Fast and Efficient Pre-Alignment Filter for Sequence Alignment

Abstract

Motivation: The ability to generate massive amounts of sequencing data continues to overwhelm the processing capability of existing algorithms and compute infrastructures. In this work, we explore the use of hardware/software co-design and hardware acceleration to significantly reduce the execution time of short sequence alignment, a crucial step in analyzing sequenced genomes. We introduce Shouji, a highly-parallel and accurate pre-alignment filter that remarkably reduces the need for computationally-costly dynamic programming algorithms. The first key idea of our proposed pre-alignment filter is to provide high filtering accuracy by correctly detecting all common subsequences shared between two given sequences. The second key idea is to design a hardware accelerator that adopts modern FPGA (Field-Programmable Gate Array) architectures to further boost the performance of our algorithm. Results: Shouji significantly improves the accuracy of pre-alignment filtering by up to two orders of magnitude compared to the state-of-the-art pre-alignment filters, GateKeeper and SHD. Our FPGA-based accelerator is up to three orders of magnitude faster than the equivalent CPU implementation of Shouji. Using a single FPGA chip, we benchmark the benefits of integrating Shouji with five state-of-the-art sequence aligners, designed for different computing platforms. The addition of Shouji as a pre-alignment step reduces the execution time of the five state-of-the-art sequence aligners by up to 18.8x. Shouji can be adapted for any bioinformatics pipeline that performs sequence alignment for verification. Unlike most existing methods that aim to accelerate sequence alignment, Shouji does not sacrifice any of the aligner capabilities, as it does not modify or replace the alignment step. Availability: https://github.com/CMU-SAFARI/Shouji

https://academic.oup.com/bioinformatics/advance-article-abstract/doi/10.1093/bioinformatics/btz234/5421509, Bioinformatics Journal 2019

References in corpus (6)

• Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM
• 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
• ASAP: Accelerated Short-Read Alignment on Programmable Hardware
• MAGNET: Understanding and Improving the Accuracy of Genome Pre-Alignment Filtering

Cited by in corpus (14)

• Technology dictates algorithms: Recent developments in read alignment
• Accelerating Genome Analysis: A Primer on an Ongoing Journey
• Apollo: A Sequencing-Technology-Independent, Scalable, and Accurate Assembly Polishing Algorithm
• In-DRAM Bulk Bitwise Execution Engine
• SneakySnake: A Fast and Accurate Universal Genome Pre-Alignment Filter for CPUs, GPUs, and FPGAs
• SeGraM: A Universal Hardware Accelerator for Genomic Sequence-to-Graph and Sequence-to-Sequence Mapping
• Scrooge: A Fast and Memory-Frugal Genomic Sequence Aligner for CPUs, GPUs, and ASICs
• 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
• Enabling Practical Processing in and near Memory for Data-Intensive Computing
• A Workload and Programming Ease Driven Perspective of Processing-in-Memory
• Processing-in-memory for genomics workloads
• DNA Pre-alignment Filter using Processing Near Racetrack Memory
• Accelerating the Understanding of Life's Code Through Better Algorithms and Hardware Design