Lightning-fast adaptive immune receptor similarity search by symmetric deletion lookup

An individual's adaptive immune receptor (AIR) repertoire records immune history due to the receptors' antigen specificity. Reading this record requires computational approaches for inferring receptor function from sequence, as the diversity of possible receptor-antigen pairs vastly outstrips experimental knowledge. Identification of AIRs with similar sequence and thus putatively similar function is a common performance bottleneck in these approaches. Here, we benchmark the runtime scaling of five algorithmic approaches to radius-based search for Levenshtein neighbors. We show that a symmetric deletion lookup approach, originally proposed for spell-checking, is particularly scalable. We introduce SymScan and XTNeighbor, optimized CPU and GPU software implementing a parallelized variant of the algorithm. For one million input sequences, these tools identify all sequence pairs that differ by one or two edits in seconds, orders of magnitude faster than existing approaches. We demonstrate how symmetric deletion lookup can be integrated as a pre-filtering step in T cell receptor metaclone discovery and B cell receptor lineage identification. Our contribution is poised to greatly accelerate existing analysis pipelines and enable processing of immunosequencing data at scale.