| A major goal in the post-genomic era is to understand how genes and proteins organize to ultimately cause complex traits. There are multiple levels of biological organization, such as low-level interactions between pairs of molecules, higher-level metabolic pathways and molecular complexes, and ultimately high-level function of an organism.;Interaction networks summarize interactions between pairs of molecules, which are the building blocks for higher levels of molecular organization. As databases of interaction networks continue to grow in size and complexity, new computational tools are needed to search them for these higher levels of organization.;Network alignment algorithms search interaction networks from different species to identify conserved functional modules groups of molecules that cooperate to perform a common biological function. The increasing belief that functional modules are a critical level of molecular organization has led to an upsurge of network alignment research.;This dissertation focuses on three network alignment algorithms we developed: (1) Graemlin, the first network aligner to align multiple large interaction networks efficiently; (2) Graemlin 1.1, a network aligner that uses a training set of network alignments to improve Graemlin's accuracy; and (3) Graemlin 2.0, a network aligner that uses machine learning techniques to find the most accurate network alignments to date. Even though Graemlin 2.0 supersedes Graemlin and Graemlin 1.1, I discuss all three algorithms in detail to provide a complete account of our work.;To provide a context for our algorithms, I also discuss the intuition behind network alignment and review past research in the field. In addition, I review methods we developed to build the Stanford Network Database, a database of microbial interaction networks that we have analyzed extensively with our alignment algorithms.;Finally, I discuss several specific examples of network alignments. The examples illustrate the advantages of our alignment algorithms over other algorithms. I conclude with illustrations of applications we have developed for network alignment, including its use to predict protein function and characterize functional modules. |
