×

zbMATH — the first resource for mathematics

Decomposition algorithms for the tree edit distance problem. (English) Zbl 1129.68099
Summary: We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Algorithms - ESA ’98. 6th annual European symposium, Venice, Italy, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1461, 91–102 (1998; Zbl 0932.68066); K. Zhang, D. Shasha, SIAM J. Comput. 18, No. 6, 1245–1262 (1989; Zbl 0692.68047)]. 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.

MSC:
68W40 Analysis of algorithms
92D20 Protein sequences, DNA sequences
05C05 Trees
05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chawathe, S., Comparing hierarchical data in external memory, (), 90-101
[2] Dulucq, S.; Tichit, L., RNA secondary structure comparison: exact analysis of the zhang – shasha tree edit algorithm, Theoret. comput. sci., 306, 1-3, 471-484, (2003) · Zbl 1060.68027
[3] Harel, D.; Tarjan, R.E., Fats algorithms for finding nearest common ancestors, SIAM J. comput., 13, 2, 338-355, (1984) · Zbl 0535.68022
[4] Jiang, T.; Wang, L.; Zhang, K., Alignment of trees—an alternative to tree edit, Theor. comput. sci., 143, (1995) · Zbl 0873.68150
[5] Klein, P., Computing the edit-distance between unrooted ordered trees, (), 91-102 · Zbl 0932.68066
[6] Needleman, S.B.; Wunsh, C.D., A general method applicable to the search for similarities in the amino acid sequence of two proteins, J. molecular biol., 48, 443-453, (1970)
[7] Selkow, S.M., The tree-to-tree editing problem, Inform. process. lett., 6, 184-186, (1977) · Zbl 0391.68022
[8] Shapiro, B.; Zhang, K., Comparing multiple RNA secondary structures using tree comparisons, Comput. appl. biosci., 4, 3, 387-393, (1988)
[9] Tai, K.C., The tre-to-tree correction problem, J. ACM, 26, 422-433, (1979) · Zbl 0409.68040
[10] Touzet, H., Tree edit distance with gaps, Inform. process. lett., 85, 3, 123-129, (2003) · Zbl 1011.68851
[11] Valiente, G., Algorithms on trees and graphs, (2002), Springer-Verlag · Zbl 1007.05001
[12] Wagner, R.A.; Fischer, M.J., The string-to-string correction problem, J. ACM, 21, 1, 168-173, (1974) · Zbl 0278.68032
[13] Zhang, K.; Shasha, D., Simple fast algorithms for the editing distance between trees and related problems, SIAM J. comput., 18, 6, 1245-1262, (1989) · Zbl 0692.68047
[14] Zhang, K., Algorithms for the constrained editing problem between ordered labeled trees and related problems, Pattern recognition, 28, 463-474, (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.