Cognitive Correlative Encoding for Genome Sequence Matching in Hyperdimensional System

Abstract

Pattern matching is one of the key algorithms in identifying and analyzing genomic data. In this paper, we propose HYPERS, a novel framework supporting highly efficient and parallel pattern matching based on HyperDimensional computing (HDC). HYPERS transforms inherent sequential processes of pattern matching to highly-parallelizable computation tasks using HDC. HYPERS exploits HDC memorization to encode and represent the genome sequences using high-dimensional vectors. Then, it combines the genome sequences to generate an HDC reference library. During the matching, HYPERS performs alignment by exact or approximate similarity check of an encoded query with the HDC reference library. HYPERS functionality is supported by theoretical proof, verified by software implementation, and extensively tested on the existing hardware platform. Our evaluation on FPGA shows that HYPERS provides, on average, $ 17.5\times$ speedup and $ 39.4\times$ energy efficiency as compared to the state-of-the-art pattern matching tools running on GTX 1080 GPU.