ShiftCAM: A Time-Domain Content Addressable Memory Utilizing Shifted Hamming Distance for Robust Genome Analysis

Fast and efficient genome analysis can have a significant impact in areas such as scientific discovery and personalized medicine. Given the extensive data produced by sequencing machines, in-memory computing is considered a strong candidate to tackle the frequent data movement issue. Previous research has introduced many designs based on Content Addressable Memories (CAM), mainly optimized for tolerating edit distance; however, these systems struggle when there are a few insertion or deletion errors. This limitation presents a significant challenge for genome analysis, as current Third-Generation Sequencing still has high error rates. In this work, we introduce ShiftCAM, a time-domain Content Addressable Memory, designed to accommodate the high error rates in practical scenarios. Utilizing time-domain comparison, ShiftCAM effectively calculates the Shifted Hamming Distance to better approximate the computationally expensive edit distance. Additionally, the Modification to Accidental Match strategy specially designed for hardware implementation is introduced to eliminate accidental matches of single base pairs, further reducing false positives and improving edit distance approximation. Monte Carlo simulations based on physical ReRAM device statistical measurements and commercial PDK are also conducted to validate the robustness of the ShiftCAM design. Our experiments demonstrate that ShiftCAM can achieve an average of 2.1× (from 40.1% to 83.8%) higher F1 score in contamination analysis, 21.3% estimation error in relative abundance analysis, 51.2% reduction in cell area, 29.5× speed up, and 9.4× higher energy efficiency, compared to state-of-the-art in-memory DNA classification accelerators.