Files
Eric Coissac 0d12494f1a Refactor indexing, sampling, and entropy documentation
This commit introduces new theoretical frameworks for k-mer indexing, pair coverage sampling, and sibling partition unification. It also implements new algorithms for calculating family entropy and statistical tests for overlap analysis. Documentation is updated across the board to reflect these new features and theoretical concepts.
2026-10-13 08:54:21 +02:00

5.6 KiB

Chance sharing of a kmer across genomes (discussion)

Null model for "a kmer is present in r of S genomes": how likely is this by chance alone? Extends the single-pair estimate P_{\mathrm{chance}}\simeq G/4^k (see user doc, K-mer specificity).

Homogeneous case: binomial tail

If every genome has the same per-genome chance probability p, the number R of genomes containing a given kmer is \mathrm{Bin}(S,p):

P(R\geq r)=\sum_{j=r}^{S}\binom{S}{j}p^j(1-p)^{S-j}=I_p(r,\,S-r+1)

where I_p is the regularized incomplete beta function. No elementary closed form; use I_p directly.

Numerical evaluation of the sum

  • Term recurrence, one lgamma start: t_{j+1}=t_j\cdot\frac{S-j}{j+1}\cdot\frac{p}{1-p}.
  • Sum the tail not containing the mode (Sp, not S/2). If r>Sp, sum \sum_{j\ge r} directly and stop when terms are negligible. The complement 1-\sum_{j=0}^{r-1} (note: from j=0) suffers catastrophic cancellation when the p-value is tiny.
  • Large S: normal approximation with continuity correction, or Poisson(Sp) when p is small. Unreliable in extreme tails.

Heterogeneous case: p_i = f(G_i)

The G_i (number of kmers of genome i) are known and differ. With p_i\simeq G_i/4^k, the indicators "kmer present in genome i by chance" are independent Bernoulli(p_i), so R follows a Poisson-binomial law, not a binomial:

P(R=j)=\sum_{|A|=j}\prod_{i\in A}p_i\prod_{i\notin A}(1-p_i).

Everything lives in canonical space: G_i is the number of distinct canonical kmers of genome i, and the kmer space has size

N=\frac{4^k}{2}

exactly, since k is odd (no kmer equals its own reverse complement, so canonicalization pairs the 4^k kmers perfectly). Exact per-genome probability: p_i=1-(1-1/N)^{G_i}\simeq 2G_i/4^k. This is twice the G/4^k of the user doc, where G is a number of positions on one strand.

Exact computation

Dynamic programming over genomes, d_j = probability of j hits so far:

d'_j=d_j(1-p_i)+d_{j-1}p_i.

For the upper tail only d_0\ldots d_{r-1} are needed: P(R\ge r)=1-\sum_{j<r}d_j, cost O(S\,r), per distinct (p_1..p_S) vector — independent of the kmer, so computed once per index (table of P(R\ge r) for r=1..S), not per kmer. Cancellation caveat as above: for tiny tails compute \Pr(R\ge r) by the DP on the upper side (track d_j for j\ge r only from a top-down recurrence) or in log space. Alternative: DFT of the characteristic function (Hong 2013), O(S^2) exact.

Approximations

  • Poisson: R\approx\mathrm{Poisson}(\lambda=\sum_i p_i) with total variation error \le\sum_i p_i^2 (Le Cam). Excellent when all p_i\ll1, i.e. 4^k\gg G_i (large k).
  • Binomial with mean $\bar p=\frac1S\sum_i p_i$: Hoeffding (1956) shows the Poisson-binomial is more concentrated than \mathrm{Bin}(S,\bar p). Hence for r\ge S\bar p+1, P_{\mathrm{PB}}(R\ge r)\le P_{\mathrm{Bin}}(R\ge r): using the mean \bar G overestimates the chance probability, i.e. is conservative in the upper tail. Wrong direction for r\le S\bar p (lower tail), irrelevant for significance testing.

Consequence: assuming a common G is safe (conservative) if G=\bar G (arithmetic mean), but loses power when genome sizes span orders of magnitude; the exact DP is cheap enough (once per index) to make the approximation unnecessary. Small genomes with k=11 saturate (p_i\to1) and break the Poisson approximation, not the DP.

Open points

  • Repeats are not a problem. The model is presence/absence per genome, so copy number within a genome is irrelevant, and G_i is the number of distinct kmers of genome i. A repeat shared between genomes is paralogy, i.e. homology: a true positive, not a false one. Low-complexity kmers (which would share by composition, not descent) are removed upstream by the entropy filter.
  • Residual violation of the equiprobability behind p_i: nucleotide composition bias (see Karlin–Ost in the user doc).
  • Test dependence between overlapping kmers (see FDR section).

Goal: an FDR of homology

H_0: the S genomes are unrelated (independent random sequences of sizes G_i). Rejecting H_0 for a kmer, i.e. sharing that chance cannot explain, is the evidence of homology. The quantity wanted is the false discovery rate of the call "shared kmer \Rightarrow homologous".

Empirical FDR from the count histogram

Let N be the size of the kmer space and n_{\ge r} the observed number of distinct kmers present in at least r genomes (a by-product of the index). Under H_0 the expected number of kmers with R\ge r over the whole space is exactly N\,P(R\ge r), with P the Poisson-binomial tail above. Hence

\widehat{\mathrm{FDR}}(r)=\min\!\left(1,\ \frac{N\,P(R\ge r)}{n_{\ge r}}\right).
  • No per-kmer multiple-testing correction: the number of tests (N) is already in the numerator.
  • Conservative: the observed n_{\ge r} mixes true homology and chance, and the true-null proportion \pi_0\le1 is taken as 1 (Storey-type upper bound).
  • Take the smallest r with \widehat{\mathrm{FDR}}(r)\le\alpha as the sharing threshold.
  • Equivalent per-kmer view: BH on p=P(R\ge r) with N tests. The zero-truncation matters if one tests only kmers present in the index (R\ge1 by selection): use P(R\ge r)/P(R\ge1), not P(R\ge r), otherwise the test is too conservative by a factor \sim1/\lambda.

Dependence

Kmers of one shared region overlap and are not independent tests. The FDR above holds per kmer; for a per-region FDR, count regions (unitigs / super-kmers, with the appropriate clumping of N and n_{\ge r}) rather than kmers. Not settled.