Allele-Restricted Prime Implicants for Pseudogene Transcription

Pseudogenes are broken copies of protein-coding genes. Yet some of them are still transcribed into RNA, and some of those RNAs regulate their parent gene. Nobody knows which small combination of sequence features switches a pseudogene on. Mouse strains give a natural experiment for this question. The same pseudogene can be transcribed in one inbred strain and silent in another, and roughly 15% of the mouse pseudogene repertoire is transcribed across 18 strains (Sisu et al.). We propose to train a sequence model that predicts pseudogene transcription, then explain it with prime implicants: a smallest set of input positions that, once fixed, guarantees the model's prediction no matter how the remaining positions are set.

The twist is where "no matter how" ranges. Standard practice asks for invariance under arbitrary substitutions or mean-imputed backgrounds. We restrict the unfixed positions to the alleles actually observed across strains, meaning the DNA variants that real mice carry. Three things follow. The perturbed sequences stay biologically realistic, which removes the out-of-distribution artifacts that plague masking-based explanations. The search space becomes small and discrete, so exact, verified prime implicants can be computed. And each explanation becomes a falsifiable genetic prediction: any held-out strain carrying the prime-implicant alleles should show the predicted transcription state.

Core Claim

Explanations of genomic models become both provably sufficient and empirically checkable when the perturbation space is defined by natural variation instead of arbitrary edits. We expect allele-restricted prime implicants to predict held-out-strain pseudogene transcription better than three alternatives: explanations computed under unrestricted nucleotide perturbation, heuristic greedy subsets, and single-variant mutagenesis. Pseudogenes are the right testbed for three reasons. Their activity is strain-variable, their regulatory logic is expected to be combinatorial, since "resurrection" may require a newly acquired promoter plus a permissive flank (Pei et al.), and they sit in the unannotated genomic space where 72% of initiation events occur outside canonical promoters (Grapotte et al.).

Relation to Prior Work

Two papers are the closest neighbours, and both supply method rather than answer our question.

Carter et al. introduced sufficient input subsets (SIS), found by greedy backward deletion with mean imputation. They showed that the subsets recovered known motifs across 422 transcription-factor binding models. We reuse the backward-selection idea, but we change two things: the perturbation space, and the certification step. They offer no formal sufficiency guarantee and never touch pseudogenes.

Grapotte et al. trained CNNs on 50bp flanks that predict CAGE initiation at microsatellites, and interpreted them with single-nucleotide in silico mutagenesis. We borrow their architecture and data style. Our interpretation is combinatorial rather than one-position-at-a-time.

Two lines of work shape the design as constraints and motivation. Bassan et al. report that heuristic methods such as SIS and Anchors produce truly sufficient explanations less than 25% of the time when formally checked. That finding is what motivates certification here. Weinbauer et al. show that prime implicants on molecular graphs are sensitive to the decision threshold and to out-of-distribution cropping. Only 3% of their explanations were rated good or perfect at threshold 0.5, rising to 16% at 0.2. This is a warning that formal sufficiency alone does not deliver meaningful explanations; our in-distribution allele space is the proposed remedy.

The underlying theory comes from Ignatiev et al.. They prove that prime implicants are minimal hitting sets of minimal counterexamples. This duality lets us enumerate all prime implicants together with their duals, which here are minimal allele swaps that flip transcription, standing in for "silencing mutations." The hardness result of Waeldchen et al. says the general problem is intractable. Restricting to a handful of variant sites per locus is our way of staying on the tractable side, and we will report where that stops holding.

Research Program

Model. We will assemble strain-specific sequences around each annotated mouse pseudogene: the pseudogene body plus upstream and downstream flanks. We pair each with its transcription label per strain from Sisu et al.. Labels will count only uniquely mappable reads, because parent-pseudogene homology causes pervasive mismapping (Pei et al.). We will train a CNN in the style of Grapotte et al. to predict transcription from sequence. Loci are split by chromosome, and whole strains are held out entirely.

Explanation space. For each locus we define a variant set $V$: the positions where strains differ, together with the parent gene's aligned base where one exists. The explanation question becomes: which minimal subset $S \subseteq V$, fixed at the query strain's alleles, forces the model's call for every observed-allele assignment of $V \setminus S$?

