Just as a phylogeny encodes the evolutionary relationships among a group of organisms, a cophylogeny represents the coevolutionary relationships among symbiotic partners. Both are primarily reconstructed using computational analysis of biomolecular sequence data. The most widely used cophylogenetic reconstruction methods utilize an important simplifying assumption: species phylogenies for each set of coevolved taxa are required as input and assumed to be correct. Many studies have shown that this assumption is rarely - if ever - satisfied, and the consequences for cophylogenetic studies are poorly understood. To address this gap, we conduct a comprehensive performance study that quantifies the relationship between species tree estimation error and downstream cophylogenetic estimation accuracy. We study the performance of state-of-the-art methods for cophylogenetic reconstruction using in silico model-based simulations. Our investigation also assessed cophylogenetic reproducibility using genomic sequence data from two important models of symbiosis: soil-associated fungi and their endosymbiotic bacteria, and bobtail squid and their bioluminescent bacterial symbionts. Our findings conclusively demonstrate the major impact that upstream phylogenetic estimation error has on downstream cophylogenetic reconstruction. Relative to other experimental factors such as cophylogenetic estimation method choice and coevolutionary event costs, phylogenetic estimation error ranked highest in importance based on a random forest-based variable importance assessment. We conclude with practical guidance and future research directions. Among the many considerations needed for accurate cophylogenetic reconstruction - choice of computational method, method settings, sampling design, and others - just as much attention must be paid to careful species phylogeny estimation using modern best practices.

Cophylogenies represent coevolutionary histories of two or more sets of coevolved taxa, and are used to study coevolution and other fundamental evolutionary processes. As with traditional phylogenies, cophylogenies are primarily reconstructed using computational analysis of DNA and other biomolecular sequence data. An essential question concerns the reliability of reconstructed phylogenies and cophylogenies.Statistical resampling offers a principled approach to evaluate statistical confidence for these tasks. We therefore apply bootstrap resampling – one of the most widely used non-parametric resampling techniques – to place confidence intervals on a reconstructed cophylogeny, which is the first such method to our knowledge. We validate the performance of the resulting reliability estimates in a simulation study as well as an empirical case study of bobtail squid and its bioluminescent endosymbionts. The utility of statistical resampling to assess cophylogenetic reconstruction reliability in an automated and data-driven manner points the way forward – both for future methods development and wider adoption in studies of symbioses and other forms of coevolution.

MOTIVATION: The standard bootstrap method is used throughout science and engineering to perform general-purpose non-parametric resampling and re-estimation. Among the most widely cited and widely used such applications is the phylogenetic bootstrap method, which Felsenstein proposed in 1985 as a means to place statistical confidence intervals on an estimated phylogeny (or estimate 'phylogenetic support'). A key simplifying assumption of the bootstrap method is that input data are independent and identically distributed (i.i.d.). However, the i.i.d. assumption is an over-simplification for biomolecular sequence analysis, as Felsenstein noted. RESULTS: In this study, we introduce a new sequence-aware non-parametric resampling technique, which we refer to as RAWR ('RAndom Walk Resampling'). RAWR consists of random walks that synthesize and extend the standard bootstrap method and the 'mirrored inputs' idea of Landan and Graur. We apply RAWR to the task of phylogenetic support estimation. RAWR's performance is compared to the state-of-the-art using synthetic and empirical data that span a range of dataset sizes and evolutionary divergence. We show that RAWR support estimates offer comparable or typically superior type I and type II error compared to phylogenetic bootstrap support. We also conduct a re-analysis of large-scale genomic sequence data from a recent study of Darwin's finches. Our findings clarify phylogenetic uncertainty in a charismatic clade that serves as an important model for complex adaptive evolution. AVAILABILITY AND IMPLEMENTATION: Data and software are publicly available under open-source software and open data licenses at: https://gitlab.msu.edu/liulab/RAWR-study-datasets-and-scripts.