Phylogeny inference under the general Markov model using MST-backbone

Abstract

MotivationPhylogeny inference via maximum likelihood is NP-hard. Current methods make simplifying assumptions such as stationarity, homogeneity, and time-reversibility for computational ease. The stationarity assumption is violated by empirical observations of GC content evolution, and might systematically bias phylogeny inference. The general Markov model (GM) is a suitable alternative to stationary models because it allows for the evolution of GC content. Related work on the GM model has predominantly focused on inferring unrooted trees using either the log-det distance or phylogenetic invariants. MethodsWe adapted the structural EM framework to perform tree search under the GM model (SEM-GM). Additionally, we implemented a minimum spanning tree framework called MST-backbone to improve the scalability of SEM-GM by constraining search through tree space. MST-backbone(SEM-GM) was used to infer unrooted trees, which are subsequently rooted under the GM model; the latter procedure is called rSEM-GM. We compared our method with RAxML-NG, IQ-TREE, and FastTree on simulated data. We validated our methods on six empirical datasets. ResultsEstimated experimental phylogenies are rooted with high accuracy under the GM model (recall ranging from 80% to 94%). However, virus phylogenies are not realistically rooted, suggesting that the GM model may be overtrained on some empirical datasets. The comparative analysis of simulated data suggests that MST-backbone(SEM-GM) and FastTree scale linearly whereas rSEM-GM, RAxML-NG, and IQ-TREE scale quadratically. The results on empirical data suggest that it is not necessary to use the general time-reversible model for computational ease. Availabilityhttps://github.com/prabhavk/mst-backbone-sem-gm Contactprabhav.kalaghatgi@molgen.mpg.de Supplementary informationSupplementary data are available online