A relation between edit distance for ordered trees and edit distance for Euler strings |
| |
Authors: | Tatsuya Akutsu |
| |
Affiliation: | Bioinformatics Center, Institute for Chemical Research, Kyoto University, Kyoto 611-0011, Japan |
| |
Abstract: | We consider a relationship between the unit cost edit distance for two rooted ordered trees and the unit cost edit distance for the corresponding Euler strings. We show that the edit distance between trees is at least half of the edit distance between the Euler strings and is at most 2h+1 times the edit distance between the Euler strings, where h is the minimum height of two trees. The result can be extended for more general cost functions. |
| |
Keywords: | Algorithms Edit distance Ordered trees Alignment Euler string |
本文献已被 ScienceDirect 等数据库收录! |