Learned Branching for Ancestral Cis-Regulatory Reconstruction

When species diverge, most of the interesting evolution happens not in the genes that encode proteins but in short non-coding DNA switches — enhancers and promoters, collectively called cis-regulatory elements — that decide where, when, and how strongly each gene is turned on. These switches evolve by gaining, losing, and relocating the short binding sites that transcription factors recognize, so the regulatory "grammar" (which sites, in which order, at what spacing) turns over rapidly even while the proteins and the downstream body plan stay conserved. Reconstructing that history — deciding which binding sites existed in a shared ancestor and when each was gained or lost along the phylogeny — is a huge combinatorial search over an exponentially large space of possible ancestral configurations. The current best tool, EMMA, handles it with a dynamic-programming alignment engine that must assume nearly independent, local evolutionary events and can only compare sequences pairwise; it cannot enforce the non-local grammar rules that real enhancers obey, such as a repressor silencing any activator within roughly 100–150 base pairs of it.

This proposal asks a question that sits exactly between two literatures that have never touched: can the machinery of machine-learning-guided logic solving — a symbolic solver that keeps mathematical guarantees while a learned model reorders its search choices — be turned loose on ancestral cis-regulatory reconstruction? The answer I want to establish is yes, and that doing so unlocks a regime (deep divergence, many species, hard grammar constraints) where both dynamic programming and default solver heuristics break down.

Core Claim

Ancestral cis-regulatory reconstruction should be formulated as a constraint optimization problem over a phylogeny, searched by a constraint programming or SMT solver whose branching is advised by a fast learned ranker in the style of cvc5's learned quantifier selection. The learned model never decides correctness; it only orders the solver's choices, so bad advice costs runtime but the solver's output is always an exactly optimal, grammar-feasible evolutionary history. The claim is that this combination recovers ancestral binding-site configurations at divergence levels and under combinatorial constraints where EMMA's dynamic programming — the strongest existing method, reporting an AUC of 0.95 at 0.8 divergence on its own benchmark — degrades or cannot be applied at all.

The two closest existing works define the gap. EMMA Alignment and Prediction of cis-Regulatory Modules Based on a Probabilistic Model of Evolution models binding-site gain and loss with real evolutionary mechanics (Halpern–Bruno affinity evolution, indels, thresholded site death), but its dynamic-programming engine restricts it to pairwise, locally independent events — it cannot express "this enhancer requires three distinct site types within a 164 bp window, no two sites overlapping, and no repressor adjacent to an activator" across eight species jointly. CPModule Cis-regulatory module detection using constraint programming proves a declarative constraint solver can enforce exactly such proximity, coverage, and redundancy constraints at scale, but it is purely within-species, purely static, and uses no learning anywhere. Neither work does what this proposal does: a phylogenetic, evolution-aware constraint model searched with learned branching. The advisor architecture itself is borrowed from the logic-solving side, where it is an established design principle Logic Solvers and Machine Learning: The Next Frontier with demonstrated large wins, including a 22.46% increase in solved problems from learned quantifier selection in cvc5 Machine learning for quantifier selection in cvc5 and 290.9% more holdout problems solved from learned term instantiation Towards Learning Quantifier Instantiation in SMT.

Research Program

The first deliverable is the encoding. Candidate binding sites in each extant species are precomputed by scanning sequences with position weight matrices, a simple scoring model for how well a DNA stretch matches a transcription factor's preferred binding pattern, as CPModule does with Clover. The solver's decision variables then assign, for every candidate site at every node of the phylogeny, whether that site is present or absent, with gain and loss events linking parent to child. The objective is a weighted parsimony or likelihood over those events:

$$\min_{s} \; \sum_{e} \lambda_{e}^{\text{gain}}\, \mathbb{1}[\text{gain on branch } e] + \lambda_{e}^{\text{loss}}\, \mathbb{1}[\text{loss on branch } e] \quad \text{s.t.} \quad s \in \mathcal{G}$$

