SymScan

SymScan enables extremely fast discovery of pairs of similar strings within and across large collections.

SymScan is a variation on the symmetric deletion algorithm that is optimised for bulk-searching similar strings within one or across two large string collections at once (e.g. searching for similar protein sequences among a collection of 10M). The key algorithmic difference between SymScan and traditional symmetric deletion is the use of a sort-merge join approach in place of hash maps to discover input strings that share common deletion variants. This sort-and-scan approach trades off an additional factor of O(log N) (with N the total number of strings being compared) in expected time complexity for improved cache locality and effective parallelization, and ends up being much faster for the above use case.

brew install yutanagano/tap/symscan-cli

Or install from crates.io:

cargo install symscan-cli

brew install yutanagano/tap/symscan-airr

Or install from crates.io:

cargo install symscan-airr

cargo add symscan

pip install symscan

SymScan takes in a list of strings (one per line) via stdin, and returns which ones are within one Levenshtein edit (the default) of each other. Each output line is <line 1>,<line 2>,<edit distance> (1-indexed):

$ echo $'fizz\nfuzz\nbuzz\nfizzy' | symscan
1,2,1
1,4,1
2,3,1

See the CLI docs for options like -d (max distance), -z (0-indexed output), --hamming, and searching across two files.

Given an AIRR-compliant TSV of rearrangements, symscan-airr reports duplicate-count-weighted overlap between repertoires:

$ cat > example.tsv <<'EOF'
junction_aa	duplicate_count	repertoire_id
CAVSTSGGSYIPTF	1	a
CAVHASGGSYIPTF	1	a
CAVSTSGGSYIPTF	1	b
CAVRLSGGSYIPTF	2	b
EOF
$ symscan-airr example.tsv
a	a	2
a	b	1
b	b	5
$ < example.tsv symscan-airr
a	a	2
a	b	1
b	b	5

See the AIRR docs for options like -d, --hamming, --locus, custom column names, and comparing repertoires across two files.

use symscan::{get_neighbors_within, NeighborPairs};

let query = ["fizz", "fuzz", "buzz", "fizzy"];
let NeighborPairs { row, col, dists } = get_neighbors_within(&query, 1).unwrap();

assert_eq!(row,   vec![0, 0, 1]);
assert_eq!(col,   vec![1, 3, 2]);
assert_eq!(dists, vec![1, 1, 1]);

See the crate docs for searching across two collections and the memoized CachedRef API.

>>> import symscan
>>> row, col, dists = symscan.get_neighbors_within(["fizz", "fuzz", "buzz", "fizzy"])
>>> row
array([0, 0, 1], dtype=uint32)
>>> col
array([1, 3, 2], dtype=uint32)
>>> dists
array([1, 1, 1], dtype=uint8)

See the Python docs for searching across two collections and the memoized CachedRef API.

SymScan is dual-licensed under the MIT and Apache 2.0 licenses. Unless explicitly stated otherwise, any contribution submitted by you, as defined in the Apache license, shall be dual-licensed as above, without any additional terms and conditions.

Please cite our preprint.

@misc{chotisorayuth_lightning-fast_2026,
	title = {Lightning-fast adaptive immune receptor similarity search by symmetric deletion lookup},
	url = {http://arxiv.org/abs/2403.09010},
	doi = {10.48550/arXiv.2403.09010},
	urldate = {2026-09-23},
	publisher = {arXiv},
	author = {Chotisorayuth, Touchchai and Nagano, Yuta and Tiffeau-Mayer, Andreas},
	month = sep,
	year = {2026},
	note = {arXiv:2403.09010 [q-bio.QM]},
	keywords = {Quantitative Biology - Genomics, Quantitative Biology - Quantitative Methods},
}