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.
Benchmarks
Throughput, scaling, alignment cost.
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.
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 & calibrated cutoffs
One contiguous indel for V(D)J junctions, its position set by a prior rather than the
score alone; E-value inversion for the cutoff that achieves a target false-positive rate,
per query; and IslandProfile, a per-island PWM. Where the indel goes and how
close is close enough — both measured, not assumed.
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.