首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号