ABSTRACT
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 will be the subject of the next chapter. A related pattern matching problem that arises in the analysis of trees
consists in finding simpler patterns, that is, paths within a given tree. For instance, finding the path between two nodes of a tree is useful for computing distances in a tree and also for computing distances between two trees. This is the subject of this chapter.
