论文标题
三片和四片叶子上的毛毛虫足以重建正常网络
Caterpillars on three and four leaves are sufficient to reconstruct normal networks
论文作者
论文摘要
虽然每个生根的二进制系统发育树都取决于其显示的根三元三联，但这种结果不能适用于任意生根的二元系统发育网络。特别是，存在两个非晶状体二进制时间正常网络，它们显示了相同的植根三元组。此外，没有对正在考虑的根系系统发育网络进行任何结构性限制，也为分别在两个和三片叶子上扎根的双层和TRINETS建立了类似的负面结果。因此，总的来说，从这样的一组小型构建块中拼凑出一个根源的系统发育网络似乎是无法克服的。与这些结果相反，在本文中，我们表明，生根的二进制正常网络由三片和四片叶子上显示的毛毛虫（特定类型的子树）确定。该证明具有建设性，并实现了多项式时间算法，该算法将毛毛虫的集合在由根系的二进制正常网络显示的三叶和四个叶子上，直至同构，直到同构，重建了该网络。
While every rooted binary phylogenetic tree is determined by its set of displayed rooted triples, such a result does not hold for an arbitrary rooted binary phylogenetic network. In particular, there exist two non-isomorphic rooted binary temporal normal networks that display the same set of rooted triples. Moreover, without any structural constraint on the rooted phylogenetic networks under consideration, similarly negative results have also been established for binets and trinets which are rooted subnetworks on two and three leaves, respectively. Hence, in general, piecing together a rooted phylogenetic network from such a set of small building blocks appears insurmountable. In contrast to these results, in this paper, we show that a rooted binary normal network is determined by its sets of displayed caterpillars (particular type of subtrees) on three and four leaves. The proof is constructive and realises a polynomial-time algorithm that takes the sets of caterpillars on three and four leaves displayed by a rooted binary normal network and, up to isomorphism, reconstructs this network.
