Files
obikmer/UserDocMD/usage/estimate.md
T
Eric Coissac 36c7247acb feat: add k-mer sharing estimation and Poisson-binomial null model
Add a new `estimate --index` command to compare observed k-mer sharing against
a random-sequence model using a Poisson-binomial distribution. Introduce the
`row_presence_histogram` API to support this analysis across various matrix
types. Update documentation and dependencies accordingly.

- Add `src/obikstats/src/null_model.rs` implementing `SharingNullModel` and
  `SharingRow` for computing cumulative probabilities and false discovery rates
  based on a Poisson-binomial distribution.
- Add `src/obikstats/src/sharing.rs` defining `GenomeSharing` and `SharingSpectrum`
  to compute k-mer sharing spectra using parallel map-reduce.
- Add `src/obikmer/src/cmd/estimate/sharing.rs` with `run` and `write_csv` to
  execute sharing estimation and output CSV results containing observed, expected,
  and deviation metrics.
- Modify `src/obikmer/src/cmd/estimate/mod.rs` to support the new `--index`
  subcommand, adding `EstimateArgs` fields for index path, presence threshold,
  and output file.
- Add `src/obicompactvec/src/row_histogram.rs` implementing `row_presence_histogram`
  for `PersistentIntMatrix`, `PersistentBitMatrix`, and sparse matrices to count
  rows present in exactly $j$ columns.
- Update `src/obikindex/src/layer/content_layer.rs` and `src/obikindex/src/layer/typed_layer.rs`
  to expose the new `row_presence_histogram` method, dispatching based on layer type.
- Add tests in `src/obicompactvec/src/tests/bitmatrix.rs`, `intmatrix.rs`, and
  `sparse.rs` to verify `count_geq` and `row_presence_histogram` against naive
  implementations for various matrix structures.
- Update `UserDocMD/theory/kmer_indexing/kmers.md` to document the Poisson-binomial
  approach, $D_r$ bounds, and FDR calculations, replacing previous binomial approximations.
- Update `UserDocMD/usage/estimate.md` to describe the two uses of `estimate`:
  parameter estimation and index comparison via `--index`.
- Add `wiki` target to `Makefile` for regenerating documentation from user docs.
- Bump `obikmer` package version from 1.4.5 to 1.4.6 in `Cargo.toml` and `Cargo.lock`.
2026-11-19 17:50:29 +01:00

4.4 KiB

estimate

estimate has two independent uses. Without --index, it estimates approximate-index parameters (z, evidence bits, false-positive rate) before building an index with --approx, without touching any files. With --index, it compares the k-mer sharing observed in an existing index with the sharing expected by chance (see the last section).

obikmer estimate [OPTIONS]

Options

Option Default Description
-k, --kmer-size 31 Kmer size used at query time (matches index's --kmer-size)
-z, --findere-z none Findere z parameter
--evidence-bits none Fingerprint bits per slot (b)
--fp none Target false-positive rate per z-window

Any two of -z, --evidence-bits, --fp may be given; the third is derived using the same model as index --approx and convert --approx-evidence (FP = 1 / 2^{b \cdot z}). The report printed to stdout includes: query k, effective indexed k (k-z+1), z, evidence bits, per-kmer false-positive rate, and per-z-window false-positive rate.

Comparing an index with random sharing

obikmer estimate --index INDEX [--presence-threshold N] [-o FILE]

With --index, estimate reads an existing index instead of computing approximate-index parameters, and it cannot be combined with -k, -z, --evidence-bits or --fp. Its purpose is to tell how much of the k-mer sharing between the genomes of the index goes beyond what chance alone would produce, which is the question behind the choice of k (see K-mer size).

The command writes a CSV, to standard output or to FILE, with one row for each r from 1 to the number of genomes S:

Column Meaning
r Minimum number of genomes sharing a k-mer
k_r Number of k-mers present in at least r genomes
O_r Observed proportion k_r / k_1
q_r Proportion expected by chance, P(X \geq r \mid X \geq 1), where X is the number of genomes containing a given k-mer under the random-sequence model
D_r Deviation O_r - q_r
FP_r Number of k-mers expected to be present in at least r genomes by chance over the whole canonical k-mer space, M_k \, P(X \geq r)
FDR_r Estimated false discovery rate of the k-mers shared by at least r genomes: 1 when k_r is 0, otherwise \min(1, \mathrm{FP}_r / k_r)

A positive D_r means that k-mers are shared by at least r genomes more often than random sequences would share them; a negative value means less often. The first row always has D_1 = 0, because k_1 counts only k-mers present in at least one genome.

When no k-mer is shared by at least r genomes (k_r = 0), there is no set of k-mers whose false discovery rate could be estimated, and FDR_r is set to 1 by convention. This value means that nothing can be claimed at this level; it does not mean that the observed k-mers are false positives. The FP_r column of the same row shows how many k-mers chance alone would have produced.

The expected proportion is computed under the random-sequence model of the theory page: the genomes are unrelated, and each genome is a set of N_i distinct canonical k-mers drawn without replacement and uniformly from the M_k = 4^k/2 canonical k-mers. A given k-mer is then present in genome i with probability p_i = N_i / M_k = 2N_i/4^k, where N_i is the number of distinct canonical k-mers considered as present in genome i. Genome sizes are rarely known, in particular when the index was built from unassembled reads, and the number of distinct k-mers has the advantage of being measured on the index itself and of not depending on the sequencing coverage.

Because the N_i differ between genomes, the number X of genomes containing a k-mer follows an exact Poisson-binomial distribution, from which P(X \geq r) is obtained for every r in a single pass. The approximation by a binomial distribution based on the mean genome size is not used.

--presence-threshold (default 1) has the same meaning as in phylo: on an index that stores counts, a k-mer is present in a genome only when its count reaches the threshold. Both N_i and k_r are computed with this same threshold, so the observed and expected proportions describe the same data. It has no effect on an index without counts.

The k used is the k-mer size stored in the index (for an approximate index, the effective indexed size k-z+1).