File(s) under permanent embargo
A sub-quadratic time and space complexity solution for the dated tree reconciliation problem for select tree topologies
conference contribution
posted on 2023-05-23, 10:55 authored by Drinkwater, B, Michael CharlestonMichael CharlestonRecently 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.
History
Publication title
Algorithms in Bioinformatics 15th International Workshop, WABI 2015 ProceedingsVolume
LNCS 9289Editors
M Pop, H TouzetPagination
93-107ISBN
978-3-662-48220-9Department/School
School of Natural SciencesPublisher
GermanyPlace of publication
SpringerEvent title
Workshop on Algorithms in Bioinformatics 2015Event Venue
Atlanta, USADate of Event (Start Date)
2015-09-10Date of Event (End Date)
2015-09-12Rights statement
Copyright 2015 Springer-VerlagRepository Status
- Restricted