seqtree#
FUZZY SEQUENCE SEARCH
seqtree finds biological sequences (amino-acid or nucleotide) within a fixed edit scope or score budget. Build an immutable index once, then search single queries or millions of queries in parallel. C++ core, minimal Python binding.
Getting Started
Install, build an index, run your first search.
Engines & Concepts
seqtm vs seqtrie, scope vs budget, scoring.
API Reference
Index, matrices, gap-block scoring, E-values.
Text Search
k-mismatch search over a proteome, one index for every query length.
seqtm — branch-and-bound
Exact per-type edit caps (subs / ins / dels), a fast Hamming-only path, and an exact edit-type breakdown per hit. The workhorse for small edit distances: UMI collapse, CDR3 error correction, CDR3/epitope matching.
seqtrie — banded DP
Matrix-weighted score budgets (BLOSUM62 + gap costs) with cost independent of the edit count. Best for similarity-scored searches over a total-edit or penalty budget.
TextIndex — search a proteome
Exact k-mismatch search over a concatenated text, where a trie over reference
strings would need one build per query length. k belongs to the index, so
one build answers every length and every max_subs: a 9-mer within 2
substitutions of the human proteome in 1.3 ms on one thread.
Pairwise alignment, no BioPython
Needleman–Wunsch and Smith–Waterman with affine or linear gaps, verified
against Bio.Align.PairwiseAligner as an oracle with zero disagreements —
and 65–87× faster.
Gap blocks for V(D)J junctions
One contiguous indel, its position set by a prior rather than by the score alone —
exactly optimal against unrestricted affine alignment on 98.8% of related
pairs. IslandProfile adds a per-island PWM over the same scale.
Calibrated cutoffs, not fixed ones
E-values counted against a background control, inverted into the score cutoff that achieves a target false-positive rate per query. A control repertoire is dense near germline and sparse among rare junctions, so one fixed threshold buys a common query far more chance neighbours than a rare one.
Every number on this site is reproducible: see Benchmarks for throughput, thread scaling, recall against ground truth, and the scripts that produce each figure.
Results are payload-agnostic — (ref_id, score, n_subs, n_ins, n_dels). Downstream libraries
map ref_id back to their own payloads (V gene, MHC, read counts) and filter there.