GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis

Damla Senol Cali; Gurpreet S. Kalsi; Zülal Bingöl; Can Firtina; Lavanya Subramanian; Jeremie S. Kim; Rachata Ausavarungnirun; Mohammed Alser; Juan Gomez-Luna; Amirali Boroumand; Anant Nori; Allison Scibisz; Sreenivas Subramoney; Can Alkan; Saugata Ghose; Onur Mutlu

Source-linked AI summary

GenASM: A High-Performance, Low-Power Approximate String Matching Acceleration Framework for Genome Sequence Analysis

Damla Senol Cali, Gurpreet S. Kalsi, Zülal Bingöl, Can Firtina, Lavanya Subramanian, Jeremie S. Kim, Rachata Ausavarungnirun, Mohammed Alser, Juan Gomez-Luna, Amirali Boroumand, Anant Nori, Allison Scibisz, Sreenivas Subramoney, Can Alkan, Saugata Ghose, Onur Mutlu

arXiv:2009.07692v1Sep 16, 2020cs.ARq-bio.GN

TL;DR

Approximate string matching is a major computational bottleneck in genome sequence analysis, whose data rates challenge existing systems. GenASM modifies Bitap and co-designs parallel, memory-efficient hardware acceleration for multiple ASM tasks, achieving substantial speed and power benefits across read alignment, filtering, and edit-distance calculation.

Problem
Approximate string matching bottlenecks genome sequence analysis because existing approaches scale quadratically in time and storage while sequencing data grows faster than computational capacity.
Method
GenASM modifies Bitap for long reads and intra-operation parallelism, adds traceback support, and co-designs the algorithms with area- and power-efficient hardware accelerators.
Results
GenASM is significantly faster and more power- and area-efficient than state-of-the-art software and hardware tools across read alignment, pre-alignment filtering, and edit-distance calculation.
Takeaways & Limitations
GenASM provides a flexible framework for accelerating multiple ASM uses in genome sequence analysis for both short and long reads.
Takeaways & Limitations
Baseline Bitap lacks traceback support for identifying optimal alignments, and GenASM can undercount edit distance when a deletion occurs in the query’s first character.

Abstract

from arXiv · show

Genome sequence analysis has enabled significant advancements in medical and scientific areas such as personalized medicine, outbreak tracing, and the understanding of evolution. Unfortunately, it is currently bottlenecked by the computational power and memory bandwidth limitations of existing systems, as many of the steps in genome sequence analysis must process a large amount of data. A major contributor to this bottleneck is approximate string matching (ASM). We propose GenASM, the first ASM acceleration framework for genome sequence analysis. We modify the underlying ASM algorithm (Bitap) to significantly increase its parallelism and reduce its memory footprint, and we design the first hardware accelerator for Bitap. Our hardware accelerator consists of specialized compute units and on-chip SRAMs that are designed to match the rate of computation with memory capacity and bandwidth. We demonstrate that GenASM is a flexible, high-performance, and low-power framework, which provides significant performance and power benefits for three different use cases in genome sequence analysis: 1) GenASM accelerates read alignment for both long reads and short reads. For long reads, GenASM outperforms state-of-the-art software and hardware accelerators by 116x and 3.9x, respectively, while consuming 37x and 2.7x less power. For short reads, GenASM outperforms state-of-the-art software and hardware accelerators by 111x and 1.9x. 2) GenASM accelerates pre-alignment filtering for short reads, with 3.7x the performance of a state-of-the-art pre-alignment filter, while consuming 1.7x less power and significantly improving the filtering accuracy. 3) GenASM accelerates edit distance calculation, with 22-12501x and 9.3-400x speedups over the state-of-the-art software library and FPGA-based accelerator, respectively, while consuming 548-582x and 67x less power.

1. Introduction

Genome sequence analysis is increasingly constrained by approximate string matching, which must process sequencing errors and genetic variation at growing data rates. GenASM modifies Bitap and co-designs hardware to accelerate multiple analysis steps for short and long reads.

