University Of Tasmania
RASCAL.pdf (573.98 kB)
Download file

RASCAL: A randomized approach for coevolutionary analysis

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


Publication title

Journal of Computational Biology








School of Natural Sciences


Mary Ann Liebert Inc Publ

Place of publication

2 Madison Avenue, Larchmont, USA, Ny, 10538

Rights statement

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

Repository Status

  • Open

Socio-economic Objectives

Expanding knowledge in the biological sciences

Usage metrics