Phylogenetics is the practice of reconstructing evolutionary history from molecular sequences such as DNA. It represents the inferred relationships between the sequences as an evolutionary tree, with splits in the tree representing evolutionary divergences.  

Our work advanced phylogenetics in both practical and theoretical directions. The primary intellectual merit of this work was a collection of foundational theoretical and algorithmic work that gives us new insight into the essential structures of phylogenetic inference, as well as foundations for new and efficient algorithms. These algorithms are for comparing collections of trees, understanding phylogenetic likelihoods, and for doing Bayesian phylogenetic inference in new and efficient ways.  

INTELLECTUL CONTRIBUTIONS  

Tree comparison: 

• Whidden & Matsen (Systematic Biology, 2015). Quantifying MCMC exploration of phylogenetic tree space: we use graph-theoretical tools to show that tree samplers get stuck in local peaks. 
• Whidden & Matsen (Theoretical Computer Science, 2017). Ricci Ollivier curvature of the rooted phylogenetic subtree “prune“ regraft graph: we show that "tree space" is quite inhomogeneous in terms of its curvature, meaning some parts are inherently easier to move around than others
• Gavryushkin, Whidden, & Matsen. (Journal of Mathematical Biology, 2017). The combinatorics of discrete time-trees, theory and open problems: we analyze the space of "timetrees", which are trees with time assigned to the internal nodes, and show that it's actually simpler than one might expect. 
• Billey, Konvalinka, & Matsen (Journal of Combinatorial Theory. Series A, 2017). On the enumeration of tanglegrams and tangled chains: we discover new integer series counting "tanglegrams", which are pairs of phylogenetic trees with connections between their leaves that are useful as means of tree comparison. 
• Matsen, Billey, Kas, & Konvalinka (Transactions on Computational Biology and Bioinformatics, 2018). Tanglegrams, A Reduction Tool for Mathematical Phylogenetics: we describe how these tanglegrams can reduce the amount of work require for computational biologists. 
• Whidden, & Matsen (Workshop on Analytic Algorithmics and Combinatorics, 2018). Efficiently Inferring Pairwise Subtree Prune-and-Regraft Adjacencies between Phylogenetic Trees: we develop time-optimal algorithms for constructing the sorts of graphs that proved essential for understanding MCMC behavior in our 2015 paper. 
• Whidden & Matsen (unpublished; arXiv). Chain Reduction Preserves the Unrooted Subtree Prune-and-Regraft Distance: we solve a long-standing conjecture establishing a key component of efficient tree-comparison methods. 

Phylogenetic likelihood function: 

• Dinh & Matsen (Annals of Applied Probability, 2017). The shape of the one-dimensional phylogenetic likelihood function: we analyze phylogenetic likelihood functions, showing that under simple models they are well-behaved but under more complex models they can have strange behavior, including a arbitrary number of local maxima. 
• Claywell, Dinh, Fourment, McCoy, & Matsen. (Molecular Biology and Evolution, 2017). A surrogate function for one-dimensional phylogenetic likelihoods: we show that a simple family of functions does a good job of approximating likelihood curves, and develop a library to use this surrogate family of functions for optimization and sampling.

Novel phylogenetic inference algorithms: 

• Dinh, Bilge, Zhang, & Matsen (International Conference on Machine Learning, 2017). Probabilistic Path Hamiltonian Monte Carlo: we extend the cutting-edge Hamiltonian Monte Carlo sampler to non-Euclidean spaces for the first time, resulting in a novel Bayesian phylogenetics algorithm. 
• Dinh, Ho, Suchard, & Matsen (Annals of Statistics, 2018). Consistency and convergence rate of phylogenetic inference via regularization: we extend and formalize a statistical framework for gene tree inference in the presence of external tree structure information.
• Dinh, Darling, & Matsen (Systematic Biology, 2017). Online Bayesian phylogenetic inference, theoretical foundations via Sequential Monte Carlo: we develop the theoretical foundations for the first online phylogenetic inference algorithm, which can progressively update phylogenetic inferences with new sequences as they arrive.
• Fourment, Claywell, Dinh, McCoy, Matsen & Darling (Systematic Biology, 2017). Effective online Bayesian phylogenetics via sequential Monte Carlo with guided proposals: we show sequential Monte Carlo to be an effective tool for online inference, namely that it can outperform classical batch algorithms for updating trees.
• Whidden, Claywell, Fisher, Magee, Fourment, & Matsen (submitted, 2018). Systematic exploration of the high likelihood set of phylogenetic tree topologies: we develop a new approach to Bayesian phylogenetics via systematic exploration, in which we explore out from local maxima. 
• Fourment, Magee, Whidden, Bilge, Matsen, Minin (submitted, 2018). 19 dubious ways to compute the marginal likelihood of a phylogenetic tree topology: we develop a component needed for this alternate direction for Bayesian phylogenetics, namely fast means of integrating out the continuous parameters of trees. 

BROADER IMPACTS:  

Our work on online phylogenetic inference stimulated special interest in the pathogen outbreak community, where two groups are working on incorporating it into the two main forks of the BEAST software package that is used by infectious disease researchers. This allows them to track pathogen evolution in real time. Our work on understanding the underpinnings of phylogenetic inference has allowed us to develop completely new means of doing Bayesian phylogenetic inference.  During the granting period, our group hosted 6 high school interns and 2 undergraduate summer students.

Last Modified: 11/30/2018
Modified by: Frederick A Matsen