Approximate string matching is a major read-mapping bottleneck because existing dynamic-programming approaches scale quadratically in time and storage while sequencing output grows faster than computational capacity.ASM also supports other bioinformatics tasks beyond read mapping.
GenASM modifies Bitap to support long reads and parallelize individual string-matching operations, then pairs the algorithms with an area- and power-efficient hardware accelerator.The framework also includes a Bitap-compatible traceback algorithm and specialized hardware components for bitvector generation and distance calculation.
GenASM is presented as the first work to enhance and accelerate Bitap for genome sequence analysis and as a faster, more power-efficient alternative to state-of-the-art software and hardware baselines.The contribution claims cover all three evaluated ASM use cases.
GenASM accelerates read alignment, pre-alignment filtering, and edit distance calculation across three genome-sequence-analysis use cases.The framework is evaluated for both short and long reads where applicable.
116× and 648× speedups over Minimap2 and BWA-MEM, respectively, were achieved for long-read alignment while reducing power consumption by 37× and 34×.These comparisons use 12-thread runs of the baseline alignment steps.

2. Background

Read mapping uses approximate string matching to compare sequencing reads with reference-genome regions despite insertions, deletions, and substitutions. Bitap represents matching state with bitvectors and bitwise operations, offering a lower-complexity alternative to quadratic dynamic programming.

2.1. Genome Sequence Analysis Pipeline: Read mapping indexes a reference, seeds candidate locations, filters dissimilar pairs, and aligns the remaining candidates to find the best match.Traceback is performed as part of the alignment step.
2.2. Approximate String Matching (ASM): Approximate string matching identifies query occurrences in a reference while allowing up to a specified edit-distance threshold.Edits include substitutions, deletions, and insertions, and traceback may be needed to identify an optimal alignment.
2.2. Approximate String Matching (ASM): Quadratic dynamic-programming ASM requires O(m × n) time and space, motivating lower-complexity alternatives.The cited examples include Levenshtein distance, Smith-Waterman, and Needleman-Wunsch.
2.3. Bitap Algorithm: Bitap computes approximate matches using pattern masks and status bitvectors for edit distances up to k, with exact matching when k is 0.The algorithm initializes bitmasks and status vectors, then processes text characters iteratively with bitwise operations.
2.3. Bitap Algorithm: Bitap combines deletion, insertion, substitution, and match information with bitwise operations to preserve potential match locations at each edit distance.The algorithm stores the combined result as the current status bitvector.

3. Motivation and Goals

GenASM addresses Bitap’s limitations for genome analysis by combining algorithmic modifications with specialized hardware, targeting long-read support, parallelism, traceback, and memory bottlenecks.

3.1. Limitations of Bitap on Existing Systems: Bitap implementations cannot handle long reads because word-sized bitvectors cannot represent queries spanning thousands to millions of base pairs.Supporting long reads requires multi-word queries and corresponding bitwise operations.
3.1. Limitations of Bitap on Existing Systems: Two levels of data dependency force Bitap’s consecutive text and edit-distance iterations to execute sequentially.Dependencies occur both across text iterations and within the inner loop over edit-distance iterations.
3.1. Limitations of Bitap on Existing Systems: Baseline Bitap finds possible matching locations but lacks traceback support for identifying the optimal alignment among multiple alternatives.The optimal alignment is defined by minimum edit distance or the highest score under a user-defined scoring function.
3.1. Limitations of Bitap on Existing Systems: CPU implementations are computation-limited by the small number of cores, while GPU implementations are bottlenecked by per-thread memory bandwidth and shared-cache interference.The GPU bottleneck is expected to worsen when traceback requires substantially higher bandwidth.
3.2. Our Goal: GenASM combines Bitap extensions with specialized hardware because modifying only the algorithm or only the hardware cannot overcome the identified limitations.The framework is designed to support fast, efficient, and flexible approximate string matching for both short and long reads.

4. GenASM: A High-Level Overview

