Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction
Emil Sharafutdinov, Ingemar André · 2026
Read Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction by Emil Sharafutdinov, Ingemar André (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04119.txt.
Introduction
Emil Sharafutdinov and Ingemar André introduce a tree-conditioned edit-flow model for ancestral sequence reconstruction. The task is inferring extinct protein sequences at the internal nodes of a phylogenetic tree. Classical methods rest on continuous-time Markov models. They treat sites largely on their own. They handle insertions and deletions weakly, or not at all. Their model is built to edit, not just substitute. The paper is about proteins and their history.
Given two descendant sequences and their branch distances to a shared ancestor, the model reconstructs the ancestor. It uses paired two-way edit paths. The two are constrained to agree on a common state. On lab-evolved cases with only substitutions, it did not match the best classical method. It still did reasonably well. On natural homologues rich in insertions and deletions, it placed inferred evolutionary change most accurately.
Catalog record
| CREATOR | Emil Sharafutdinov, Ingemar André |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04119
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tree-Conditioned Edit Flows for Ancestral Sequence Reconstruction Emil Sharafutdinov, Ingemar André Abstract Ancestral sequence reconstruction (ASR) aims to infer extinct protein sequences at internal nodes of a phylogenetic tree. Classical ASR methods are typically based on continuous-time Markov substitution models, but they treat sites largely independently and handle insertions and deletions only weakly or not at all. We introduce a tree-conditioned edit-flow model for variable-length ASR. Given two descendant sequences and their branch distances to a shared ancestor, the model reconstructs the ancestor through paired bidirectional edit trajectories constrained to agree on a common ancestral state. On a benchmark of experimentally evolved sequences with only context-independent substitutions, the model does not match the accuracy of the best classical method, yet still achieves reasonable performance despite being trained on natural sequences that include insertions, deletions, and substitutions. On a benchmark of natural homologous sequences with abundant insertions and deletions, the model most accurately localizes inferred evolutionary change. 1 Introduction Proteins are the result of evolutionary processes that can be traced back to when life first emerged on Earth. The sequences of proteins carry an evolutionary record of this process, but the ancestral states that have given rise to modern proteins are not known. The concept of Ancestral Sequence Reconstruction (ASR), predicting sequences of extinct proteins using statistical models, was introduced in the early 1960s by Zuckerkandl and Pauling [ 24 ] . ASR has since become a key tool for studying the emergence of protein functions and for protein engineering [ 31 , 26 , 32 ] . Classical maximum-likelihood and Bayesian ASR methods [ 15 , 36 , 10 ] rely on continuous-time Markov substitution models with rate matrices that are fixed or only weakly context-dependent, treating each site as conditionally independent of the surrounding sequence even though real amino acid changes depend on structural, thermodynamic, and functional context [ 22 , 25 ] . A strength of these methods is that inference is global over the phylogenetic tree: all leaves, including distant outgroups, can inform each internal state through the tree likelihood [ 5 ] . However, insertion and deletion operations (indels) are either excluded entirely or ignored in the likelihood calculation, a significant restriction given their functional importance in protein evolution [ 30 , 34 , 9 ] . Indel-aware models such as ARPIP [ 13 ] introduce an explicit insertion–deletion process, but still combine this with site-wise ancestral character reconstruction rather than a sequence-contextual edit model. More recent neural approaches introduce greater expressivity in modeling of sequence patterns, but do not directly consider phylogenetic trees. AutoregressiveASR [ 2 ] processes each branch independently and collapses indels into a 21st token class, conflating indels with substitutions in the modeling. BetaReconstruct [ 4 ] treats ASR as a next-token prediction. This approach is alignment-independent and can account for more complex indel evolution, but does not consider tree topology, branch lengths and that ancestors must explain both descendants. With an accurate phylogenetic tree, classical methods substantially outperform BetaReconstruct, suggesting that phylogeny may be highly beneficial for inference of ancestors. Here, we introduce Lærad , a tree-conditioned paired edit-flow model for ancestral sequence reconstruction. Lærad treats ASR as a branch-conditioned edit process with explicit substitutions, insertions, and deletions; uses paired cross-attention so both descendants inform each child-to-ancestor edit field; and enforces consistency through bidirectional bridge losses and exact-LCA consistency across multiple descendant pairs. At inference time, it decodes candidate ancestors from both descendants under branch-length constraints and reconciles the two directional reconstructions to recover internal nodes recursively across the tree. 2 Background Figure 1: A rooted phylogenetic tree with leaves A , B , C and internal nodes D , E (root). Node D=\operatorname{LCA}(A,B) is the deepest shared ancestor of the sibling pair (A,B) ; E=\operatorname{LCA}(A,B,C) is the root. The length of branches indicate the evolutionary distance between endpoints. Phylogenetic trees. Hypothesized evolutionary relationships among a set of biological sequences are represented on a phylogenetic tree. A rooted tree T=(V,E) partitions nodes into observed leaves L\subset V and unobserved internal nodes I=V\setminus L . Nodes on the tree are connected by edges. In our implementation, lengths of tree edges are converted into edit-operation budgets by estimating internal states with Fitch parsimony [ 6 ] and counting substitutions, insertions, and deletions along each edge. These budgets constrain how much change each reconstruction is allowed to spend; the Fitch states are used only to assign edge distances, not as supervised ancestral targets. For any two nodes a and b , their lowest common ancestor \operatorname{LCA}(a,b) is the deepest (from the root) internal node that has a and b as its descendants. In Figure 1 , D=\operatorname{LCA}(A,B) and E=\operatorname{LCA}(A,B,C) . Ancestral Sequence Reconstruction. Classical protein ASR typically starts from a fixed multiple sequence alignment (MSA) of the observed leaf sequences and a phylogenetic tree. At each aligned site j , a continuous-time Markov substitution model computes the probability of the observed leaf states x_{L,j} by summing over all possible internal states: p(x_{L,j}\mid T,Q)=\sum_{h_{I,j}}\pi(h_{r,j})\prod_{(u,v)\in E}\left[e^{t_{uv}Q}\right]_{h_{u,j},h_{v,j}}, where h_{v,j},h_{u,j} are the amino-acid states and are unknown at internal nodes ( u,v\in V\setminus L ), \pi(h_{r,j}) is the root-state probability under the equilibrium distribution of Q , and \left[e^{t_{uv}Q}\right]_{h_{u,j},h_{v,j}} is the probability of changing from amino acid h_{u,j} to h_{v,j} along branch (u,v) of length t_{uv} . The rate matrix Q is usually chosen from empirically estimated protein substitution matrices such as JTT [ 12 ] , WAG [ 35 ] , or LG [ 18 ] . In practice, these models are commonly extended with among-site rate variation, usually through a discrete Gamma distribution over site-specific rate modifiers [ 37 ] ; we give the full likelihood in Appendix A.1 . Given the site-wise likelihoods, ancestral states are commonly inferred either jointly or marginally. Joint reconstruction seeks the assignment of all internal states that maximizes the posterior over the whole tree, and can be solved efficiently by dynamic programming [ 28 ] . Marginal reconstruction instead estimates the most probable state at each internal node and site separately, conditioning on the observed leaves [ 36 ] . These two procedures optimize different objectives and can disagree at individual positions. More broadly, classical ASR remains strongest when evolution is well described as independent substitutions on a fixed alignment; modeling context-dependent insertions, deletions, and sequence-level edit structure requires a different formulation. 3 Related Work EditFlows. Building on recent discrete flow matching methods for discrete generative modeling, edit flows lift flow matching from fixed-length token spaces to variable-length sequences by defining transitions through elementary edit operations [ 1 , 8 ] . Let \mathcal{V} denote a discrete vocabulary and let \mathcal{X}=\bigcup_{n\geq 0}\mathcal{V}^{n} be the space of all finite sequences over that vocabulary. A continuous-time Markov chain on \mathcal{X} is specified by transition rates u_{t}^{\theta}(y\mid x) , where x,y\in\mathcal{X} and u_{t}^{\theta}(y\mid x) is nonzero only when y can be obtained from x by one elementary edit operation. The three elementary edits are insertion, deletion, and substitution. Insertions increase sequence length by one, deletions decrease it by one, and substitutions preserve length. This makes edit flows a natural model class for variable-length sequence evolution. A useful feature of edit flows is that they separate where an edit happens from what symbol it