Here $s$ is the full assignment of site presences across the tree, the sum ranges over phylogeny branches $e$, the weights $\lambda$ come from the same Halpern–Bruno affinity-evolution rates EMMA uses, and $\mathcal{G}$ is the grammar constraint set. Crucially, $\mathcal{G}$ can hold the non-local rules that dynamic programming cannot: the proximity window $\theta$ from CPModule, minimum spacing to prevent steric clash, and — this is what makes the biology real — short-range repression and synergistic activation windows taken directly from the thermodynamic models of He et al., who showed that a repressor quenching nearby activators and multiplicative activator synergy are what actually explain enhancer readouts, raising average fit correlation from 0.516 to 0.587 as these mechanisms were added Thermodynamics-Based Models of Transcriptional Regulation by Enhancers: The Roles of Synergistic Activation, Cooperative Binding and Short-Range Repression.

The second deliverable is the advisor. Following the cvc5 design, a LightGBM gradient-boosted tree model — chosen deliberately over heavier graph neural networks because the constraint-solving literature warns that deep-model inference latency can outweigh the search pruning it buys Combining Constraint Programming and Machine Learning: From Current Progress to Future Opportunities — ranks the solver's next branching choices (which site variable to decide, gain or loss first). Its features are the analogs of cvc5's syntax path features: the weight-matrix score of the candidate site, the branch's divergence level, distance to the grammar window's edge, remaining constraint slack, and the identities of neighboring sites. One design lesson is copied verbatim from cvc5: the advisor filters probabilistically and never truncates, because hard truncation risks missing the critical decision that unlocks the optimum. Training data comes from solver traces on simulated evolutionary histories where the true ancestral configuration is known, so the ranker learns from ground truth that this domain uniquely provides — sidestepping the "no ground truth for intermediate decisions" problem the CP-ML survey identifies for general solving.

The third deliverable is the analysis that the guarantees survive: because the learned model only reorders choices, the solver remains sound and complete, and every returned ancestral grammar comes with a certificate of optimality under the stated model — something no stochastic search method can offer.

Baselines

The naive reference point is progressive alignment plus motif scanning, the standard pipeline EMMA was built to improve; on EMMA's own simulated benchmark at 0.7 divergence, EMMA outperformed the Lagan aligner by 12–13% in binding-site conservation sensitivity Alignment and Prediction of cis-Regulatory Modules Based on a Probabilistic Model of Evolution, so anything at or below that floor is a failure. The strongest existing competitor is EMMA2 itself, which achieved an AUC of 0.95 at 0.8 divergence, against 0.87 for Stubb and 0.82 for Morph, on the simulated Drosophila benchmark Alignment and Prediction of cis-Regulatory Modules Based on a Probabilistic Model of Evolution; it will be run from its published implementation on exactly the same simulated and RedFly data, the same weight matrices, the same divergence grid, and the same wall-clock budget as our solver, so any comparison is about search method, not data or tuning. Beating it means strictly higher binding-site reconstruction sensitivity at divergence of 0.8 and above, or solving at all on grammar-constrained, many-species instances it cannot encode. A third baseline is stochastic local search — simulated annealing over the same objective and constraints, mirroring the optimizer in CODA Machine-guided design of cell-type-targeting cis-regulatory elements — given the same compute and the same candidate sites, scored on solution quality and on how often its outputs violate the hard grammar constraints. The essential ablation is the identical constraint encoding run with the solver's default search heuristics and no advisor; it isolates exactly the ingredient this proposal adds, and it doubles as the direct descendant of CPModule, which on the planted benchmark of Xie et al. kept false positives under 1% with a motif-level correlation of 0.57 where competing itemset tools crashed or failed to terminate within two days Cis-regulatory module detection using constraint programming.

Why not just…?