Solving. When $|V|$ is small, sufficiency is checked by exhaustive enumeration of the assignments. When it is larger, we use the abstraction-refinement verifier of Bassan et al. We then enumerate all prime implicants and dual counterexamples through hitting-set duality. Enumerating all of them matters because paralogous and redundant sites would otherwise hide alternative explanations.

Second arm. The same procedure will be applied to human duplicated pseudogenes. There, $V$ is the set of differences between the pseudogene and its parent's promoter region, and labels are FANTOM5 CAGE signal (Noguchi et al.). This asks which inherited-versus-acquired differences are sufficient for activity.

Baselines

The naive reference is the per-locus majority transcription state, and separately the model's own prediction for a held-out strain with no explanation at all. Every explanation-based prediction must beat the majority state to be meaningful. It must also be compared against the raw model to show that compressing the model to a prime implicant loses little.

The strongest existing explanation method is SIS from Carter et al., with its original mean imputation. We will run it on the same trained model, the same loci, and the same threshold sweep. The file gives no numerical genomics result for it. The relevant reported figure is Bassan et al.'s: heuristic SIS/Anchors explanations are sufficient under formal checking less than 25% of the time. Beating SIS means two things. First, a higher certified sufficiency rate under the allele space. Second, higher held-out-strain agreement at equal or smaller explanation size.

In silico single-variant mutagenesis, as used by Grapotte et al., is run over exactly the same variant set $V$. Its top-scoring variants form a subset matched in size to our explanations. Integrated Gradients, restricted to $V$, is also matched in size.

The key ablation keeps our exact prime-implicant solver but changes the perturbation space. In one version, unfixed positions may take any nucleotide; in another, they are mean-imputed. This isolates whether the gain comes from the allele restriction or merely from formal solving.

For model quality, Grapotte et al. report a Spearman correlation above 0.65 between predicted and observed CAGE signal across 14 microsatellite classes. We treat that as the bar the human-arm model should approach. We found no reported result on Lacuna for predicting strain-specific pseudogene transcription.

All methods share the same model, the same data, and the same per-locus compute budget. Heuristic methods receive the same wall-clock allowance as the solver.

Why not just…?

Why not just run a genetic association test of transcription state against strain variants? This is the most serious threat, because it needs no model. With 18 strains, however, association is underpowered, and it is confounded by shared haplotype blocks: correlated variants cannot be told apart. It also cannot express conjunctions, such as "variant A and variant B together are required." Our model pools evidence across thousands of loci. We will run per-locus association (Fisher tests and a lasso over $V$) as a baseline on held-out strains. If association matches allele-restricted prime implicants on agreement, the explanation machinery adds nothing at this scale, and we will say so.

Why not just use in silico saturation mutagenesis? When two redundant sites each suffice, mutating either alone shows no effect, so mutagenesis calls both unimportant. This is exactly the combinatorial case that hitting-set reasoning handles (Ignatiev et al.). The matched-size comparison on held-out strains, stratified by the number of prime implicants per locus, will show whether the advantage is concentrated where redundancy exists. If it is not, the combinatorial story fails.

Why not just use SIS, which already recovered motifs? Recovering a motif does not establish sufficiency. Formal checks find heuristic subsets sufficient less than a quarter of the time (Bassan et al.). Mean imputation also creates sequences that no genome contains. The ablation that runs SIS with allele-restricted backgrounds tells us how much of the benefit plain SIS could capture with a better background alone.

Proposed Experiments

The decisive check is held-out-strain agreement. For each held-out strain and locus, we find every prime implicant (computed from training strains) whose alleles the strain carries. We then ask whether its observed transcription matches the implied state. We report this agreement, coverage, and explanation size for every baseline, sweeping the decision threshold to address the sensitivity Weinbauer et al. observed.

Second, we measure certified sufficiency for each method under the allele space. Ours is 100% by construction; the question is how far the heuristics fall.

Third, we test biological plausibility. Are prime-implicant variants enriched in microsatellites and known transcription-factor motifs, relative to size-matched random subsets of $V$? The dual counterexamples, which predict minimal silencing swaps, should concentrate at the same elements.

Finally, in the human arm, we ask whether prime implicants for active duplicated pseudogenes more often fall on acquired, non-parental differences than on inherited ones. This would be the first quantitative test of the "novel promoter" account of resurrection that Pei et al. leave open.

A negative result would still be informative. Unrestricted-space explanations agreeing as well as ours would mean out-of-distribution artifacts matter less in genomics than feared. Association matching us would bound the value of model-based explanation at strain-panel scale.