A New Measure of Edit Distance between Labeled Trees
A New Measure of Edit Distance between Labeled Trees
复制标题
标记树之间编辑距离的新测量
DOI：
10.1007/3-540-44679-6_37
复制
发表时间：
2001
影响因子：
--
通讯作者：
C. Tang
中科院分区：
文献类型：
--
作者：
C. Lu;Z. Su;C. Tang
计算生物学中最重要的问题之一是树的编辑问题，即确定两个扎根的树木之间的编辑距离。已显示它在RNA二级结构和进化树中都有重要的应用。考虑此问题的另一个观点是找到具有最低成本的编辑映射。通过限制映射的类型，张[7,8]和里希特[5]分别独立地引入了约束的编辑距离和尊重距离的结构。实际上，它们是相同的概念。在本文中，我们通过放松约束编辑映射的限制，定义了两个扎根的树木之间的编辑距离的新度量，称为较小的编辑距离。然后，我们研究计算两个扎根的树木之间不受约束的编辑距离的算法复杂性。对于未排序的标记树，我们表明此问题是NP完整的，甚至没有绝对近似算法，除非p = np，否则这也意味着无法解决该问题的PTA。对于有序标记的树，我们给出了一个多项式时间算法来解决该问题。
One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem.