A General and Efficient Algorithm for the Likelihood of Diversification and Discrete-Trait Evolutionary Models.

As the size of phylogenetic trees and comparative data continue to grow and more complex models are developed to investigate the processes that gave rise to them, macroevolutionary analyses are becoming increasingly limited by computational requirements. Here, we introduce a novel algorithm, based on the "flow" of the differential equations that describe likelihoods along tree edges in backward time, to reduce redundancy in calculations and efficiently compute the likelihood of various macroevolutionary models. Our algorithm applies to several diversification models, including birth-death models and models that account for state- or time-dependent rates, as well as many commonly used models of discrete-trait evolution, and provides an alternative way to describe macroevolutionary model likelihoods. As a demonstration of our algorithm's utility, we implemented it for a popular class of state-dependent diversification models-BiSSE, MuSSE, and their extensions to hidden-states. Our implementation is available through the R package $\texttt{castor}$. We show that, for these models, our algorithm is one or more orders of magnitude faster than existing implementations when applied to large phylogenies. Our algorithm thus enables the fitting of state-dependent diversification models to modern massive phylogenies with millions of tips and may lead to potentially similar computational improvements for many other macroevolutionary models.