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 PopcornSourceAuthors
Same statements as twosfs: the seed-hash function seed_from_name and the tskit branch-spectrum call, both in twowindow_sim.pysimulations.py and spectra.py in twosfsD. 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 twosfsThe 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) iyaf023Fenton, 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.

The package holds six more modules. Their functions and commands are in GUIDE.md.

ModuleWhat it does
popcorn.twosfsExact two-site spectrum of completely linked sites under multiple-merger coalescents, with exact certificates against the variable-size Kingman class
popcorn.foldgateMinor-allele folding of a two-site spectrum, with exact deciders against the folded variable-size Kingman class
popcorn.twositeExact projection of two-site genotype tables to a fixed sample size; the two-site spectrum of a diploid panel from genotypes
popcorn.enclosureCertified intervals for the selected spectrum after a piecewise-constant size history, for $S\le 0$ and small samples
popcorn.plantedSimulated data with known expected spectra, for testing estimators (msprime)
popcorn.twowindowThe 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:

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/.

CommandWhat 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

FunctionWhat 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

FunctionWhat 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

FunctionWhat 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_supPositivity 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_rootsA 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

FunctionWhat 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

FunctionWhat 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

FunctionWhat 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

FunctionWhat 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

Requirements

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.

ReferenceWhat it supplies
Sawyer and Hartl, Genetics 132 (1992) 1161The Poisson-random-field selected spectrum
Bustamante, Wakeley, Sawyer and Hartl, Genetics 159 (2001) 1779The closed form in ${}_1F_1$ written explicitly
Williamson, Fledel-Alon and Bustamante, Genetics 168 (2004) 463Selection 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: twosfsThe 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

← back to the tools index