Popcorn
Popcorn is a Python package for the expected site-frequency spectrumfor a sample of n chromosomes, the number of variable sites at which the mutant allele is carried by exactly i of them, for each i of a DNA sample under natural selection, in the Poisson random field model of Sawyer and Hartl. Programs that infer the distribution of fitness effects of new mutations (polyDFE, dadi and fitdadi, fastDFE) evaluate this quantity in double precision inside their likelihoods. Popcorn returns it to a requested number of digits, as an exact value, as an interval guaranteed to contain the true value, or with a count of the digits on which two separate computations agree.
Where it comes from
E. F. Fenton, D. P. Rice, J. Novembre and M. M. Desai proposed the two-site test for multiple-merger coalescentsgenealogical models in which three or more ancestral lineages may merge in a single event, as under sweepstakes reproduction, a test on the joint frequencies of pairs of nearby variable sites. They also defined the folded two-site spectrum. Their program for the test is twosfs. Popcorn implements the test and the folded spectrum.
Popcorn's two-window simulation harness (popcorn.twowindow) runs the simulator msprime and reads the spectrum of each simulated genealogy with tskit. It reuses the seed-hash function and the tskit branch-spectrum call of twosfs, and its seed scheme follows theirs. The rest of Popcorn is new code written for BootLoops, following the conventions of dadi, fitdadi, polyDFE, fastDFE and moments.
| Part of Popcorn | Source | Authors |
|---|---|---|
Same statements as twosfs: the seed-hash function seed_from_name and the tskit branch-spectrum call, both in twowindow_sim.py | simulations.py and spectra.py in twosfs | D. P. Rice, E. F. Fenton, J. Novembre and M. M. Desai |
Follows twosfs: the seed scheme of twowindow_sim.py (a run name hashed to a seed, which starts the generator that seeds msprime) | simulations.py and snakefiles/simulations.snake in twosfs | The same authors |
New code for objects of their paper: the two-site spectrum (popcorn.twowindow, popcorn.twosite), its folding (popcorn.foldgate), the spectrum-matched Kingman null (popcorn.planted) | Genetics 229 (2025) iyaf023 | Fenton, Rice, Novembre and Desai (paper); code by Claude |
Please cite the authors' paper when you use the two-site modules. This package is unrelated to Popcorn, the trans-ethnic genetic-correlation estimator of Brown, Ye, Price and Zaitlen (2016).
What it does
In a sample of $n$ chromosomes, entry $i$ of the site-frequency spectrum is the number of variable sites at which the derived (mutant) allele is carried by exactly $i$ of them. Under the Poisson random field model of a constant-size population, mutations with scaled selection coefficient $S=4N_e s$ ($S \gt 0$ advantageous) give entry $i$ the expectation
$$E_i(S)=\theta\,\frac{n}{i(n-i)}\,\frac{1-{}_1F_1(n-i;\,n;\,-S)}{1-e^{-S}},\qquad i=1,\dots,n-1,$$
with ${}_1F_1$ the confluent hypergeometric function and $\theta$ the scaled mutation rate (Popcorn uses $\theta=1$).
Evaluating it is badly conditioned. At moderate $n$ and $|S|$ the intermediate quantities cancel far beyond the 16 digits of double precision, so a double-precision value can be wrong with no warning. On the rare-mutations page, the unphysical second solution of the recurrence is already at least $10^{83}$ for $n=100$ at $S=\pm 10$, against entries of order one for the true solution. Popcorn computes the same object in exact or arbitrary-precision arithmetic with a check attached to every number.
Eight modules are described on this page.
popcorn.sfs, exact route. The values $M_i={}_1F_1(n-i;n;-S)$ obey a three-term recurrence in $i$ with elementary end values, so the vector solves one tridiagonal linear system. For rational $S$ the solution separates as $M_i=\alpha_i+\beta_i e^{-S}$ with $\alpha_i,\beta_i$ exact fractions. Each derivative $d^kM/dS^k$ is one more solve of the same system. The sum is evaluated at a precision chosen from the size of the fractions, so the cancellation cannot reach the requested digits. This route is practical to about $n=2000$.popcorn.sfs, ball route. Above $n=2000$ the recurrence runs in ball arithmeticeach number is a midpoint plus a radius that provably contains the true value (python-flint), with the precision doubled until the worst relative radius meets the target. It has been run to $n=10^5$.popcorn.dfeintegrates the spectrum against polyDFE's "model C" distribution of fitness effects. That is a reflected gamma density (shape $b$, mean $S_d \lt 0$) for deleterious mutations plus, with weight $p_b$, an exponential (mean $S_b \gt 0$) for beneficial ones. Ball-arithmetic spectra are computed once at fixed quadrature nodes in $\log|S|$. Each later evaluation is a weighted sum over that cache, and the gradient in $(b,S_d,p_b,S_b)$ reuses it.popcorn.dominancehandles a dominance coefficient $h\neq 1/2$ (genotype fitnesses $1:1+2sh:1+2s$). It has two evaluators for cross-checking: adaptive quadrature over a closed-form inner integral, and a series.popcorn.certificatesdecides in exact rational arithmetic whether a polynomial is nonnegative on $[0,1]$ and whether a rational point lies in the convex hull of a set of rational points. Membership comes with exact weights, and non-membership with an exact separating (Farkas) functional. Theregionpart certifies statements over a whole two-parameter box instead of a grid of samples. A floating-point solve may propose an answer, but only exact arithmetic accepts it, and every certificate is substituted back before it is returned.popcorn.lambda_coalescenthandles multiple-merger coalescents at constant population size. For the Kingman (pairwise mergers only), Beta$(2-\alpha,\alpha)$ and Dirac$(\psi)$ families it returns the merger rates $\lambda_{b,k}$ and the expected branch length $E[L_i]$ subtending $i$ of $n$ samples, as exact fractions. $E[L_i]$ gives the expected neutral unfolded spectrum.popcorn.twolocuscomputes the second moments $E[T_i^A T_j^B]$ of the branch lengths subtending $i$ samples at one locus and $j$ at another. The model is the coalescent with recombination at scaled rate $\rho$ and a piecewise-constant population size. The moments are the expected two-locus frequency spectrum up to scale. The module solves sparse linear systems, with no simulation, and is practical to $n=8$.popcorn.transientcomputes the expected spectrum under genic selection $S$ after a piecewise-constant size history, for samples of roughly $n=1000$ to $2500$. It integrates the Kimura forward diffusion on a fixed frequency grid and projects to the sample size only at the end. It also down-samples and folds spectra.popcorn.ancestralis a data utility with nothing certified in it. It joins a table of variant sites to an Ensembl EPO ancestral-allele FASTA file and classifies each site by the EPO confidence convention (uppercase base high, lowercase low,N,-or.no call). For biallelic SNVs it orients REF and ALT to ancestral and derived, and writes apos ref alt anc conftable.
The package holds six more modules. Their functions and commands are in GUIDE.md.
| Module | What it does |
|---|---|
popcorn.twosfs | Exact two-site spectrum of completely linked sites under multiple-merger coalescents, with exact certificates against the variable-size Kingman class |
popcorn.foldgate | Minor-allele folding of a two-site spectrum, with exact deciders against the folded variable-size Kingman class |
popcorn.twosite | Exact projection of two-site genotype tables to a fixed sample size; the two-site spectrum of a diploid panel from genotypes |
popcorn.enclosure | Certified intervals for the selected spectrum after a piecewise-constant size history, for $S\le 0$ and small samples |
popcorn.planted | Simulated data with known expected spectra, for testing estimators (msprime) |
popcorn.twowindow | The two-window simulation harness: the pooled two-site vector with jackknife standard errors (msprime) |
The package stores a SHA-256 digest of every engine and certificate file and of REFERENCE_VALUES.json, and popcorn.verify() names any file that changed. The command-line script certsfs.py checks the files it uses before importing them. On a digest mismatch, a disagreement between its two routes, or a failure to reproduce a stored reference value, it exits with status 3 instead of printing an unchecked number.
Popcorn has these limits:
- The certified modules assume a constant population size at equilibrium, except
popcorn.enclosure.popcorn.lambda_coalescentis neutral and constant-size. popcorn.twolocusandpopcorn.transientare floating point: double precision, validated by measurement over a stated range and unmeasured outside it. The guide records that range (forpopcorn.transientat $n=1000$, agreement with the certified stationary values to $9.4\times10^{-5}$ relative or better for $|S|\le 100$). Label their numbers as floating point wherever they appear beside certified ones.- The digit counts of
popcorn.dfeandpopcorn.dominancemeasure self-consistency. They are strong evidence of accuracy; unlike the exact fractions and ball radii ofpopcorn.sfs, they are not proofs. - Results of
popcorn.plantedandpopcorn.twowindoware simulations with Monte Carlo errors, never exact or certified. - There is no migration, no multi-population spectrum, no continuous size change and no fitting driver.
- Spectra are unfolded, at $\theta=1$. $S$ is the $S$ of polyDFE and fastDFE; dadi and fitdadi use $\gamma=S/2$.
Examples
Run the self-test suite. With the package set up (see Requirements), run from the root of the BootLoops repository; the package directory is tools/popcorn/:
python3 tools/popcorn/selftest.py
The suite prints one line per check (LEG <name> with PASS, SKIP or FAIL and a short detail), then a count of passes, skips and failures. It ends with exactly one OVERALL PASS or OVERALL FAIL: <names> line, with exit status 0 or 1. The checks include deliberately wrong inputs (an exterior point, a negative polynomial) that must be refused.
Compute one entry by two routes. Here entry $i=50$ of a sample of $n=100$ at $S=-1000$, to 40 digits:
python3 tools/popcorn/certsfs.py check 100 50 -1000 --dps 40
Three lines come back, labeled closed, series and agree. They hold the value from the hypergeometric closed form (mpmath), the value from an exact-rational series, and the number of digits on which the two agree. If agreement falls below dps minus 5, the script still prints both values, then writes an error to standard error and exits with status 3. A calling script cannot mistake such a run for a success. Only mpmath is needed.
Mix the spectrum over a distribution of fitness effects, from Python. Put the repository's tools/ directory on PYTHONPATH so that import popcorn resolves. Then check the digests and drive the mixing layer the way the engine's self-test does:
import popcorn
popcorn.verify()
from popcorn.dfe import CertifiedKernel
n = 20
K = CertifiedKernel(n, dps=40)
K.build(-1)
K.build(1)
Ev, sc, tail = K.mix({'b': '0.4', 'Sd': '-1000', 'pb': 0})
g = K.grad_mix({'b': 0.4, 'Sd': -1000.0, 'pb': 0.02, 'Sb': 10.0})
verify() returns [] on an intact copy and otherwise one string per changed or missing file. build(-1) and build(1) fill the cache for each sign of $S$ (the slow step; python-flint required). mix returns the mixed spectrum as a list indexed by $i$ (here purely deleterious, $p_b=0$), the digits on which the two quadrature degrees agree, and the relative tail bound. grad_mix returns the derivatives with respect to the four parameters.
Exact expected spectrum under a multiple-merger coalescent, from Python. With tools/ on PYTHONPATH as above, the guide's example evaluates a Beta coalescent and a Dirac coalescent for a sample of 50:
import popcorn # with tools/ on PYTHONPATH
from fractions import Fraction
L = popcorn.lambda_coalescent # exact, standard library
h = L.expected_lengths(50, L.beta_rate(Fraction(3, 2)))[50] # {i: E[L_i]} exact Fractions
x = L.xi_hat(50, L.dirac_rate(Fraction(1, 10))) # normalized expected SFS, sums to 1 exactly
beta_rate(Fraction(3, 2)) returns the merger-rate function of the Beta$(1/2,3/2)$ coalescent ($\alpha=3/2$) and dirac_rate(Fraction(1, 10)) that of the Dirac coalescent with $\psi=1/10$. The entry [50] of expected_lengths maps each $i=1,\dots,49$ to the exact expected total branch length subtending $i$ of the 50 samples, which is proportional to the expected unfolded spectrum. Pass parameters as Fraction objects or strings such as '3/2', never as binary floats, or the rates are exact for the wrong rational number. The cost is $O(n^3)$ rational operations whose size grows with $n$, and $O(n^2)$ for Kingman.
Routines
The scripts are in tools/popcorn/.
| Command | What it does |
|---|---|
certsfs.py check N I S [--dps D] | One entry by two routes, with the digits of agreement; exit status 3 below $D-5$ |
certsfs.py entry N I S [--dps D] | One entry from the closed form to $D$ digits (default 40) |
certsfs.py vector N S [--dps D] [--grad] | The whole spectrum, one tab-separated line per $i$, with $dE_i/dS$ under --grad |
certsfs.py selftest [--dps D] | Verifies the digests, reproduces two stored reference values and cross-checks the routes |
selftest.py [--full] | The self-test suite of the first example; --full adds the slow checks |
lambda_exact.py [--n N] [--out FILE] | Runs the exact identity checks and prints the $n=20$ reference grid; --out also writes JSON |
epo_join.py --fasta F --sites T --out O [--chrom C] [--summary J] | Writes the polarized table and prints the counters; --summary writes counters and rates as JSON |
vector uses the exact route for $N\le 2000$ and ball arithmetic above. Every refusal of certsfs.py raises CertSFSGateError, with exit status 3. epo_join.py also takes --layout with the value auto, chrom or nochrom. Always pass --chrom with a multi-chromosome sites table, since only the first FASTA record is read.
The modules load on first access after import popcorn.
popcorn.sfs
| Function | What it returns |
|---|---|
solve_M_exact(n, S) | Exact (alpha, beta), length $n+1$, with $M_i=\alpha_i+\beta_i e^{-S}$; S an integer or Fraction |
solve_dM_exact(n, S, alpha, beta, order) | Exact $d^kM/dS^k$ up to order, as a list of (alpha_k, beta_k) |
assemble_M(alpha, beta, S, target_dps) | $M_i$ to target_dps digits; pass the same S as in the solve |
sfs_engine.sfs_from_M(n, S, M_alpha_beta_or_list, dps) | $E_i$, $i=1,\dots,n-1$, from the (alpha, beta) tuple or a list of $M_i$ |
arb_route.solve_vector_arb(n, S, target_dps) | Ball-arithmetic $M$ and $dM/dS$: a dictionary with M, Mp, achieved_dps, prec |
arb_route.sfs_arb(n, S, sol, i) | $E_i$ and $dE_i/dS$ as balls from that result |
popcorn.dfe and popcorn.dominance
| Function | What it returns |
|---|---|
CertifiedKernel(n, dps) | The cache object; .build(sign) fills it for one sign of $S$ |
.mix(params) | The mixed spectrum, the self-consistency digits and the tail bound; params has keys b, Sd, pb, Sb |
.grad_mix(params) | A dictionary keyed 'b', 'Sd', 'pb', 'Sb', each a list of $\partial E_i/\partial(\text{parameter})$ |
E_dominant(n, k, S, h, dps) | Entry $k$ at selection $S$ and dominance $h$, with its self-consistency digits |
E_dominant_qseries(n, k, S, h, dps) | The same entry from the series evaluator; call it at two precisions and compare |
popcorn.certificates
| Function | What it returns |
|---|---|
positivity.nonneg_route_B(coeffs, touch_points) | (verdict, info): verdict True, False or None (undecided) for nonnegativity of {exponent: rational} on $[0,1]$, by exact Bernstein subdivision |
positivity.nonneg_route_R(coeffs) | (verdict, info, dips): the same verdict by certified root isolation and exact sign checks |
exact_lp.membership(points, q) | ('FEASIBLE', weights), or ('INFEASIBLE', (w, w0)) with an exact Farkas functional, by a pure-rational simplex |
fast_lp.membership_fast(points, q), cone_lp_b.membership_exact(points, q, warm) | The same verdicts by a floating-point solve decided exactly, and by an exact integer dual simplex |
CertHull(points), .decide(q) | Status, certificate, basis and route, for many queries against one point set |
region.to_bernstein, region.bern_nonneg, region.certified_sup | Positivity of {(es, eu): Fraction} on $[0,1]^2$, and the smallest certified $c$ with $c\,T-P\ge 0$ on a box |
region.cs_chi2_lower_bound, region.reconstruct_rational, region.count_roots | A Cauchy–Schwarz lower bound on a $\chi^2$ distance, rational reconstruction, and a Sturm root count |
membership_fast raises BudgetExceeded when its exact check runs out of budget. It never returns a rounded verdict.
popcorn.lambda_coalescent
| Function | What it returns |
|---|---|
kingman_rate(), beta_rate(alpha), dirac_rate(psi), msprime_dirac_rate(psi, c) | Merger-rate functions lam(b, k) for the Kingman, Beta, Dirac and Kingman-plus-Dirac (msprime's Dirac model) coalescents |
expected_lengths(n, lam) | Dictionary h[m][i] of exact expected branch lengths subtending $i$ of $m$ lineages; h[n] is the sample's spectrum |
xi_hat(n, lam) | The expected unfolded spectrum normalized to unit sum, a list of $n-1$ fractions |
identity_checks(n) | The built-in exact identities, such as the Kingman $2/i$, as booleans |
reference_grid(), load_reference_spectra() | The $n=20$ grid of families (Kingman, seven Beta, six Dirac) and its stored exact spectra |
popcorn.twolocus
| Function | What it returns |
|---|---|
TwoLocus(n), .moments(rho, epochs) | (M, m1A, m1B) with M[i-1][j-1] $=E[T_i^A T_j^B]$ and the first moments at each locus |
moments(n, rho, epochs) | The same in one call, with the chain cached per n (default: constant size) |
pool_pairs(M) | The symmetrized moments on pairs $i\le j$ (diagonal doubled), normalized to unit sum |
epochs_from_Nt(times_gen, sizes, N_ref) | A size history in generations converted to the [(tau_start, eta)] form |
epochs is [(tau_start, eta), ...] with time in units of $2N_{\mathrm{ref}}$ generations ascending from 0, eta $=N_{\mathrm{ref}}/N$ and the last epoch extending to infinity; rho $=4N_{\mathrm{ref}}R$. Compare a pooled vector only with vectors pooled the same way.
popcorn.transient
| Function | What it returns |
|---|---|
TransientSFSEngine(n) | The engine, with the frequency grid and the projection to sample size n built once |
.expected_sfs(S, epochs) | (E, meta): the unfolded spectrum $E_i$, $i=1,\dots,n-1$, after the history epochs |
.equilibrium_sfs(S) | The stationary spectrum in floating point (use popcorn.sfs for certified values) |
project_down(E, n, m), fold_sfs(E) | An unfolded spectrum down-sampled from sample size n to m, or folded to minor-allele classes |
epochs is [(nu, T), ...]: relative size $N/N_{\mathrm{ref}}$ and duration in $2N_{\mathrm{ref}}$ generations, past to present, following an ancestral equilibrium. T <= 0 is an instantaneous size change. The caller must check meta["negative_entries"] == 0.
popcorn.ancestral
| Function | What it returns |
|---|---|
join_sites(fasta, sites, out, chrom) | The counters dictionary, after writing the pos ref alt anc conf table (out=None for counters only) |
polarization_rates(counts) | Summary fractions from those counters; None where a denominator is zero |
Each module file in the package directory, such as sfs.py, lists its exported names in __all__.
Used on this site
- Demography of rare mutations: the library implements the exact computation of the first paper listed there. The exact values are the reference against which the accuracy of polyDFE, fitdadi and fastDFE is measured.
Requirements
- Runs on: Python 3 with mpmath. The exact route of
popcorn.sfs, theentry,checkandselftestmodes ofcertsfs.pyandpopcorn.dominanceneed nothing else.popcorn.lambda_coalescentandpopcorn.ancestralneed only the standard library. - Install: nothing to build. Run the scripts from the repository root, and put the repository's
tools/directory onPYTHONPATHtoimport popcorn. - Self-test:
python3 tools/popcorn/selftest.pyends withOVERALL PASS. Add--fullfor the slow checks. A check whose optional dependency is missing is skipped with a line naming the package to install, and skips do not fail the suite. Nothing is written into the package directory. The quick test ispython3 tools/popcorn/certsfs.py selftest --dps 40. - Optional, python-flint: the ball route and
vectormode above $n=2000$,popcorn.dfe,cone_lp_b, one positivity route andpopcorn.enclosure. - Optional, numpy and scipy:
popcorn.twolocus,popcorn.transientand the floating-point proposers of the certificates. - Optional, others: gmpy2 for the linear-programming certificates, sympy for root counting and for the certificates of
popcorn.twosfsandpopcorn.foldgate, msprime for the simulations ofpopcorn.plantedandpopcorn.twowindow.
Source and references
The code is tools/popcorn/, version 1.0, in the BootLoops repository, with the package guide GUIDE.md beside it. The CREDIT section of GUIDE.md gives the further references module by module.
| Reference | What it supplies |
|---|---|
| Sawyer and Hartl, Genetics 132 (1992) 1161 | The Poisson-random-field selected spectrum |
| Bustamante, Wakeley, Sawyer and Hartl, Genetics 159 (2001) 1779 | The closed form in ${}_1F_1$ written explicitly |
| Williamson, Fledel-Alon and Bustamante, Genetics 168 (2004) 463 | Selection with dominance |
| dadi (Gutenkunst et al. 2009), fitdadi (Kim, Huber and Lohmueller 2017) and moments (Jouganous et al. 2017) | The likelihood conventions that Popcorn follows |
| polyDFE (Tataru et al. 2017) and fastDFE (Sendrowski and Bataillon 2024) | The same conventions; model C is polyDFE's |
| E. F. Fenton, D. P. Rice, J. Novembre and M. M. Desai, Genetics 229 (2025) iyaf023; code: twosfs | The two-site test and the folded two-site spectrum; the seed-hash function and the branch-spectrum call of twowindow_sim.py |
| msprime and tskit (Kelleher et al.) | The simulations, imported at run time when installed; moments is an optional cross-check |