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

70 lines
5.6 KiB
Markdown

# 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](entropy.md).
- 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.