Trading running time for memory in phylogenetic likelihood computations

The revolution in wet-lab sequencing techniques that has given rise to a plethora of whole-genome or whole-transcriptome sequencing projects, often targeting 50 up to 1000 species, poses new challenges for efficiently computing the phylogenetic likelihood function both for phylogenetic inference and statistical post-analysis purposes. The phylogenetic likelihood function as deployed in maximum likelihood and Bayesian inference programs consumes the vast majority of computational resources, that is, memory and CPU time. Here, we introduce and implement a novel, general, and versatile concept to trade additional computations for memory consumption in the likelihood function which exhibits a surprisingly small impact on overall execution times. When trading 50% of the required RAM for additional computations, the average execution time increase because of additional computations amounts to only 15%. We demonstrate that, for a phylogeny with n species only log(n) + 2 memory space is required for computing the likelihood. This is a promising result given the exponential growth of molecular datasets.