Name
Abstract | ||
|---|---|---|
One of the most important problem in computational biology is the tree editing problem which is to determine the edit distance between two rooted labeled trees. It has been shown to have significant applications in both RNA secondary structures and evolutionary trees. Another viewpoint of considering this problem is to find an edit mapping with the minimum cost. By restricting the type of mapping, Zhang [7,8] and Richter [5] independently introduced the constrained edit distance and the structure respecting distance, respectively. They are, in fact, the same concept. In this paper, we define a new measure of the edit distance between two rooted labeled trees, called less-constrained edit distance, by relaxing the restriction of constrained edit mapping. Then we study the algorithmic complexities of computing the less-constrained edit distance between two rooted labeled trees. For unordered labeled trees, we show that this problem is NP-complete and even has no absolute approximation algorithm unless P = NP, which also implies that it is impossible to have a PTAS for the problem. For ordered labeled trees, we give a polynomial-time algorithm to solve the problem. |
Year | Venue | Keywords |
|---|---|---|
2001 | COCOON | tree graph,cladding,rna,plasma arc,tree structure,polynomial time,np complete problem,computational complexity,evolutionary algorithm |
Field | DocType | Volume |
Edit distance,String-to-string correction problem,Discrete mathematics,Combinatorics,Tree (graph theory),Computer science,Wagner–Fischer algorithm,Jaro–Winkler distance,Damerau–Levenshtein distance,Time complexity,Polynomial-time approximation scheme | Conference | 2108 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-42494-6 | 17 |
PageRank | References | Authors |
1.05 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chin Lung Lu | 1 | 423 | 34.59 |
| Zheng-Yao Su | 2 | 17 | 1.05 |
| Chuan Yi Tang | 3 | 704 | 79.25 |