Networks

The study of protein interactions from the networks point of view has yielded new insights into systems biology [Bar03, MA03, RSM+02, WS98]. In particular, “net-work motifs ” become apparent as a useful and systematic tool for describing and exploring networks [BP06, MKFV06, MSOI+02, SOMMA02, SV06]. Finding mo-tifs has involved either exact counting (e.g. [MSOI+02]) or subgraph sampling (e.g. [BP06, KIMA04a, MZW05]). In this thesis we develop an algorithm to count all instances of a particular subgraph, which can be used to query whether a given sub-graph is a significant motif. This method can be used to perform exact counting of network motifs faster and with less memory than previous methods, and can also be combined with subgraph sampling to find larger motifs than ever before – we have found motifs with up to 15 nodes and explored subgraphs up to 20 nodes. Unlike previous methods, this method can also be used to explore motif clustering and can be combined with network alignment techniques [FNS+06, KSK+03]. We also present new methods of estimating parameters for models of biologica