Algorithms for Finding a Most Similar Subforest
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 forest edit 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. Algorithms for the most similar subforest problem restricted to subforests which are either rooted sub-trees or simple substructures exist in the literature; in this article, we show how to solve the most similar subforest problem for two other types of subforests: sibling substructures and closed subforests.
forest edit distance simple substructure sibling substructure closed subforest approximate pattern matching dynamic programming