chapter  10
28 Pages

General Pattern Matching in Graphs

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 is the subject of this chapter.