Fast Coalescent-Based Computation of Local Branch Support from Quartet Frequencies.
Sayyari E, Mirarab S. · 2016
Read Fast Coalescent-Based Computation of Local Branch Support from Quartet Frequencies. by Sayyari E, Mirarab S. (2016) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/europmc-pmc4915361.txt.
Introduction
Erfan Sayyari and Siavash Mirarab offered a fast way in 2016 to compute local branch support for species trees from quartet frequencies. Rebuilding species trees is tangled by incomplete lineage sorting, where gene trees clash. Trust in each branch needs a support score, and older routes lean on slow repeated sampling. Their algorithm counts how gene trees vote on four-species splits around each branch.
From those counts it derives a local posterior probability that the branch belongs in the species tree, plus branch length in coalescent units. On simulated and real data the score showed very high precision and better recall than multi-locus bootstrapping. Species tree builders gain a swift trust gauge for every branch.
Catalog record
| CREATOR | Sayyari E, Mirarab S. |
|---|---|
| YEAR | 2016 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| LICENSE | CC BY 4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Coalescent-Based Computation of Local Branch Support from Quartet Frequencies By Erfan Sayyari, Siavash Mirarab Published in: Molecular Biology and Evolution DOI: 10.1093/molbev/msw079 ABSTRACT Abstract Species tree reconstruction is complicated by effects of incomplete lineage sorting, commonly modeled by the multi-species coalescent model (MSC). While there has been substantial progress in developing methods that estimate a species tree given a collection of gene trees, less attention has been paid to fast and accurate methods of quantifying support. In this article, we propose a fast algorithm to compute quartet-based support for each branch of a given species tree with regard to a given set of gene trees. We then show how the quartet support can be used in the context of the MSC to compute (1) the local posterior probability (PP) that the branch is in the species tree and (2) the length of the branch in coalescent units. We evaluate the precision and recall of the local PP on a wide set of simulated and biological datasets, and show that it has very high precision and improved recall compared with multi-locus bootstrapping. The estimated branch lengths are highly accurate when gene tree estimation error is low, but are underestimated when gene tree estimation error increases. Computation of both the branch length and local PP is implemented as new features in ASTRAL. Keywords: Incomplete lineage sorting, multi-species coalescent, quartet-based methods, ASTRAL, posterior probability, local support, branch length estimation. INTRODUCTION The multi-species coalescent model (MSC) of Rannala and Yang (2003) has emerged as the standard method used for reconstructing species trees in the presence of gene tree discordance due to incomplete lineage sorting (ILS) (Maddison 1997; Degnan and Rosenberg 2006). Many methods have been developed to estimate species trees under the MSC (e.g., Heled and Drummond 2010; Bryant et al. 2012; Chifman and Kubatko 2014; Mirarab, Bayzid, Boussau, et al. 2014). The most scalable family of MSC-based methods are based on a two-step process where gene trees are first estimated independently for each gene and are then combined to build the species tree using a summary method. Many of the summary methods are statistically consistent and thus converge in probability to the true species tree as the number of input error-free gene trees increases; examples of consistent methods include ASTRAL (Mirarab, Reaz, Bayzid, et al. 2014; Mirarab and Warnow 2015), BUCKy-population (Larget et al. 2010), GLASS (Mossel and Roch 2010), MP-EST (Liu et al. 2010), NJst and ASTRID (Liu and Yu 2011; Vachaspati and Warnow 2015), and STAR (Liu et al. 2009). While some methods (e.g., MP-EST) can estimate branch lengths in coalescent units, others only infer the topology. The traditional concatenation approach (where all genes are put together in a supermatrix) can produce high support for incorrect branches (Kubatko and Degnan 2007; Roch and Steel 2014), and the main goal of statistically consistent summary methods is to address this shortcoming. However, despite the progress in developing methods for species tree reconstruction, little attention has been paid to methods of calculating support. Bayesian methods (e.g., Liu 2008; Heled and Drummond 2010) readily provide support but remain computationally challenging. Calculating support through bootstrapping (Felsenstein 1985), while still computationally expensive, is not prohibitively slow and is easily parallelizable. Seo et al. (2005) proposed a multi-locus bootstrapping (MLBS) procedure that produces bootstrap replicates by first resampling genes and then sites within those sampled genes. Seo (2008) later studied the accuracy of the MLBS approach in the context of distance-based tree reconstruction for 4-taxon trees and explored other strategies where only genes or only sites were resampled. These earlier works did not consider ILS as the cause of discordance; nor did they use summary methods. Nevertheless, the community has adopted MLBS as a standard way of estimating support using ILS-based summary methods; most biological studies using summary methods rely on site-only or site/gene MLBS (e.g., Song et al. 2012; Jarvis et al. 2014; Wickett et al. 2014; Prum et al. 2015). Recently, Mirarab, Bayzid, Warnow (2014) studied the reliability of MLBS support values as a measure of accuracy in simulation studies, and documented both under-estimation and over-estimation of support (for low- and high-support branches, respectively) using MP-EST (Liu et al. 2010) and supertree methods such as MRP (Ragan 1992) and MRL (Nguyen et al. 2012). Mirarab, Bayzid, Warnow (2014) also observed better species tree accuracy when a summary method was run directly on ML gene trees, compared with running the summary method on bootstrapped gene trees first and then taking a consensus. This observation led to the conjecture that MLBS might give biased estimates of the support. Furthermore, Bayzid et al. (2015) found in simulation studies that false positive branches can sometimes have high MLBS support and that many true branches tend to have low support. Obtaining low support for true branches should not be a cause of concern if the lack of support is caused by insufficient data; however, when low support is caused by underestimation, we need better methods of quantifying support. In this article, we show that using properties of the MSC on four taxa (quartets), we can derive support values that are more precise and more powerful than MLBS, and are much faster to compute. Under the MSC, quartet trees do not have anomaly zones (Allman et al. 2011; Degnan 2013), meaning that the most probable gene tree is identical to the species tree for any quartet. Exploiting this property, some summary methods break up gene trees into quartet trees. For example, ASTRAL (Mirarab and Warnow 2015), a summary method used in many recent studies (e.g., Wickett et al. 2014; Andrade et al. 2015; Giarla and Esselstyn 2015; Grover et al. 2015; Hosner et al. 2015; Laumer et al. 2015; Prum et al. 2015; Streicher et al. 2015), finds the species tree that shares the maximum number of induced quartet trees with gene trees. We introduce a new method for computing support for species tree branches with regard to a set of unrooted gene trees by calculating Bayesian posterior probabilities. Our support values, which we call local posterior probabilities, are computed based on gene tree quartet frequencies. For each internal branch of the given species tree, we assume that the four sides of the branch (fig. 1) are correct, and therefore three topologies are possible around that branch. We introduce a fast algorithm to compute a quartet support for each of those three alternatives in Θ(nl) time (where l is the number of species and n is the number of genes). We then use the quartet support for each alternative topology to derive the posterior probability (PP) that it is the correct species topology. Besides producing measures of support, quartet frequencies can be used to derive estimates of internal branch lengths in coalescent units. [Figure: Quadripartitions and tripartitions. (A) An internal branch (black, in the middle) divides the set of leaves into a quadripartition. A quartet of leaves {1,2,3,4} induces a quartet tree (in red) with two internal nodes that map to two nodes in the larger tree (here, u and v). (B) An internal node, here u, divides leaves into a tripartition; a selection of two leaves from one side and one from each remaining side gives a quartet mapped to