JaCK & Jill
JaCK & Jill, the Python package phyloexact (import phyloexact as px), computes the Bayesian evidencemarginal likelihood: the probability of the alignment under a tree and a model, integrated over the branch lengths with a prior of a tree from a small alignmentthe same gene from several species lined up, one row per species and one column per position and a substitution modelthe rates at which one base is replaced by another along a branch. It returns an exact fraction, a proven interval, an estimate with a measured error, or a proof that two trees tie, each with a machine-readable certificate that a separate routine rechecks against the data. JaCK stands for the exact Jukes–Cantor and Kimura computations, Jill for the interval and sampling routines, and the method is that of the papers by Schwartz, Edwards and Lewis (Phylogenetics).
Where it comes from
Tim Peters wrote int_to_decimal, the CPython routine that prints a large integer in decimal, and the package's printer int_str follows it, as a restatement with small edits. Sebastiano Vigna wrote the reference code of the SplitMix64 and xorshift64* random-number generators, which the compiled kernel for the general Markov model uses constant for constant. One recoding table was checked against the source of PhyloBayes. The rest was written for BootLoops.
| Part of the package | Source | Authors |
|---|---|---|
Translated routine (same language): int_str in phyloexact/bigint.py | int_to_decimal in Lib/_pylong.py, CPython 3.12 | Tim Peters; Python Software Foundation |
Translated routines: the generators _splitmix64 and _next_u01 in phyloexact/lanes/gm.py | splitmix64.c (2015) and xorshift64star.c (2014) | Sebastiano Vigna |
Table checked against their source: PB_dayhoff4 in pins/phylo_bio/recode.py | sources/phylo.h in PhyloBayes; the PhyloBayes manual prints the same grouping | N. Lartillot, T. Lepage and S. Blanquart |
| New code: the other modules | Written for BootLoops | Code by Claude, supervised by Matthew D. Schwartz |
Please cite the authors' work when you rely on these parts. JaCK & Jill is not affiliated with or endorsed by the Python Software Foundation, Sebastiano Vigna or the PhyloBayes authors.
What it does
Bayesian phylogenetics weighs one tree topologythe branching pattern of a tree: which species are joined to which, regardless of how long the branches are or one substitution model against another by its evidence, and a ratio of two evidences is a Bayes factor. Programs in everyday use estimate the evidence by sampling, without a proven error bound. For four taxa (the species at the tips of the tree) under the Jukes–Cantor model (JC69, all substitutions equally likely) with the package's prior, the evidence is a rational number, returned as a Python Fraction:
$$Z(T)=\int_{(0,1)^5} P(D\mid T,x)\,dx_1\cdots dx_5,\qquad x_e=e^{-4t_e/3}.$$
The prior is uniform in each $x_e$, which is an exponential prior of rate $4/3$ on each branch length $t_e$. Under JC69 the likelihood is a polynomial in the $x_e$ with rational coefficients, so $Z$ is rational and a Bayes factor is a ratio of integers. Kimura's two-parameter model (K2P) is exact too on shorter alignments, and protein sequences enter through a four-letter recoding ('JC-SR4').
The package calls the kind of answer its register. Each answer is labeled with one of four registers:
R0, a tie proof. If a permutation of the taxa leaves the site-pattern countshow many columns of the alignment show each pattern of letters across the taxa unchanged and maps one topology onto the other, the two evidences are equal. This holds under the usual models (JC69, K2P, GTR, mixtures) with any independent branch prior. Nothing is integrated, and every comparison checks for this first.R1, the exact fraction. It comes with a check that its denominator divides a bound known in advance, $256^N\,\mathrm{lcm}(1,\ldots,N+1)^5$ for $N$ columns under JC69.R2, an interval. Quadrature in ball arithmeticeach number is a midpoint plus a radius that provably contains the true value (needspython-flint) gives exact rational endpoints proven to contain $Z$. Where only the upper end is proven the label isR2-one-sided.R3, an estimate. Importance samplingdraws branch lengths from a fitted stand-in distribution and reweights each draw with scrambled Sobol points (points spread evenly instead of at random) works at any alignment length, for JC69, HKY85, GTR with gamma rates and your own log-likelihood (px.PlugIn).
The error figure of an R3 estimate comes from a calibration record of measured deviations from exact values on small alignments, identified by checksum in the certificate. It is an indicative accuracy, not a bound. The bundled record was measured on JC69 quartets (alignments of four taxa), and HKY85 and GTR estimates reuse it and say so in the certificate. A model without a usable record, such as general Markov ('GM'), is refused with a message.
register="auto" returns the strongest answer available, based on an import-time probe of the installed libraries and GPU that is recorded in every certificate. Forcing a register that cannot be met raises px.RegisterUnavailable. Its reason gives the limit and its unlock the smallest change that would satisfy the request. Nothing weaker is substituted silently.
px.verify_certificate rechecks a certificate against the data. It recomputes the value where that is cheap and says what it skipped. It catches mistakes, stale installs and corruption, and is not designed to stop someone who can rewrite both the certificate and the package.
px.hill works at genome length. It runs window scans and computes an exact upper bound on the likelihood that any independent-sites model can reach on an alignment of any size. It also checks published likelihood tables against that bound and writes weighted-quartet input files for the species-tree programs wASTRAL and wQFM. px.quintet ranks the 15 rooted five-taxon trees by maximum likelihood with proven bounds, abstaining rather than guessing.
The package has these limits:
- It scores a given topology and does not search trees.
- Exact values and intervals are four-taxon (the quintet engine aside). Beyond that it offers tie proofs for up to 32 taxa and the JC69 estimate.
- On a CPU, JC69 is exact for quartets up to 150 usable columns and K2P up to about 35. Past 150 columns exact JC69 needs a CUDA GPU with
torch, and only for alignments inside a measured size range that the refusal message states. - HKY85 and GTR have irrational transition probabilities, so no exact value exists and a forced
R1says so. - Columns with gaps or ambiguity codes are dropped.
- The certificates of the weight files cover the inputs to a species-tree program, never the tree.
Examples
The self-test suite. The package is the root of the jackandjill repository. With it installed (see Requirements), run the suite from any directory you can write in:
python3 -m phyloexact.validate
The suite prints the capability probe, one line per test with PASS or FAIL, and a line beginning OVERALL PASS or OVERALL FAIL. It writes VALIDATION_REPORT.json. No GPU or external data is needed, a missing optional library is reported as a skip, and any failure makes the exit code nonzero.
The smallest exact case. From the suite's JC69 test: one column in which all four taxa carry the same base, then twenty such columns with the exact register forced.
from fractions import Fraction as F
from phyloexact import Dataset, evidence
rep = evidence(Dataset.from_counts({"AAAA": 1}), "12|34", "JC69")
rep.register == "R1" and rep.value == F(103, 4096) # True
rep = evidence(Dataset.from_counts({"AAAA": 20}), "12|34", "JC69",
register="R1")
c = rep.certificate
c["denominator_bound"]["divides"] # True
len(c["engine"]["sha256"]) == 64 # True
A constant column has evidence exactly $103/4096$ on 12|34; the same test checks AGCT ($7/4096$) and AACG ($15/4096$). rep.logZ is the floating-point logarithm. In the certificate, denominator_bound records that the denominator divides the bound above, and engine holds the SHA-256 of the exact engine's source, which the verifier compares with the file on disk.
A quartet from a FASTA file. Lines from the quickstart of the package guide: one evidence, the tie-proof certificate, a topology comparison, a between-model Bayes factor and a certificate check.
import phyloexact as px
ds = px.Dataset.from_fasta("quartet.fasta", taxa=["a", "b", "c", "d"])
rep = px.evidence(ds, topology="12|34", model="JC69", register="auto")
rep.value # exact Fraction (R1) or float logZ view (R2/R3)
rep.register # register actually delivered, e.g. 'R1'
rep.certificate # machine-checkable dict
px.decidability(ds) # R0 certificate directly (always available)
px.compare(ds, "13|24", "14|23", model="GTR+G") # forced tie => R0, no arithmetic
px.compare_models(ds, "12|34", models=("K2P", "JC69")) # exact between-model BF
px.verify_certificate(rep.certificate, dataset=ds) # machine-check any cert
taxa= selects the records and fixes their order, so "12|34" pairs a with b; "13|24" and "14|23" are the other two quartet trees. For a transfer-RNA-length alignment rep.register is 'R1' and rep.value a Fraction with hundreds of digits; on a long one auto gives 'R3' and a floating-point log evidence. px.compare returns a dictionary whose verdict is 'forced-tie' (with log_bf exactly 0 and the symmetry that proves it) or 'computed' (with log_bf, and bf_exact when both sides are exact).
Routines
| Command | What it does |
|---|---|
python3 -m phyloexact.validate | The self-test suite; --parity adds the tier that recomputes exact values quoted in the paper, --full every one |
python -m phyloexact.hill.grader FILE | Tests a published likelihood table (--package iqtree, paup, mrbayes or auto) against the exact ceiling and its own numbers |
python -m phyloexact.hill.scan --windows windows_W.npy --out OUTDIR | Window scan: one JSON line per window plus MANIFEST.json; --rows windows.json is the other input form |
python -m phyloexact.hill.weights --scan SCAN_OUT.jsonl --manifest MANIFEST.json --taxa A,B,C,D --out OUTDIR | Writes wASTRAL and wQFM weight files with sidecar certificates |
python -m phyloexact.hill.verify_cert FILE.certificate.json --scan SCAN_OUT.jsonl --taxa A,B,C,D | Rechecks a sidecar by re-rendering your weight file from your scan output under your four leaf names |
python -m phyloexact.hill.l4_check [FILE] | A score-gap certificate for a returned species tree, from exact scores and per-quartet bounds |
python -m phyloexact.hill.bench run --case CASE.json | The large exact-JC69 GPU benchmark; without CUDA it stops with BenchUnavailable, exit 2 |
A rerun of hill.scan on the same input skips finished windows. An --out that holds another input's rows is refused unless --force-rescan is given, and provably tied windows are marked tied with no winner. hill.verify_cert exits with 0 for verified, 1 for failed, 2 for unreadable, 3 for format checks only (no scan supplied, or --no-sources) and 4 for format checks only (no taxa supplied).
| Function | What it returns |
|---|---|
px.Dataset.from_fasta(path), .from_rows(rows), .from_counts(counts) | An alignment from a file, a {name: sequence} mapping, or site-pattern counts |
px.evidence(ds, topology, model, register) | An EvidenceReport with .value, .logZ, .register, .certificate and .meta |
px.decidability(ds) | The R0 certificate for 4 to 32 taxa: the symmetry group of the pattern counts and the topology pairs forced to tie |
px.compare(ds, topoA, topoB, model) | The tie check first, else both evidences and the log Bayes factor |
px.compare_models(ds, topology, models) | A ModelComparisonReport whose .bf is an exact ratio when both models ran exactly |
px.grade_model(ds, rep) | How far the evidence falls below the ceiling $\prod_k (n_k/N)^{n_k}$ of every independent-sites model, in nats per site |
px.check_adequacy(data, topology, model), px.prior_predictive(model, topology) | A posterior-predictive check on pattern-class frequencies, and the exact prior-predictive class probabilities |
px.pail_evidence(ds, model), px.pail_row(ds, models), px.pail_aggregate(rows) | Tree-free model choice: evidence averaged over the three topologies, one window's between-model differences, the summary over windows |
px.PlugIn(loglik_fn, d) | Your own vectorized log-likelihood on the d-dimensional unit cube as a model, for the estimate register only |
px.verify_certificate(cert, dataset) | ok, register, checks (each pass, fail or skipped), n_performed and n_skipped |
px.capabilities() | The import-time probe of libraries and GPU |
px.hill.sup_ceiling_from_counts(counts) | The exact ceiling for a count table, as a Fraction plus certificate |
px.quintet.engine() | The interval engine; its rank_topologies(counter, cap=...) returns certified upper and lower bounds on each of the 15 trees' evidence |
px.quintet.adjudicate(fasta, name_map) | A report whose verdict is CERTIFIED_ML_WINNER, CERTIFIED_TOP_SET or ABSTAIN, with leader, surviving and the policy used |
topology is a quartet key such as "12|34", a Newick string over the taxa names, or "all" for the sum over the three quartet topologies, which returns a TopologySumReport. Under JC69 the estimate route also accepts five or more taxa. Beyond four taxa px.compare computes the untied case only under JC69, as estimates. Up to seven taxa px.decidability returns every orbit; from eight on, pass topology= as a Newick string to get that topology's orbit.
In px.compare_models an exact and an estimated side combine only with allow_mixed_registers=True, and then carry the weaker label.
Three worked plug-ins (a covarion switch, a two-profile mixture, a multispecies-coalescent quartet) are under examples/, for example python3 examples/covarion_plugin.py.
px.quintet.adjudicate expects five records named H, OT, CO, RN and OG, or a name_map={"H": "taxonA", ...} from those seats to your record names. The compiled fastbnb.so is used when it loads on this CPU, and otherwise a numpy path gives the same verdicts. The bounds of px.quintet.engine() are computed in exact arithmetic and are tight enough to separate trees on short windows.
The package README marks a few interfaces as experimental: the pail_* calls, non-default priors and plug-in models, the genome-scan command-line tools, the quintet tuning options, and the estimate route of the adequacy check. They are tested, but their signatures may change in a later release. GUIDE.md in the package describes every call, and phyloexact/__init__.py, phyloexact/hill/__init__.py and phyloexact/quintet/__init__.py list the exported names.
Used on this site
- Phylogenetics: the package described in the second paper there; its exact values are the reference for that page's benchmark of evidence estimators.
Requirements
- Runs on: Python 3.10 or later with
numpy,scipy,sympyandmpmath. - Install: run
pip install -e .from the root of ajackandjillcheckout, or put that directory onPYTHONPATH. The package reads checksummed reference files beside it, so it is not built as a wheel. - Self-test:
python3 -m phyloexact.validateprints a line beginningOVERALL PASS. - Optional:
python-flint(intervals),numba(compiled sampling kernels),torchwith CUDA (large exact JC69). - Files not to edit: anything under
pins/andphyloexact/quintet/_vendor/. The bundledfastbnb.sois checksummed, so never rebuild it in place. - Rebuilding the quintet kernel:
build_fastbnb.sh OUT.sobuilds the kernel to a path of yours (setFASTBNB_MARCH=nativeon a CPU without AVX2 or a non-x86-64 machine; keep-ffp-contract=off, no fast-math). Then point$PHYLOEXACT_FASTBNB_SOat it and rerun the self-tests.
Source and references
The code is BootLoops' jackandjill repository (GitHub organization BootLoops-ai, beside the bootloops toolkit repository rather than inside it). The author is Matthew D. Schwartz, and the code was written by Claude (Anthropic) under his supervision. The supplementary material on the Phylogenetics page is the full manual: every call with its options, returned objects and refusals, the models available for each kind of answer, and cost planning.
| Reference | What it supplies |
|---|---|
| M. D. Schwartz, S. V. Edwards and P. O. Lewis, the two papers on the Phylogenetics page | The method and the description of the package |
| T. H. Jukes and C. R. Cantor (1969), doi:10.1016/B978-1-4832-3211-9.50009-7; M. Kimura (1980), doi:10.1007/BF01731581 | The JC69 and K2P substitution models |
| M. D. Hendy and D. Penny (1989), doi:10.2307/2992396 | The Hadamard coordinates in which the exact values are computed |
| S. N. Evans and T. P. Speed (1993), doi:10.1214/aos/1176349030 | The same coordinates |
| L. A. Székely, M. A. Steel and P. L. Erdős (1993), doi:10.1006/aama.1993.1011 | The same coordinates |
| N. Goldman (1993), doi:10.1007/BF00166252 | The unconstrained likelihood, which is the ceiling of px.hill |
F. Johansson (2017), doi:10.1109/TC.2017.2690633; python-flint by F. Johansson, O. Benjamin and contributors | Arb, the ball arithmetic of the R2 intervals |
Tim Peters, int_to_decimal in Lib/_pylong.py, CPython 3.12 | The routine that int_str follows |
S. Vigna, splitmix64.c (2015) and xorshift64star.c (2014) | The reference code of the two random-number generators of the general Markov kernel |
| Steele, Lea and Flood, OOPSLA 2014; Marsaglia, J. Stat. Softw. 8(14) (2003); S. Vigna, ACM Trans. Math. Softw. 42 (2016) 30 | The papers that define SplitMix, xorshift and xorshift64* |
| N. Lartillot, T. Lepage and S. Blanquart (2009), doi:10.1093/bioinformatics/btp368 | PhyloBayes, against whose source PB_dayhoff4 was checked |
The full list of references, with DOIs, is in GUIDE.md in the package, under "References".