Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jda.2008.05.001 | J. Discrete Algorithms |
Keywords | Field | DocType |
rna secondary structures comparison,equivalence relation,edit distance.,new notation,dynamic programming,edit distance,simple fast algorithm,left-to-right order,ordered labeled trees,quotiented graph,k. zhang,siam journal,equivalence class,editing distance,dynamic programming algorithm,word order,polynomial time,rna secondary structure | Edit distance,Dynamic programming,Discrete mathematics,Range tree,Combinatorics,Equivalence relation,Vertex (geometry),K-ary tree,Equivalence class,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aïda Ouangraoua | 1 | 94 | 15.93 |
| Pascal Ferraro | 2 | 77 | 11.54 |