Sibling annex & SNP-family pipeline — architecture
Current state of obikphylo::siblings (crate obikphylo, module siblings).
Historical rationale, dated findings, and superseded designs live in jj
history, not here.
Data model
A family is the up-to-4 k-mers sharing all flanks and differing only at
the central base (well-defined for odd k). FamilyMask (siblingannex.rs)
is a 4-bit presence mask (bit b set iff the family member whose own
canonical central base is b is observed anywhere in the index) plus a
minorant flag; family_size()/siblings() derive member count from it.
SiblingAnnex/SiblingAnnexBuilder persist one FamilyMask per k-mer,
keyed by iteration order (the physical layout of unitigs.bin), never by
MPHF slot — this lets every reader zip-iterate a layer's own k-mer stream
against the annex file directly, no MPHF/slot indirection.
Construction
algorithms::annex::build_layer_sibling_annex builds one layer's annex:
seeds each k-mer's own central base, generates its up-to-3 central-base
variants, resolves each cross-partition (IndexCache::find_in_partition,
grouped and chunked per destination partition for mmap locality), writes the
final mask (with the minorant flag) in a second streamed pass.
SiblingExt::build_sibling_annex drives this for every layer of every
partition, then invalidates and rebuilds the entropy and family-overlap
annexes (their family_idx numbering depends on the sibling annex).
Shared traversal
algorithms::family_scan::scan_layer_families is the only place that
resolves a family's full per-genome presence (genome_mask: &[u8],
cross-partition) — every other consumer in this module is built on it, never
reimplements the resolution. Two decoupled concurrency mechanisms: batch
generation (CPU-only) runs on an obipipeline throttle/pipe; per-batch
resolution (I/O-bound, mmap page faults) runs rayon-parallel across
destination partitions, one generated batch at a time (never several
concurrently, to keep one partition's pages hot instead of scattering
access). fast_mode (is_fast_mode, <= 7 layers per partition) picks
between trusting a family member's recorded layer index outright or probing
every layer of the destination partition.
Selection<'a> bounds which families of a layer are resolved:
All— every minorant, monomorphic included (SiblingExt::shannon_entropy_csv,sibling_annex_stats).Some(&HashSet<usize>)— a caller-picked subset, skipping the expensive cross-partition resolution entirely for excluded families (subsample::sample_layer's accepted-candidates batch;entropy::ensure_layer_entropy_annex's non-monomorphic-only restriction).
minorant_selection::eligible_bitset_layer/non_monomorphic_reindex_layer
provide the cheap, annex-bits-only (no cross-partition resolution) filters
these restricted scans are built from: monomorphism (family_size() < 2) is
knowable straight from the annex, so nothing pays scan_layer_families's
resolution cost just to discard a monomorphic result.
Masking — computed once, shared everywhere
algorithms::masking::masked_state(m, free_loss, no_ambiguity) is the single
function that turns a raw per-genome 4-bit state into the masked view every
consumer needs (None for absence under --free-loss or ambiguity under
--no-ambiguity). It is called exactly once per (family, genome), in
subsample::sample_layer, immediately after scan_layer_families resolves
the raw state — never recomputed downstream. survives_masking (does the
family still carry ≥2 distinct masked states among included genomes?) and
SurvivingFamily::masked: Vec<Option<u8>> both consume this same
precomputed array, which is also what AlignmentReducer/PairwiseReducer
read (see below) — this is what guarantees the alignment and the pairwise
tally can never disagree about a genome's state at a given site.
Precomputed annexes (entropy, family overlap)
algorithms::entropy::ensure_layer_entropy_annex builds EntropyAnnex
(entropy_annex.rs, one f32 Shannon-entropy value per non-monomorphic
minorant, mmap-backed) and/or feeds FamilyOverlapAccumulator
(family_overlap.rs) from one shared Selection::Some scan — both need the
same genome_mask resolution, so a missing one never pays for it twice.
family_entropy (15 non-empty states of {A,C,G,T}'s powerset, ∅
excluded from the denominator — the project's settled informativeness
definition, matching the calibrated 16-state Sankoff cost matrix) and
family_entropy_4 (plain 4-symbol reduction, kept only for comparison) are
pure functions of genome_mask. extensions::SiblingBuilder::ensure_entropy_and_overlap_annexes
drives this for every cached layer, lazily (only what's missing).
Sampling and the shared scan trunk
algorithms::subsample::sample_index draws up to n non-monomorphic
families index-wide, proportionally per layer: for each layer, a target
quota sized from that layer's share of the index-wide eligible count, filled
by a circular walk with a Bernoulli(p) draw per candidate — p optionally
weighted by an unnormalized Gaussian kernel over the candidate's entropy
(EntropyBias { mu, sigma }, read from the entropy annex). Accepted
candidates are resolved in batches (scan_layer_families) and checked
against survives_masking; rejected-after-masking candidates don't count
toward quota, triggering further "topup" rounds (bounded, MAX_TOPUP_ROUNDS
= 5) rather than silently under-filling. Every SurvivingFamily reaching a
caller has already survived both the draw and post-masking informativeness —
no second filter pass needed downstream.
algorithms::scan::sampled_scan is the single entry point every sampled
computation goes through: one sample_index pass, fanned out to whichever
LayerReducer implementations the caller actually needs, each receiving the
exact same per-layer SurvivingFamily batch (an Arc, cloned not copied).
This is what guarantees several outputs requested together
(--pseudo-alignment and --sankoff and a snp-* --distance in one CLI
invocation) come from one random sample, not independently-drawn ones —
there is no other driver of sample_index anywhere in this crate.
Two LayerReducer implementations exist today:
AlignmentReducer(alignment.rs) — accumulatesSnpAlignment(one IUPAC-coded row per included genome), readingfamily.maskeddirectly.PairwiseReducer(pairwise.rs) — accumulatesPairwiseTally/PartitionDispersion, also readingfamily.maskeddirectly (substitution/ agreement counts and cardinality both derive from the same masked state the alignment uses).
From a tally to distances and calibration
PairwiseTally stores per-genome-pair substitution/agreement/cardinality
counts, unfiltered, from which every downstream output is cheap O(n²)
post-processing (never a second scan):
algorithms::snp_distance::distance_matrix— closed-formsnp-*corrections (raw p-distance, JC69, K80, K81, F81, T92, TN93, transversions- only), optionally gamma-corrected (GammaShape,PartitionDispersion::estimate_alphaforAuto).algorithms::sankoff::SankoffBundle::finish— assembles the--sankoff/--tnt/--phyg/--iqtreepipeline's inputs (RawSnpDistanceOutput,BasePairTally,CardinalityTally) from an already-scannedAlignmentReducer/PairwiseReducerpair, plusSankoffBundle::snp_distanceto reuse that exact sample for asnp-*--distancein the same invocation without a second scan.algorithms::cardcomp— pure functions turningCardinalityTally/BasePairTallyinto row-stochastic transition probability matrices, then the calibrated 16-state Sankoff cost matrix (pairwise_cost_matrix).
Public API surface
extensions::SiblingExt (CLI-facing trait on IndexCache) covers only the
operations with no cross-invocation sharing concern: build_sibling_annex,
shannon_entropy_csv, sibling_family_size_histogram/sibling_annex_stats,
family_overlap. The sampled SNP path (sampled_scan, AlignmentReducer,
PairwiseReducer, distance_matrix, SankoffBundle) is not wrapped in
trait methods — the CLI (obikmer::cmd::phylo) composes them directly,
because it alone knows the union of reducers a given invocation needs
(--pseudo-alignment/Sankoff group/snp-* --distance can combine in one
call). A per-output trait method would have to either duplicate that
composition logic or reintroduce the "two independent scans" problem this
design replaced.
Known gaps
sample_index'sskip_layersparameter (checkpointed-resume support) is never called with a non-zero value by any current caller —--sessionpersistence was removed pending a redesign on top ofsampled_scan(single shared trunk, not per-driver checkpoint plumbing). The parameter stays as the seam a future resume mechanism would use.- No cheap entropy pre-filter exists yet for the very high (saturated) tail — a row-marginal coverage approximation was considered and rejected (cannot represent joint multi-base co-occurrence, which is exactly what the 15-state entropy definition exists to capture).