Struct BkTree 

pub struct BkTree { /* private fields */ }

BK-tree for efficient Hamming distance queries on UMIs.

A BK-tree (Burkhard-Keller tree) is a metric tree that exploits the triangle inequality to efficiently find all strings within a given edit distance. For Hamming distance queries with threshold k, it achieves O(k * log n) average case complexity instead of O(n) for linear scan.

This implementation uses BitEnc for O(1) Hamming distance computation.

Algorithm

The tree is built by inserting UMIs one by one:

1. The first UMI becomes the root
2. For each subsequent UMI, traverse from root following edges labeled with the Hamming distance to each node’s UMI
3. Insert as a new child when no edge exists for that distance

To query for all UMIs within distance k of a query:

1. Compute distance d from query to current node
2. If d <= k, include this node in results
3. Recursively search children with edge labels in range [d-k, d+k] (triangle inequality guarantees other children can’t contain matches)

Implementations

impl BkTree

pub fn new() -> BkTree

Create a new empty BK-tree.

pub fn from_umis(umis: &[(usize, &str)]) -> Option<BkTree>

Build a BK-tree from a list of UMIs with their indices.

Returns None if any UMI contains non-ACGT bases (cannot be encoded).

pub fn find_within(&self, query: &str, max_distance: u32) -> Vec<(usize, u32)>

Find all UMIs within the given Hamming distance of the query.

Returns a vector of (index, distance) pairs for all matching UMIs. Returns empty if query cannot be encoded (contains non-ACGT bases).

pub fn len(&self) -> usize

Returns the number of UMIs in the tree.

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Trait Implementations

impl Default for BkTree

fn default() -> BkTree

Returns the “default value” for a type.