Why not just use EMMA's dynamic programming? This is the most serious objection, because EMMA is genuinely strong: 0.95 AUC at 0.8 divergence is hard to beat, and at moderate divergence it may well remain the method of choice. The honest answer is that the win is claimed for a different regime. Dynamic programming needs local independence and pairwise comparison, while the biology is non-local — short-range repression acts over a 100–150 bp neighborhood and activation is multiplicative across sites, mechanisms that measurably improved expression fits in Thermodynamics-Based Models of Transcriptional Regulation by Enhancers — and joint constraints across more than two species explode the pair-HMM state space. The experiments include a head-to-head on EMMA's own simulated benchmark at matched divergence precisely to locate the crossover point, and if no crossover appears even at divergence 1.0 without grammar constraints, that result will be reported as a boundary on the method.

Why not just do simulated annealing over the objective, like CODA does for design? CODA's annealing over a deep predictor achieves impressive design results — 94.1% of synthetic elements drove target specificity in vitro Machine-guided design of cell-type-targeting cis-regulatory elements — and an annealing baseline over our own objective is cheap to run. But annealing is incomplete: it cannot certify that no feasible ancestral configuration exists under a given parsimony budget, and it can return grammars that violate spacing or repression-window constraints, which is fatal when the constraints are the scientific claim. The experiment that settles this measures the constraint-violation rate and optimality gap of annealing against the solver on identical instances; the logic-solving literature's core finding is that learned advice inside a deductive engine gets neural-pattern exploitation without giving up exactness Logic Solvers and Machine Learning: The Next Frontier.

Why not just extend the CP encoding and skip the ML advisor? This is the ablation, and it is a real threat: CPModule shows default declarative search already scales where classical tools fail. The counter-evidence is that on hard structured instances, learned ranking has repeatedly paid for its latency — 22.46% more problems solved in cvc5 Machine learning for quantifier selection in cvc5, 284.4% more cumulative problems in the looping instantiation setting Towards Learning Quantifier Instantiation in SMT — and phylogenetic site trees with dense grammar constraints are exactly the kind of instance where branching order dominates runtime. The proposal's own experiment decides it: if the no-advisor ablation matches the advised solver within, say, 20% on solved instances at fixed timeout, the ML component is not earning its keep and the proposal's contribution reduces to the encoding alone, which would still be reported but with the claim narrowed accordingly.

Proposed Experiments

The first experiment uses EMMA's own simulation infrastructure: binding-site evolution under Halpern–Bruno dynamics with divergence swept from 0 to 1.0, plus real Drosophila CRMs from RedFly with known sites from FlyReg. Metrics are binding-site reconstruction sensitivity and site-position accuracy against the known truth, and CRM prediction AUC compared against EMMA's reported 0.95 at 0.8 divergence. The second experiment scales the constraint side: the planted-grammar design of Xie et al. (22 sequences, sites clustered in a 164 bp window, the full 516 weight matrices) extended from 2 to 8 simulated species with injected gain/loss events and hard grammar constraints, measuring where dynamic programming's state space explodes versus where the solver, with and without the advisor, still terminates; CPModule's demonstrated scalability on 516 motifs is the evidence this regime is reachable Cis-regulatory module detection using constraint programming. The third experiment probes the biology directly: on the yeast ribosomal promoter panel of 668 orthologous promoters across nine species, where expression is conserved at correlation r ≈ 0.9 despite rapid sequence turnover and 78% of binding-site mutations show no expression change Molecular dissection of the genetic mechanisms that underlie expression conservation in orthologous yeast ribosomal promoters, the solver searches for minimal sets of compensatory mutations consistent with grammar constraints — testing whether expression conservation can be explained as constrained search rather than lucky robustness. Throughout, runtime is decomposed into advisor latency versus branches pruned, directly addressing the overhead concern raised in Combining Constraint Programming and Machine Learning: From Current Progress to Future Opportunities.

The decisive checks are stated in advance. The idea succeeds if the advised solver strictly beats EMMA in sensitivity at divergence 0.8–1.0 or solves grammar-constrained multi-species instances EMMA cannot, while the ablation shows the advisor is necessary, not decorative. It fails if EMMA dominates at all divergences, or if default search matches learned search — and both failure modes are cheap to detect early on the simulated benchmark.