eCite Digital Repository

A time and space complexity reduction for coevolutionary analysis of trees generated under both a Yule and Uniform model


Drinkwater, B and Charleston, M, A time and space complexity reduction for coevolutionary analysis of trees generated under both a Yule and Uniform model, Computational Biology and Chemistry, 57 pp. 61-71. ISSN 1476-9271 (2015) [Refereed Article]

PDF (Preprint version)

Copyright Statement

Copyright 2015 Elsevier Ltd.

DOI: doi:10.1016/j.compbiolchem.2015.02.003


The topology or shape of evolutionary trees and their unbalanced nature has been a long standing area of interest in the field of phylogenetics. Coevolutionary analysis, which considers the evolutionary relationships between a pair of phylogenetic trees, has to date not considered leveraging this unbalanced nature as a means to reduce the complexity of coevolutionary analysis. In this work we apply previous analyses of tree shapes to improve the efficiency of inferring coevolutionary events. In particular, we use this prior research to derive a new data structure for inferring coevolutionary histories. Our new data structure is proven to provide a reduction in the time and space required to infer coevolutionary events. It is integrated into an existing framework for coevolutionary analysis and has been validated using both synthetic and previously published biological data sets. This proposed data structure performs twice as fast as algorithms implemented using existing data structures with no degradation in the algorithm's accuracy. As the coevolutionary data sets increase in size so too does the running time reduction provided by the newly proposed data structure. This is due to our data structure offering a logarithmic time and space complexity improvement. As a result, the proposed update to existing coevolutionary analysis algorithms outlined herein should enable the inference of larger coevolutionary systems in the future.

Item Details

Item Type:Refereed Article
Keywords:coevolution, phylogeny, tree topology, NP-hard
Research Division:Biological Sciences
Research Group:Genetics
Research Field:Genetics not elsewhere classified
Objective Division:Expanding Knowledge
Objective Group:Expanding knowledge
Objective Field:Expanding knowledge in the biological sciences
UTAS Author:Charleston, M (Professor Michael Charleston)
ID Code:108217
Year Published:2015
Web of Science® Times Cited:4
Deposited By:Mathematics and Physics
Deposited On:2016-04-13
Last Modified:2017-12-08
Downloads:209 View Download Statistics

Repository Staff Only: item control page