GenASM co-designs distance calculation and traceback accelerators to process overlapping windows with parallel bitwise computation and dedicated SRAMs.

4. GenASM: A High-Level Overview: GenASM combines GenASM-DC for bitvector generation and minimum edit-distance calculation with GenASM-TB for traceback and optimal-alignment discovery.The two components are co-designed with an area- and power-efficient hardware accelerator.
4. GenASM: A High-Level Overview: GenASM-DC divides reference and query sequences into multiple overlapping windows before processing each sub-text and sub-pattern.The accelerator reads the sequences into dedicated DC-SRAM before windowed processing.
4. GenASM: A High-Level Overview: The GenASM hardware targets high parallelism and low memory footprint, using a systolic-array design for GenASM-DC’s regular bitwise operations.GenASM-TB uses simple logic for SRAM accesses and traceback control flow.
4. GenASM: A High-Level Overview: Figure 4 presents the overall GenASM framework architecture.The figure is identified as an overview of GenASM.

5. GenASM-DC Algorithm

GenASM-DC modifies Bitap to support long reads and expose parallelism, including parallel computation across independent bitvectors and overlapping text sub-sequences.

5. GenASM-DC Algorithm: GenASM-DC removes loop-carried dependencies and provides parallelism across the large number of Bitap iterations.These changes are central modifications to the baseline Bitap algorithm.
5. GenASM-DC Algorithm: Multi-word bitvectors let GenASM-DC support queries longer than the machine word size, including both short and long reads.The modification adds shift-related computation to transfer bits between adjacent words.
5. GenASM-DC Algorithm: The algorithm’s operation count scales with query length, word size, text length, and edit distance.The supplied complexity expression includes factors of m, w, n, and k.
5. GenASM-DC Algorithm: Independent bitvectors can be computed in parallel because each target depends only on specific neighboring vectors, not all surrounding iterations.Loop unrolling exposes this independence for parallel execution.
5. GenASM-DC Algorithm: Text-level parallelism divides the text into overlapping sub-texts and searches each sub-text concurrently.The overlap must have length m + k, where m is query length and k is the edit-distance threshold, to avoid missing boundary-spanning matches.

6. GenASM-TB Algorithm

GenASM-TB reconstructs optimal alignments from GenASM-DC bitvectors by traversing match, substitution, insertion, and deletion decisions. A divide-and-conquer windowing strategy reduces traceback storage while preserving accurate reconstruction.

Traceback operation: GenASM-TB finds the optimal alignment by examining each character in the matched region and selecting matches, substitutions, insertions, or deletions.It outputs the resulting sequence of operations and their positions as a CIGAR string.
Traceback operation: The traceback state tracks pattern position, text position, and remaining errors, updating these values according to the selected edit operation.Matches consume both sequences without changing the error count, while substitutions and indels decrement remaining errors.
Memory reduction: Divide-and-conquer windows reduce GenASM-TB’s memory footprint from ((m + k) × 4 × k × m) bits to (W × 4 × W × W) bits.Overlapping windows are merged to produce the complete traceback output.
Memory reduction: Storing only match, insertion, and deletion bitvectors further reduces memory and write bandwidth because the substitution bitvector can be derived by shifting deletion.The resulting storage requirement is (W × 3 × W × W) bits.
Windowing: GenASM-TB uses overlapping windows with W-O consumed characters so consecutive windows share O characters and preserve traceback accuracy.Window inputs are selected using the text and pattern consumption counts from the previous window.
Scoring schemes: GenASM-TB provides partial support for non-unit edit costs and affine gap penalties by changing traceback-case priority.Gap extensions are prioritized after an insertion or deletion, while edit cases can be ordered by penalty.

7. GenASM Hardware Design

GenASM hardware co-designs specialized accelerators, SRAM buffers, and 3D-stacked-memory placement for efficient approximate matching and traceback. GenASM-DC generates bitvectors and distances, while GenASM-TB reconstructs CIGAR strings from stored intermediate data.

