Department of Mathematics and Centre for Data Science and Machine Learning, National University of Singapore, Singapore 119076, Singapore;
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada.
Genome Res. 2023 Jul;33(7):1053-1060. doi: 10.1101/gr.277669.123. Epub 2023 May 22.
The reconstruction of phylogenetic networks is an important but challenging problem in phylogenetics and genome evolution, as the space of phylogenetic networks is vast and cannot be sampled well. One approach to the problem is to solve the minimum phylogenetic network problem, in which phylogenetic trees are first inferred, and then the smallest phylogenetic network that displays all the trees is computed. The approach takes advantage of the fact that the theory of phylogenetic trees is mature, and there are excellent tools available for inferring phylogenetic trees from a large number of biomolecular sequences. A tree-child network is a phylogenetic network satisfying the condition that every nonleaf node has at least one child that is of indegree one. Here, we develop a new method that infers the minimum tree-child network by aligning lineage taxon strings in the phylogenetic trees. This algorithmic innovation enables us to get around the limitations of the existing programs for phylogenetic network inference. Our new program, named ALTS, is fast enough to infer a tree-child network with a large number of reticulations for a set of up to 50 phylogenetic trees with 50 taxa that have only trivial common clusters in about a quarter of an hour on average.
系统发生网络重建是系统发生学和基因组进化中的一个重要但具有挑战性的问题，因为系统发生网络的空间非常大，无法很好地进行采样。解决该问题的一种方法是解决最小系统发生网络问题，首先推断出系统发生树，然后计算出显示所有树的最小系统发生网络。该方法利用了系统发生树理论已经成熟这一事实，并且有优秀的工具可用于从大量生物分子序列中推断系统发生树。树-子网络是一种满足每个非叶节点至少有一个入度为一的子节点的系统发生网络。在这里，我们开发了一种新方法，通过对齐系统发生树中的谱系分类单元字符串来推断最小树-子网络。这种算法创新使我们能够克服现有的系统发生网络推断程序的限制。我们的新程序名为 ALTS，速度足够快，可以在大约四分之一小时的时间内平均推断出一组多达 50 棵具有 50 个分类单元的系统发生树的树-子网络，其中只有少量的常见聚类。
