COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Algorithms for biological network alignment
by Flannick, Jason, Ph.D., Stanford University, 2009, 152; 3343954
Abstract (Summary)

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) Græmlin, the first network aligner to align multiple large interaction networks efficiently; (2) Græmlin 1.1, a network aligner that uses a training set of network alignments to improve Græmlin's accuracy; and (3) Græmlin 2.0, a network aligner that uses machine learning techniques to find the most accurate network alignments to date. Even though Græmlin 2.0 supersedes Græmlin and Græmlin 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.

Indexing (document details)
Advisor: Batzoglou, Serafim
School: Stanford University
School Location: United States -- California
Source: DAI-B 70/01, Dissertation Abstracts International
Subjects: Bioinformatics, Computer science
Keywords: Biological networks, Interaction networks, Network alignment
Publication Number: 3343954
ISBN: 978-0-549-99336-0
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy