Semple Charles, Toft Gerry
School of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand.
J Math Biol. 2021 Aug 21;83(3):28. doi: 10.1007/s00285-021-01654-7.
Rooted triples, rooted binary phylogenetic trees on three leaves, are sufficient to encode rooted binary phylogenetic trees. That is, if [Formula: see text] and [Formula: see text] are rooted binary phylogenetic X-trees that infer the same set of rooted triples, then [Formula: see text] and [Formula: see text] are isomorphic. However, in general, this sufficiency does not extend to rooted binary phylogenetic networks. In this paper, we show that trinets, phylogenetic network analogues of rooted triples, are sufficient to encode rooted binary orchard networks. Rooted binary orchard networks naturally generalise rooted binary tree-child networks. Moreover, we present a polynomial-time algorithm for building a rooted binary orchard network from its set of trinets. As a consequence, this algorithm affirmatively answers a previously-posed question of whether there is a polynomial-time algorithm for building a rooted binary tree-child network from the set of trinets it infers.
有根三元组，即具有三个叶节点的有根二叉系统发育树，足以对有根二叉系统发育树进行编码。也就是说，如果[公式：见原文]和[公式：见原文]是推断出相同有根三元组集合的有根二叉X-树，那么[公式：见原文]和[公式：见原文]是同构的。然而，一般来说，这种充分性并不适用于有根二叉系统发育网络。在本文中，我们表明三网（有根三元组的系统发育网络类似物）足以对有根二叉果园网络进行编码。有根二叉果园网络自然地推广了有根二叉树子网络。此外，我们提出了一种多项式时间算法，用于从其三网集合构建有根二叉果园网络。因此，该算法肯定地回答了一个先前提出的问题，即是否存在一种多项式时间算法，用于从其推断出的三网集合构建有根二叉树子网络。
