RASCAL.pdf (573.98 kB)
RASCAL: A randomized approach for coevolutionary analysis
journal contribution
posted on 2023-05-19, 02:48 authored by Drinkwater, B, Michael CharlestonMichael CharlestonA 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.
History
Publication title
Journal of Computational BiologyVolume
23Pagination
218-227ISSN
1066-5277Department/School
School of Natural SciencesPublisher
Mary Ann Liebert Inc PublPlace of publication
2 Madison Avenue, Larchmont, USA, Ny, 10538Rights statement
©2012 Mary Ann Liebert, Inc. publishers. All rights reserved, USA and worldwide.Repository Status
- Open