A sub-quadratic time and space complexity solution for the dated tree reconciliation problem for select tree topologies

Recently coevolutionary analysis has turned to tree topology, specifically the unbalanced nature of evolutionary trees, as a means to reduce the asymptotic complexity associated with inferring coevolutionary interrelationships that exist between organismal trees. The leveraging of tree topology for coevolutionary analysis has been shown to be highly successful, with one recent result demonstrating a logarithmic space complexity reduction for the dated tree reconciliation problem. In this work we build on this prior result providing a reduced complexity bound by applying a new model to construct the dynamic programming table. The new complexity bound is the first sub quadratic running time solution for the dated tree reconciliation problem for selected tree topologies and is shown to be, in practice, the fastest method for solving the dated tree reconciliation problem for expected evolutionary trees. Our theoretical results are then validated using a combination of synthetic and biological data with our proposed model shown to save almost O(√n) space while finishing in half the time compared to existing methodologies.