GenASM-DC Hardware: GenASM-DC uses a linear cyclic systolic-array accelerator optimized to reduce memory bandwidth and footprint through feedback-based cyclic operation.The design fixes the required number of memory ports while supporting cyclic data reuse.
GenASM-DC Hardware: GenASM-DC processing elements execute approximate matching for w-bit query patterns, with their number chosen according to compute, area, bandwidth, and power requirements.Each processing element contains a processing core and flip-flop-based storage logic.
On-chip storage: GenASM uses DC-SRAM for inputs and intermediate data, and TB-SRAM for bitvectors consumed later by GenASM-TB.For a 64-PE configuration and a 10Kbp read with 15% errors, DC-SRAM requires 8KB.
GenASM-TB Hardware: GenASM-TB reads stored bitvectors under irregular control flow, performs bitwise comparisons, and computes the next SRAM address until the complete CIGAR string is produced.The accelerator then writes the output to main memory.
On-chip storage: A 64-PE configuration uses one 1.5KB TB-SRAM per processing element, totaling 96KB connected to one GenASM-TB accelerator.Each traceback cycle reads from only one TB-SRAM using indices derived from the traceback state.
3D-stacked-memory integration: GenASM places accelerators in the logic layer of 3D-stacked memory to parallelize across vaults or pseudo-channels and reduce off-chip data movement.An example 16GB HMC-like system uses one GenASM-DC accelerator, DC-SRAM, GenASM-TB accelerator, and TB-SRAMs within each of 32 vaults.

8. GenASM Framework

GenASM is a flexible approximate string matching framework built around modified Bitap algorithms and hardware support for multiple genome-analysis tasks. Its use cases include read alignment, short-read pre-alignment filtering, and edit-distance calculation.

Use cases: GenASM targets three approximate-matching use cases: short- and long-read alignment, short-read pre-alignment filtering, and edit-distance calculation.The framework is presented as applicable to multiple steps of the genome sequence analysis pipeline.
Read alignment: Read alignment uses the full GenASM pipeline, including traceback, and supports short and long reads with configurable edit costs.GenASM-TB is configured for the scoring scheme used by the alignment task.
Pre-alignment filtering: GenASM-DC can serve as a short-read pre-alignment filter by estimating edit distance and testing it against a user-defined threshold.This use case benefits from Bitap’s O(m × n × k) complexity for shorter sequences and low error thresholds.
Scope: Evaluation of GenASM as a long-read pre-alignment filter is left for future work.
Edit distance calculation: GenASM supports edit-distance calculation between arbitrary-length genomic sequences, with traceback optional for this use case.GenASM-DC and GenASM-TB cooperate to exploit divide-and-conquer, although traceback output is not generated by default.

9. Evaluation Methodology

The evaluation combines synthesis-based hardware modeling, analytical performance modeling, benchmark comparisons, and datasets spanning read alignment, pre-alignment filtering, and edit-distance calculation. Comparisons use software, GPU, FPGA, and hardware alignment baselines under specified workloads and system assumptions.

Hardware evaluation: GenASM hardware is evaluated with 28nm synthesis and place-and-route targeting 1GHz, plus cycle-accurate simulation driven by synthesized datapath and memory estimates.
Hardware evaluation: The modeled platform is a 16GB HMC-like 3D-stacked DRAM with 32 vaults, 256GB/s internal bandwidth, 1.25GHz clock, and 312mW per-vault logic power budget.
Performance modeling: The performance model projects cycles, DRAM and SRAM bandwidth, and memory footprint from sequence lengths, error bounds, window size, hardware parameters, and vault count.
Read-alignment benchmarks: Read-alignment comparisons use Minimap2, BWA-MEM, GASAL2, GACT, and SillaX across CPU, GPU, and hardware baselines.CPU software baselines are measured with one and twelve threads, while power and execution time are collected for alignment steps.
Filtering benchmarks: Pre-alignment filtering is compared with Shouji using reported execution-time and accuracy data and synthesized power estimates.
Datasets: Datasets include GRCh38, simulated 10Kbp PacBio and ONT reads at 10% and 15% error rates, Illumina reads, short-read filtering cases, and 100Kbp-to-1Mbp edit-distance sequences.

