Algorithms for Systematic Identification of Small Subgraphs

The ability to analyze large biological networks proves to be a computationally expensive task, but the information one can gain is worth the cost and effort. In cancer research for example, one is able to derive knowledge about putative drug targets by revealing the strengths and weaknesses inherent in a protein–protein interaction (PPI) network. Further, network analyses can be used to optimize high-throughput genetic and proteomic experiments. In addition, the study of biological networks is now an active part of molecular biology. In this chapter, we review techniques for studying biological networks in general but with a focus on PPI networks, including an example of a bacterial PPI network. After a brief introduction, we concentrate on methods based on the analysis of subnetworks, namely, graph motifs and graphlets.