Phylogenetic inference should be impossible. The number of trees that could explain a set of sequences grows superexponentially with the number of sequences, the landscape of those trees is quite rugged, and the problem is NP-complete. And yet we routinely infer trees on thousands, and these days even millions, of sequences.

I believe that the reason phylogenetic inference works at all is due to two classical ideas: tree traversal and local search. Nevertheless, phylogenetic inference is still very computationally expensive, motivating continued research on how to do better.

In this post I will describe a new approach, led by Lena Collienne, that merges deep learning with these classical ideas. The paper, Unifying phylogenetic traversal and deep learning to guide tree exploration, is now out in Systematic Biology.

Two ideas drive all successful algorithms in parsimony- and likelihood-based phylogenetics.

The first is that a good phylogenetic algorithm never looks at the sequence alignment as a naked, structureless block of letters. It always reads the alignment through a tree. The Fitch and Felsenstein algorithms are the canonical examples: given a tree, they walk over it with a dynamic program and ask how well the alignment fits on that tree. Thus alignments are always interpreted in the context of an evolutionary history, which is exactly the object we care about.

The second idea is local search. You start from some reasonable tree, generate its neighbors via small rearrangements, score each one with the dynamic program above, and move to the best neighbor. Repeat until you can’t improve. This is important because the set of not-horrible trees for a given sequence alignment is a microscopic fraction of the super-exponential set of possible trees, and local moves keep us close to not-horrible trees.

I love both of these ideas, and I think they will persist well into the future. However, there is still a gap. I would like to have an algorithm that makes intelligent choices about what local modifications to pursue, and I think that deep learning is the vehicle that is going to get us there. This work has some precedent in, for example, parsimony proposals for Bayesian phylogenetics, and Dana Azouri’s work on summary statistics for move choice and reinforcement learning for phylogenetics.

There has been a lot of creative work applying deep learning to the problem of phylogenetic inference. People have treated alignments like images and inferred quartets with neural networks, merged those quartets into trees, learned to predict distance matrices straight from sequences, and used GANs to construct a phylogeny. These are clever and worthy approaches, but they are not yet delivering the qualitative improvements we’ve seen over classical approaches in other fields, such as image labeling, protein structure prediction, or any one of the wild capabilities LLMs have now.

Notice what most of them have in common. They take the raw alignment as input, treating it as a structureless block, which classical phylogenetics never does. And they try to produce a whole tree in a single forward pass, without local search. From my perspective, both of the ideas that make phylogenetics work have gone missing.

So: could we do deep learning that keeps the two things we already know make phylogenetics work?

Our answer is a model called DPVT, for Deep neural networks for Phylogenetics Via Traversal. It is built around exactly those two ideas.

For the first idea, we don’t hand the network the raw alignment. We first run a dynamic program (Fitch) on the alignment in the context of a candidate tree, and feed the network the result: the mutations reconstructed along each edge. The network learns from the alignment as seen through a tree, just like the classical algorithms do. The architecture itself is a recurrent neural network shaped like the tree, traversing it up from the leaves and back down again so that every edge sees all the information on both sides of it. Because it does a tree traversal, the architecture can be applied to trees of any size. It has two components: the first finds useful features (and is identical across sites), and the second classifies each edge (after a pooling layer across sites).

For the second idea, the goal of the model is to guide local search. Rather than predicting a whole tree, DPVT looks at a given tree and predicts, for each edge, whether that edge belongs in an optimal tree or not. The point is to find the parts of the tree that need fixing, which is precisely the information a local search wants in order to decide where to make its next move.

For this first paper we kept the goal deliberately simple: predict, for each edge, whether it is present in a maximum parsimony tree. That turns out to be an NP-complete problem, so it captures a hard piece of phylogenetic inference.

Does it work? It does, and better than I expected. On simulated data the model reaches AUROC values up to 0.98, well above the 0.43–0.45 of a baseline that flags edges carrying reversions, a classic sign of a misplaced edge. More importantly, once the training trees are large enough, the model generalizes well beyond them. Trained only on simulated 50-leaf trees, it reaches AUROC values of 0.92 and higher on real viral, mammalian, and protein-family datasets, including a rotavirus tree with 452 sequences. (Training on 25-leaf trees wasn’t enough.) We can also train directly on real data. Models trained on mammalian alignments from OrthoMaM match the best simulation-trained model, with AUROC values of 0.92 and higher on held-out real data. The exception is the PANDIT protein families (0.78–0.81), whose trees average 24 leaves, far smaller than the 152-leaf average of the training trees.

This is a stepping stone and not the destination. DPVT predicts where a tree is wrong, but it does not yet do the search itself. It is currently limited to parsimony, and the version that pools across sites with a transformer is still very memory-hungry.

Our next steps are to:

• Understand what DPVT is learning, and whether we can distill that into a deterministic algorithm.
• Extend the algorithm to propose moves rather than bad edges.
• Extend to likelihood-based inference.
• Investigate whether we can find moves in an analogous way for the history DAG, a structure that compactly captures whole ensembles of parsimony trees.

The overall theme here, which I now emphasize on our redesigned home page, is to use deep learning in a way that respects the underlying structure of the data and the problem. This theme really spans all of our recent methodological work.

Many thanks to Lena Collienne, who led this project. Lena is a phylogenetics theorist by training, and gradually pivoted to this style of methods work in my group. Watching her take the leap, learn deep learning tooling, and then drive the whole thing to completion was a joy. She has since landed a lectureship (equivalent to tenure-track assistant professor) at the School of Computing at the University of Otago in Dunedin, New Zealand, back in the country where she did her PhD and exactly the setting she was hoping for. If this work interests you, she is building her group! I did a postdoc in NZ and it was one of the best choices I ever made.

[True story: When I learned that I had the opportunity to go work with Mike Steel in NZ, I was so excited that I was jumping up and down, including in an elevator. I broke the elevator with my jumping and had to get rescued by the elevator technician. They levered open the door and I crawled out with my buzz intact.]

Thanks to Harry Richman, David Rich, Mary Barker, and Chris Jennings-Shaffer, and to Marc Suchard for feedback on an earlier version.

This work was supported by NIH grant R01-AI162611 and the HHMI.