Landry Kaari, Teodocio Aivee, Lafond Manuel, Tremblay-Savard Olivier
IEEE/ACM Trans Comput Biol Bioinform. 2023 May-Jun;20(3):1654-1666. doi: 10.1109/TCBB.2022.3162991. Epub 2023 Jun 5.
In phylogenetic networks, picking a cherry consists of removing a leaf that shares a parent with another leaf, or removing a reticulate edge whose endpoints are parents of leaves. Cherry-picking operations were recently shown to have several structural and algorithmic applications in the study of networks, for instance in determining their reconstructibility or in solving the network hybridization and network containment problems. In particular, some networks within certain classes are isomorphic if they can be reduced to a single node by the same sequence of cherry-picking operations. Therefore, cherry-picking sequences contain information on the level of similarity between two networks. In this paper, we expand on this idea by devising four novel distances on networks based on cherry picking and their reverse operation. We provide bounds between these distances and show that three of them are equal despite their different formulations. We also show that computing these three equivalent distances is NP-hard, even when restricted to comparing a tree and a network. On the positive side, we show that they can be computed in quadratic time on two trees, providing a new comparative measure for phylogenetic trees that can be computed efficiently.
在系统发育网络中，挑选一个樱桃包含移除与另一叶子共享一个父节点的叶子，或者移除其端点是叶子父节点的网状边。最近研究表明，樱桃挑选操作在网络研究中有若干结构和算法应用，例如在确定网络的可重构性或解决网络杂交和网络包含问题方面。特别地，如果某些类别的网络可以通过相同的樱桃挑选操作序列简化为单个节点，那么这些网络是同构的。因此，樱桃挑选序列包含两个网络之间相似程度的信息。在本文中，我们基于樱桃挑选及其反向操作，设计了四种新颖的网络距离，从而拓展了这一思想。我们给出了这些距离之间的界限，并表明其中三个距离尽管表述不同但相等。我们还表明，即使限制在比较一棵树和一个网络时，计算这三个相等的距离也是NP难的。从积极的方面来看，我们表明它们可以在两棵树上以二次时间计算出来，为系统发育树提供了一种可以高效计算的新的比较度量。
