A time and space complexity reduction for coevolutionary analysis of trees generated under both a Yule and Uniform model. (August 2015)

• Record Type: Journal Article
• Authors: Drinkwater, Benjamin; Charleston, Michael A.
• Is Part Of: Computational biology and chemistry. Volume 57(2015)
• Page Start: 61
• Page End: 71
• Publication Date: 2015-08
• Subjects: Coevolution -- Phylogeny -- Tree topology -- NP-Hard; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2015.02.003
• Languages: English
• ISSNs: 1476-9271

Abstract

Abstract : Graphical abstract: Abstract : Highlights: Introduces a more efficient data structure for coevolutionary analysis. Presents the first sub quadratic space approach for cophylogenetic reconstruction. Provides a logarithmic time complexity reduction for cophylogenetic reconstruction. Abstract: 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.