University Of Tasmania
DrinkwaterCharleston2015TimeAndSpace.pdf (457.04 kB)
Download file

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

Download (457.04 kB)
journal contribution
posted on 2023-05-18, 18:40 authored by Drinkwater, B, Michael CharlestonMichael Charleston
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.


Publication title

Computational Biology and Chemistry








School of Natural Sciences


Elsevier Sci Ltd

Place of publication

The Boulevard, Langford Lane, Kidlington, Oxford, England, Oxon, Ox5 1Gb

Rights statement

Copyright 2015 Elsevier Ltd.

Repository Status

  • Open

Socio-economic Objectives

Expanding knowledge in the biological sciences

Usage metrics