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.
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
lgammastart:t_{j+1}=t_j\cdot\frac{S-j}{j+1}\cdot\frac{p}{1-p}. - Sum the tail not containing the mode (
Sp, notS/2). Ifr>Sp, sum\sum_{j\ge r}directly and stop when terms are negligible. The complement1-\sum_{j=0}^{r-1}(note: fromj=0) suffers catastrophic cancellation when the p-value is tiny. - Large
S: normal approximation with continuity correction, or Poisson(Sp) whenpis 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 allp_i\ll1, i.e.4^k\gg G_i(largek). - 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 forr\ge S\bar p+1,P_{\mathrm{PB}}(R\ge r)\le P_{\mathrm{Bin}}(R\ge r): using the mean\bar Goverestimates the chance probability, i.e. is conservative in the upper tail. Wrong direction forr\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_iis the number of distinct kmers of genomei. 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\le1is taken as1(Storey-type upper bound). - Take the smallest
rwith\widehat{\mathrm{FDR}}(r)\le\alphaas the sharing threshold. - Equivalent per-kmer view: BH on
p=P(R\ge r)withNtests. The zero-truncation matters if one tests only kmers present in the index (R\ge1by selection): useP(R\ge r)/P(R\ge1), notP(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.