Given an ordered labeled forest F ("the target forest") and an ordered labeled forest G ("the pattern forest"), the most similar subforest problem is to find a subforest F′ of F such that the distance between F′ and G is minimum over all possible F'. This problem generalizes several well-studied problems which have important applications in locating patterns in hierarchical structures such as RNA molecules' secondary structures and XML documents. In this paper, we present efficient algorithms for the most similar subforest problem with forest edit distance for three types of subforests: simple substructures, sibling substructures, and closed subforests.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006|
|Period||5/07/06 → 7/07/06|
- Theoretical Computer Science
- Computer Science(all)