A new constrained edit distance between quotiented ordered trees |
| |
Authors: | Aïda Ouangraoua Pascal Ferraro |
| |
Institution: | LaBRI - Université de Bordeaux 1, 351 Cours de la Libération, 33405 Talence Cedex, France |
| |
Abstract: | In this paper we propose a dynamic programming algorithm to compare two quotiented ordered trees using a constrained edit distance. An ordered tree is a tree in which the left-to-right order among siblings is significant. A quotiented ordered tree is an ordered tree T with an equivalence relation on vertices and such that, when the equivalence classes are collapsed to super-nodes, the graph so obtained is an ordered tree as well. Based on an algorithm proposed by Zhang and Shasha K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18 (6) (1989) 1245–1262] and introducing new notations, we describe a tree edit distance between quotiented ordered trees preserving equivalence relations on vertices during computation which works in polynomial time. Its application to RNA secondary structures comparison is finally presented. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|