chapter  7
26 Pages

General Pattern Matching in Trees

Combinatorial pattern matching is the search for exact or approximate occurrences of a given pattern within a given text. When it comes to trees in computational biology, both the pattern and the text are trees and the pattern matching problem becomes one of finding the occurrences of a tree within another tree. For instance, scanning an RNA secondary structure for the presence of a known pattern can help in finding conserved RNA motifs, and finding a phylogenetic tree within another phylogenetic tree can help in assessing their similarities and differences. This is the subject of this chapter.