Abstract
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.
Supported partly by the National Science Council of the Republic of China under grant NSC89-2213-E-321-004.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and the hardness of approximation problems, Journal of the Association for Computing Machinery, 45 (1998) 501–555.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamelai, and M. Protasi, Complexity and Approximation—Combinatorial Optimization Problems and Their Approximability Properties, Springer Verlag, Berlin, 1999.
M.R. Garey and D.S. Johnson, Computers and Intractability—A Guide to the Theory of NP-Completeness, San Francisco, Freeman, 1979.
V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, 37 (1991) 27–35.
T. Richter, A newmeasure of the distance between ordered trees and its applications, Technical Report 85166-CS, Department of Computer Science, University of Bonn, 1997.
E. Tanaka and K. Tanaka, The tree-to-tree editing problem, International Journal of Pattern Recognition and Artificial Intelligence, 2 (1988) 221–240.
K. Zhang, Algorithms for the constrained editing distance between ordered labeled trees and related problems, Pattern Recognition, 28 (1995) 463–474.
K. Zhang, A constrained edit distance between unordered labeled trees, Algorithmica, 15 (1996) 205–222.
K. Zhang and T. Jiang, Some MAX SNP-hard results concerning unordered labeled trees, Information Processing Letters, 49 (1994) 249–254.
K. Zhang and D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, 18 (1989) 1245–1262.
K. Zhang, R. Statman, and D. Shasha, On the editing distance between unordered labeled trees, Information Processing Letters, 42 (1992) 133–139.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lu, C.L., Su, ZY., Tang, C.Y. (2001). A New Measure of Edit Distance between Labeled Trees. In: Wang, J. (eds) Computing and Combinatorics. COCOON 2001. Lecture Notes in Computer Science, vol 2108. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44679-6_37
Download citation
DOI: https://doi.org/10.1007/3-540-44679-6_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42494-9
Online ISBN: 978-3-540-44679-8
eBook Packages: Springer Book Archive