ABSTRACT
Combinatorial pattern matching is the search for exact or approximate occurrences of a given pattern within a given text. When it comes to graphs in computational biology, both the pattern and the text are graphs and the pattern matching problem becomes one of finding the occurrences of a graph within another graph. For instance, scanning a metabolic pathway for the presence of a known pattern can help in finding conserved network motifs, and finding a phylogenetic network within another phylogenetic network 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 graphs
consists in finding simpler patterns, that is, paths and trees within a given graph. For instance, finding paths between two nodes of a graph is useful for computing distances in a graph and also for computing distances between two graphs, and finding the trees contained in a graph is also useful for computing distances between two graphs. This is the subject of this chapter.
