Name
Abstract | ||
|---|---|---|
In this paper we propose a dynamic programming algorithm to evaluate local similarity between ordered quotiented trees using a constrained edit scoring scheme. A quotiented tree is a tree defined with an additional equivalent relation on vertices and such that the quotient graph is also a tree. The core of the method relies on two adaptations of an algorithm proposed by Zhang et al. [K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems (1989) 1245-1262] for comparing ordered rooted trees. After some preliminary definitions and the description of this tree edit algorithm, we propose extensions to globally and locally compare two quotiented trees. This last method allows to find the region in each tree with the highest similarity. Algorithms are currently being used in genomic analysis to evaluate variability between RNA secondary structures. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jda.2006.03.010 | J. Discrete Algorithms |
Keywords | Field | DocType |
local similarity,rna secondary structure,highest similarity,dynamic programming,simple fast algorithm,local edition,ordered labeled trees,quotiented graph,last method,k. zhang,editing distance,quotiented tree,additional equivalent relation,dynamic programming algorithm,equivalence relation,edit distance | Dynamic programming,Discrete mathematics,Combinatorics,Range tree,Vertex (geometry),K-ary tree,Link/cut tree,Mathematics,Zhàng,Quotient graph | Journal |
Volume | Issue | ISSN |
5 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
10 | 0.64 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aïda Ouangraoua | 1 | 94 | 15.93 |
| Pascal Ferraro | 2 | 77 | 11.54 |
| Laurent Tichit | 3 | 32 | 2.16 |
| serge dulucq | 4 | 103 | 11.08 |