RASCAL: A randomized approach for coevolutionary analysis
journal contributionposted 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 titleJournal of Computational Biology
Department/SchoolSchool of Natural Sciences
PublisherMary Ann Liebert Inc Publ
Place of publication2 Madison Avenue, Larchmont, USA, Ny, 10538
Rights statement©2012 Mary Ann Liebert, Inc. publishers. All rights reserved, USA and worldwide.