10. Results

GenASM delivers substantial speed, power, area, and accuracy benefits across read alignment and pre-alignment filtering, enabled by modified Bitap algorithms and specialized hardware.

Hardware Implementation: GenASM's accelerator occupies 0.334 mm2 and consumes 101 mW per accelerator, while 32 accelerators total 10.69 mm2 and 3.23 W.The design uses GenASM-DC and GenASM-TB components operating at 1GHz.
Read Alignment: 7173× and 648× throughput improvement over BWA-MEM, and 1126× and 116× over Minimap2, for single-thread and 12-thread long-read alignment.GenASM also reduces long-read alignment power relative to 12-thread BWA-MEM and Minimap2 by 34× and 37×, respectively.
Read Alignment: 1390× and 111× throughput improvement over BWA-MEM, and 1839× and 158× over Minimap2, for single-thread and 12-thread short-read alignment.Short-read alignment power is reduced by 16× and 18× versus single-thread baselines, and by 33× and 31× versus 12-thread baselines.
Read Alignment: 1.9× higher throughput than SillaX for 101bp short reads, with 63% less logic area and 82% less logic power.GenASM requires 17% more total area than SillaX after including SRAM.
Read Alignment: 96.6% of short reads match BWA-MEM's alignment score exactly, while 99.6% and 99.7% of long reads remain within ±0.4% and ±0.7% of Minimap2 scores at 10% and 15% error rates.The reported score differences arise from minimum-edit-distance traceback and fixed error-type selection during traceback.

11. Other Use Cases of GenASM

The paper discusses additional potential applications of GenASM beyond its three evaluated use cases, including assembly, indexing, whole-genome alignment, and broader sequence or text search.

Scope: The paper quantitatively evaluates three approximate-string-matching use cases and leaves four additional potential use cases for future work.
Read-to-Read Overlap Finding: GenASM may accelerate read-to-read overlap finding, whose final step performs pairwise read alignment.
Hash-Table Based Indexing: GenASM can generate hash-table indices by finding reference locations for fixed-length seed substrings.
Whole Genome Alignment: GenASM can support whole-genome alignment because its divide-and-conquer approach operates on arbitrary-length sequences.
Generic Text Search: GenASM-DC can extend beyond DNA by generating pattern bitmasks for larger alphabets without changing edit-distance calculation.The paper identifies RNA and protein sequence alignment as examples of this broader use.

12. Related Work

Prior genome-analysis accelerators generally target one pipeline step, whereas GenASM is designed to support multiple approximate-string-matching use cases.

12. Related Work: GenASM is presented as the first framework to enhance and accelerate Bitap for approximate string matching.The framework is positioned as a multi-use-case alternative to prior single-step acceleration efforts.
12. Related Work: Prior approaches primarily use heuristic pre-alignment filters or hardware accelerators for computationally expensive read alignment.Examples include CPU, SIMD, and 3D-stacked-memory filters, alongside ReRAM- and processing-in-memory-based accelerators.
12. Related Work: GenASM accelerates at least three approximate-string-matching use cases, unlike prior works that focus on a single genome-analysis step.The supported use cases are read alignment, pre-alignment filtering, and edit-distance calculation.

13. Conclusion

GenASM combines a modified Bitap algorithm with co-designed hardware to accelerate approximate string matching across genome-analysis tasks. The framework is evaluated on three use cases for short and long reads and is reported as faster and more power- and area-efficient than state-of-the-art software and hardware tools.

13. Conclusion: GenASM evaluates modified Bitap algorithms and co-designed hardware on read alignment, pre-alignment filtering, and edit-distance calculation.The evaluation covers both short and long reads.
13. Conclusion: GenASM is reported as significantly faster and more power- and area-efficient than state-of-the-art software and hardware tools across these use cases.