eCite Digital Repository

RASCAL: A randomized approach for coevolutionary analysis


Drinkwater, B and Charleston, MA, RASCAL: A randomized approach for coevolutionary analysis, Journal of Computational Biology, 23, (3) pp. 218-227. ISSN 1066-5277 (2016) [Refereed Article]


Copyright Statement

2012 Mary Ann Liebert, Inc. publishers. All rights reserved, USA and worldwide.

DOI: doi:10.1089/cmb.2015.0111


A popular method for coevolutionary inference is cophylogenetic reconstruction where the branch length of the phylogenies have been previously derived. This approach, unlike the more generalized reconstruction techniques that are NP-Hard, can reconcile the shared evolutionary history of a pair of phylogenetic trees in polynomial time. This approach, while proven to be highly successful, requires a high polynomial running time. This is quickly becoming a limiting factor of this approach due to the continual increase in size of coevolutionary data sets. One existing method that combats this issue proposes a trade-off of accuracy for an asymptotic time complexity reduction. This technique in almost 70% of cases converges on Pareto optimal solutions in linear time. We build on this prior work by proposing an alternate linear time algorithm (RASCAL) that offers a significant accuracy increase, with RASCAL converging on Pareto optimal solutions in 85% of cases and unlike prior methods can ensure, with high probability, that all optimal solutions can be recovered, provided sufficient replicates are performed.

Item Details

Item Type:Refereed Article
Keywords:coevolution, phylogeny, randomisation, 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, MA (Professor Michael Charleston)
ID Code:114965
Year Published:2016
Web of Science® Times Cited:4
Deposited By:Mathematics and Physics
Deposited On:2017-03-03
Last Modified:2018-03-18
Downloads:152 View Download Statistics

Repository Staff Only: item control page