Differentiable Search of Evolutionary Trees

Inferring the most probable evolutionary tree given leaf nodes is an important problem in computational biology that reveals the evolutionary relationships between species. Due to the exponential growth in the number of possible tree topologies, finding the best tree in polynomial time becomes computationally infeasible. In this work, we propose a novel differentiable approach as an alternative to traditional heuristic-based combinatorial tree search methods in phylogeny. Our method provides a general framework that is applicable for many phylogenetic inference problems where the optimization can be performed based on a desired objective. We empirically evaluate our method using randomly generated trees of up to 128 leaves, with each node represented by a 256-length protein sequence. The optimization objective of our method is to find the most parsimonious tree (i.e., to minimize the total number of evolutionary changes in the tree). Our method exhibits promising convergence ($<1\$% error for trees up to 32 leaves, $<8\$% error up to 128 leaves, given only leaf node information), illustrating its potential in much broader phylogenetic inference problems and possible integration with end-to-end differentiable models.