title: RASCAL: A Randomized Approach for Coevolutionary Analysis.
abstract: 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.
authors.affiliation: 1 School of Information Technologies, The University of Sydney , Sydney, Australia .|2 School of Physical Sciences, University of Tasmania , Tasmania, Australia .
authors.forename: Benjamin
authors.initials: B
authors.lastname: Drinkwater
authors.affiliation: 1 School of Information Technologies, The University of Sydney , Sydney, Australia .|2 School of Physical Sciences, University of Tasmania , Tasmania, Australia .
authors.forename: Michael A
authors.initials: MA
authors.lastname: Charleston
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D010802:Phylogeny; D017422:Sequence Analysis, DNA / Q000379:methods
keywords: NP-hard; coevolution; phylogeny; randomization