Department of Computer Science and Engineering, UC San Diego, 9500 Gilman Dr, La Jolla, 92093, USA.
Department of Electrical and Computer Engineering, UC San Diego, 9500 Gilman Dr, La Jolla, 92093, USA.
BMC Genomics. 2020 Apr 16;21(Suppl 2):218. doi: 10.1186/s12864-020-6607-z.
To account for genome-wide discordance among gene trees, several widely-used methods seek to find a species tree with the minimum distance to input gene trees. To efficiently explore the large space of species trees, some of these methods, including ASTRAL, use dynamic programming (DP). The DP paradigm can restrict the search space, and thus, ASTRAL and similar methods use heuristic methods to define a restricted search space. However, arbitrary constraints provided by the user on the output tree cannot be trivially incorporated into such restrictions. The ability to infer trees that honor user-defined constraints is needed for many phylogenetic analyses, but no solution currently exists for constraining the output of ASTRAL.
We introduce methods that enable the ASTRAL dynamic programming to infer constrained trees in an effective and scalable manner. To do so, we adopt a recently developed tree completion algorithm and extend it to allow multifurcating input and output trees. In simulation studies, we show that the approach for honoring constraints is both effective and fast. On real data, we show that constrained searches can help interrogate branches not recovered in the optimal ASTRAL tree to reveal support for alternative hypotheses.
The new algorithm is added ASTRAL to all user-provided constraints on the species tree.
为了解决基因树之间全基因组不一致的问题，几种广泛使用的方法试图找到与输入基因树距离最小的物种树。为了有效地探索物种树的广阔空间，其中一些方法，包括 ASTRAL，使用动态规划（DP）。DP 范式可以限制搜索空间，因此，ASTRAL 和类似的方法使用启发式方法来定义受限的搜索空间。然而，用户对输出树的任意约束不能轻易地纳入到这些限制中。对于许多系统发育分析，需要能够推断出符合用户定义约束的树，但目前还没有方法可以限制 ASTRAL 的输出。
我们引入了一些方法，使 ASTRAL 的动态规划能够有效地、可扩展地推断出受约束的树。为此，我们采用了最近开发的树完成算法，并将其扩展为允许输入和输出树具有多叉分枝。在模拟研究中，我们表明，这种方法对于尊重约束是有效的和快速的。在真实数据上，我们表明，受约束的搜索可以帮助检查在最优 ASTRAL 树中未恢复的分支，以揭示对替代假设的支持。
新算法将所有用户提供的物种树约束都添加到了 ASTRAL 中。
