Decomposition algorithms for the tree edit distance problem

被引：19

作者：

Dulucq, Serge ^{[1
]}

Touzet, Helene ^{[2
]}

机构：

[1] Univ Bordeaux 1, LaBRI, UMR CNRS 5800, F-33405 Talence, France

[2] Univ Lille 1, LIFL, UMR CNRS 8022, F-59655 Villeneuve Dascq, France

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2005年 / 3卷 / 2-4期

关键词：

Algorithm; Edit distance; Alignment; Tree; Computational biology;

D O I：

10.1016/j.jda.2004.08.018

中图分类号：

O29 [应用数学];

学科分类号：

070104 [应用数学];

摘要：

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91-102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245-1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies. (C) 2004 Elsevier B. V. All rights reserved.

引用

页码：448 / 471

页数：24

共 14 条

[1]

Chawathe SS, 1999, PROCEEDINGS OF THE TWENTY-FIFTH INTERNATIONAL CONFERENCE ON VERY LARGE DATA BASES, P90

[2]

RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm [J].