ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees.

Zhang C, Rabiee M, Sayyari E, Mirarab S. · 2018

Read ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees. by Zhang C, Rabiee M, Sayyari E, Mirarab S. (2018) 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-pmc5998893.txt.

Introduction

Zhang, Rabiee, Sayyari, and Mirarab introduce ASTRAL-III, a faster method for rebuilding species trees from gene trees. Their paper appeared in BMC Bioinformatics. Gene histories often disagree across the genome. Species trees must account for that discordance. ASTRAL searches for the tree sharing the most quartets with the gene trees. The new version guarantees polynomial running time. It also handles unresolved gene trees more efficiently. Several search shortcuts skip parts that cannot hold the best tree.

Simulations showed that cutting very weak branches improves accuracy, they report. Over-aggressive filtering hurt instead. On a bird data set of 14,000 genes the gains were large. The method scales to 10,000 species.

Catalog record

CREATORZhang C, Rabiee M, Sayyari E, Mirarab S.
YEAR2018
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC5998893

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees By Chao Zhang, Maryam Rabiee, Erfan Sayyari, Siavash Mirarab Published in: BMC Bioinformatics DOI: 10.1186/s12859-018-2129-y ABSTRACT Background Evolutionary histories can be discordant across the genome, and such discordances need to be considered in reconstructing the species phylogeny. ASTRAL is one of the leading methods for inferring species trees from gene trees while accounting for gene tree discordance. ASTRAL uses dynamic programming to search for the tree that shares the maximum number of quartet topologies with input gene trees, restricting itself to a predefined set of bipartitions. Results We introduce ASTRAL-III, which substantially improves the running time of ASTRAL-II and guarantees polynomial running time as a function of both the number of species (n) and the number of genes (k). ASTRAL-III limits the bipartition constraint set (X) to grow at most linearly with n and k. Moreover, it handles polytomies more efficiently than ASTRAL-II, exploits similarities between gene trees better, and uses several techniques to avoid searching parts of the search space that are mathematically guaranteed not to include the optimal tree. The asymptotic running time of ASTRAL-III in the presence of polytomies is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O\left ((nk)^{1.726} D \right)$\end{document}O(nk)1.726D where D=O(nk) is the sum of degrees of all unique nodes in input trees. The running time improvements enable us to test whether contracting low support branches in gene trees improves the accuracy by reducing noise. In extensive simulations, we show that removing branches with very low support (e.g., below 10%) improves accuracy while overly aggressive filtering is harmful. We observe on a biological avian phylogenomic dataset of 14K genes that contracting low support branches greatly improve results. Conclusions ASTRAL-III is a faster version of the ASTRAL method for phylogenetic reconstruction and can scale up to 10,000 species. With ASTRAL-III, low support branches can be removed, resulting in improved accuracy. Electronic supplementary material The online version of this article (10.1186/s12859-018-2129-y) contains supplementary material, which is available to authorized users. BACKGROUND The potential for genome-wide discordance of evolutionary histories [1, 2] has motivated the development of several approaches for species phylogeny reconstruction. Reconstructing a collection of gene trees, each inferred from a different part of the genome, and then summarizing them to get a species tree is one such approach and is used by many phylogenomic projects (e.g., [3–7]) (while “gene trees” need not be inferred from functional genes, following the conventions of the field, we will refer to them as such). This two-step approach stands in contrast to concatenation [8], where all the data are combined and analyzed in a single analysis. The two-step approach aims to account for discordances between gene trees and the species tree (but its effectiveness is debated [9–12]) and is more computationally efficient than statistical co-estimation of gene trees and the species tree [13]. Incomplete lineage sorting (ILS) is a ubiquitous [14] cause of discordance. ILS is typically modeled by the multi-species coalescent model (MSCM) [15, 16], where branches of the species tree represent populations, and lineages are allowed to coalesce inside each branch; lineages that fail to coalesce at the root of each branch are moved to the parent branch. Many “summary” methods have been developed to infer a species tree from a collection of input trees. Examples include MP-EST [17], NJst [18], ASTRID [19], DISTIQUE [20], ASTRAL [21, 22] and STAR [23], which only use gene tree topologies, and GLASS [24] and STEAC [23], which also use branch lengths. These methods are all proved statistically consistent under the MSCM, given error-free input gene trees; when input trees are inferred from sequence data, statistical consistency is not guaranteed [25]. Most methods take rooted gene trees as input, but some methods (e.g., ASTRAL, NJst/ASTRID and DISTIQUE) use unrooted input trees. ASTRAL-II [22] is currently one of the commonly used summary methods. In this paper, we introduce an improved version of ASTRAL called ASTRAL-III. As we will show, compared to ASTRAL-II, the new version has better running time without sacrificing accuracy. The improvements in the running time are both theoretical (reducing the asymptotic running time so that it is guaranteed to grow polynomially with the dataset size) and empirical. METHODS Notations and definitions Let the set of n species be called L and let G be the set of k input gene trees on L. Let [d] represent the set {1,2…,d}. We use Q(t) to denote the set of quartet trees induced by a tree t. Any subset of L is called a cluster. We define a partition as a set of clusters that are pairwise mutually exclusive; note that we abuse the term “partition” here because the union of all clusters in a partition need not give the complete set. Each node in an unrooted tree defines a partition. A bipartition (tripartition) is a partition with cardinality two (three); a partition with cardinality at least four corresponds to a multifurcation (also referred to as a polytomy). Let X (the constraint bipartition set) be a set of clusters such that for each A∈X, we also have L−A∈X. We use Y to represent the set of all tripartitions that can be build from X: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\begin{aligned} Y=\{(A',A-A',L-A) : A' \subset A, A \in X, A' \in X, A-A' \in X\}. \end{aligned} $$ \end{document}Y={(A′,A−A′,L−A):A′⊂A,A∈X,A′∈X,A−A′∈X}. We use E to denote the set of all unique partitions and their frequency in G. Thus, 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$ E=\left\{\left(M, \sum_{g\in G}|N(g) \cap \{M\}|\right) : M\in N(g), g\in G\right\} $$ \end{document}E=M,∑g∈G|N(g)∩{M}|:M∈N(g),g∈G where N(g) is the set of all partitions representing all internal nodes in the tree g. We also define D as the sum of the cardinalities of unique partitions in gene trees: 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$ D=\sum_{(M,c)\in E} |M|. $$ \end{document}D=∑(M,c)∈E|M|. ASTRAL (old versions) The problem addressed by ASTRAL is to find the tree that shares the maximum number of induced quartet topologies with the collection of input gene trees: Problem statement: Given a set G of input gene trees, find the species tree t that maximizes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sum _{g \in G} |Q(g)\cap Q(t)|$\end{document}∑g∈G|Q(g)∩Q(t)|. Lafond and Scornavacca recently proved this problem is NP-hard [26]. ASTRAL-I and ASTRAL-II algorithms ASTRAL solves a constrained version of the problem where a set of clusters X restricts bipartitions that the output species tree may include (recall ∀A∈X:L−A∈X). Note that setting X to the powerset solves the unconstrained problem. Based on the fact that an unrooted quartet species tree always matches the most likely unrooted quartet gene tree [27], ASTRAL is proved statistically consistent [21]. ASTRAL uses dynamic programming to solve the problem using the recursive relation: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $${{} \begin{aligned} V(A) &= \left\{\begin{array}{lc} 0 & |A|=1\\ \max_{A'\subset A, (A'|A-A'|L-A)\in Y} V(A,A') & |A|>1 \end{array}\right.\\ V(A,A') &= V(A') + V(A-A') + w(A'|A-A'|L-A) \end{aligned}} $$ \end{document}V(A)=0|A|=1maxA′⊂A,(A′|A−A′|L−A)∈YV(A,A′)|A|>1V(A,A′)=V(A′)+V(A−A′)+w(A′|A−A′|L−A) where the function w(T) scores each tripartition T=(A|B|C) against each node in each input gene tree. Let partition \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$M=\left (M_{1}|M_{2}|...|M_{d}\right)$\end{document}M=M1|M2|...|Md represent an internal node of degree

Read the complete text