eCite Digital Repository

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


Drinkwater, B and Charleston, MA, A sub-quadratic time and space complexity solution for the dated tree reconciliation problem for select tree topologies, Algorithms in Bioinformatics 15th International Workshop, WABI 2015 Proceedings, 10-12 September 2015, Atlanta, USA, pp. 93-107. ISBN 978-3-662-48220-9 (2015) [Refereed Conference Paper]

Restricted - Request a copy

Copyright Statement

Copyright 2015 Springer-Verlag

DOI: doi:10.1007/978-3-662-48221-6_7


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.

Item Details

Item Type:Refereed Conference Paper
Keywords:coevolution, phylogeny, tree reconciliation, tree shape, NP-Hard
Research Division:Biological Sciences
Research Group:Bioinformatics and computational biology
Research Field:Bioinformatic methods development
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the biological sciences
UTAS Author:Charleston, MA (Professor Michael Charleston)
ID Code:106986
Year Published:2015
Web of Science® Times Cited:1
Deposited By:Mathematics and Physics
Deposited On:2016-02-29
Last Modified:2018-04-04

Repository Staff Only: item control page