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 packageSourceAuthors
Translated routine (same language): int_str in phyloexact/bigint.pyint_to_decimal in Lib/_pylong.py, CPython 3.12Tim Peters; Python Software Foundation
Translated routines: the generators _splitmix64 and _next_u01 in phyloexact/lanes/gm.pysplitmix64.c (2015) and xorshift64star.c (2014)Sebastiano Vigna
Table checked against their source: PB_dayhoff4 in pins/phylo_bio/recode.pysources/phylo.h in PhyloBayes; the PhyloBayes manual prints the same groupingN. Lartillot, T. Lepage and S. Blanquart
New code: the other modulesWritten for BootLoopsCode 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:

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:

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

CommandWhat it does
python3 -m phyloexact.validateThe self-test suite; --parity adds the tier that recomputes exact values quoted in the paper, --full every one
python -m phyloexact.hill.grader FILETests 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 OUTDIRWindow 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 OUTDIRWrites 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,DRechecks 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.jsonThe 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).

FunctionWhat 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

Requirements

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.

ReferenceWhat it supplies
M. D. Schwartz, S. V. Edwards and P. O. Lewis, the two papers on the Phylogenetics pageThe 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/BF01731581The JC69 and K2P substitution models
M. D. Hendy and D. Penny (1989), doi:10.2307/2992396The Hadamard coordinates in which the exact values are computed
S. N. Evans and T. P. Speed (1993), doi:10.1214/aos/1176349030The same coordinates
L. A. Székely, M. A. Steel and P. L. Erdős (1993), doi:10.1006/aama.1993.1011The same coordinates
N. Goldman (1993), doi:10.1007/BF00166252The 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 contributorsArb, the ball arithmetic of the R2 intervals
Tim Peters, int_to_decimal in Lib/_pylong.py, CPython 3.12The 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) 30The papers that define SplitMix, xorshift and xorshift64*
N. Lartillot, T. Lepage and S. Blanquart (2009), doi:10.1093/bioinformatics/btp368PhyloBayes, against whose source PB_dayhoff4 was checked

The full list of references, with DOIs, is in GUIDE.md in the package, under "References".

← back to the tools index