Algorithms for finding a most similar subforest

Jesper Andreas Jansson, Zeshan Peng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 17th Annual Symposium, CPM 2006, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540354557, 9783540354550
Publication statusPublished - 1 Jan 2006
Externally publishedYes
Event17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006 - Barcelona, Spain
Duration: 5 Jul 20067 Jul 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4009 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th Annual Symposium on Combinatorial Pattern Matching, CPM 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Algorithms for finding a most similar subforest'. Together they form a unique fingerprint.

Cite this