LISA: A Case For Learned Index based Acceleration of Biological Sequence Analysis

Abstract

Next Generation Sequencing (NGS) is transforming fields like genomics, transcriptomics, and epigenetics with rapidly increasing throughput at reduced cost. This also demands overcoming performance bottlenecks in the downstream analysis of the sequencing data. A key performance bottleneck is searching for exact matches of entire or substrings of short DNA/RNA sequence queries in a long reference sequence database. This task is typically performed by using an index of the reference - such as FM-index, suffix arrays, suffix trees, hash tables, or lookup tables. In this paper, we propose accelerating this sequence search by substituting or enhancing the indexes with machine learning based indexes - called learned indexes - and present LISA (Learned Indexes for Sequence Analysis). We evaluate LISA through a number of case studies - that cover widely used software tools; short and long reads; human, animal, and plant genome datasets; DNA and RNA sequences; various traditional indexing techniques (FM-indexes, hash tables and suffix arrays) - and demonstrate significant performance benefits in a majority of them. For example, our experiments on real datasets show that LISA achieves speedups of up to 2.2 fold and 4.7 fold over the state-of-the-art FM-index based implementations for exact sequence search modules in popular tools bowtie2 and BWA-MEM2, respectively. Code availabilityLISA-based FM-index: https://github.com/IntelLabs/Trans-Omics-Acceleration-Library/tree/master/src/LISA-FMI LISA-based hash-table: https://github.com/IntelLabs/Trans-Omics-Acceleration-Library/tree/master/src/LISA-hash LISA applied to BWA-MEM2: https://github.com/bwa-mem2/bwa-mem2/tree/bwa-mem2-lisa.