期刊
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
卷 20, 期 3, 页码 1654-1666出版社
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2022.3162991
关键词
Phylogeny; Vegetation; Time measurement; Licenses; Directed graphs; Bioinformatics; Viruses (medical); Network problems; graph theory; discrete mathematics; mathematics of computing; biology and genetics; life and medical sciences; computer applications
In phylogenetic networks, cherry-picking operations have been shown to have structural and algorithmic applications. They can be used to determine reconstructibility, solve network hybridization and network containment problems, and measure similarity between networks. This paper introduces four novel distances on networks based on cherry picking and their reverse operation, providing new comparative measures for phylogenetic trees. While computing these distances is NP-hard, they can be efficiently computed in quadratic time on two trees.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据