Abstract

Genomic similarity is a key metric in genomics, used in important tasks such as genome clustering and metagenomic profiling. One commonly-used approach is to treat each genome as a set of k-mers and to compute the Jaccard coefficient between each genome pair. However, computing the Jaccard coefficient between genomes in a large dataset is a computationally-challenging task. In this paper, we present an algorithm and accelerator architecture that uses an FPGA-as-a-service paradigm to compute the Jaccard similarity between pairs of genomes in large datasets using sketches and hardware acceleration in the cloud. The algorithm can compute the similarity between all genome pairs in the dataset, or it can use a selection criterion to reduce the amount of computation when only genome pairs with a Jaccard coefficient above a user-supplied threshold are of interest. After building the sketches, our heterogeneous accelerator can compute more than 96 million Jaccard coefficients per second running on an AWS EC2 f1.2xlarge instance with a Xilinx XCVU9P FPGA, which is 58 times faster than a state-of-the art software implementation that exploits SIMD instructions and thread-level parallelism on a compute-optimized EC2 c5.9xlarge instance with 36 hardware threads. The accelerator also computes similarities 27 times faster than a straightforward GPU-accelerated implementation of the Jaccard coefficient using sketches, and 4 times faster than an optimized GPU implementation of our algorithm, both running on an EC2 g5.4xlarge instance tailored with an NVIDIA A10G GPU. Furthermore, using a Jaccard coefficient threshold of 0.8 reduces the execution time of similarity computation to approximately one third in the hardware-accelerated and parallel software implementations, compared to computing the complete similarity matrix.(C) 2022 Elsevier B.V. All rights reserved.