THE DISSERTATION DEFENSE FOR THE DEGREE OF Ph.D. IN COMPUTER SCIENCE FOR

                                                Robert Patro

Biological networks, such as protein-protein interaction, regulatory, or metabolic networks, provide information about biological function beyond what can be gleaned from sequence alone. Unfortunately, most computational problems associated with these networks are NP-hard. In this dissertation, we develop algorithms to tackle numerous fundamental problems in the study of biological networks.

First, we present a system for classifying the binding affinity of peptides to a diverse array of immunoglobulin antibodies. Computational approaches to this problem are integral to virtual screening and modern drug discovery. Our system is based on an ensemble of support vector machines and exhibits state-of-the-art performance. It can also be used to accurately generate de novo peptide sequences that exhibit a desired reactivity to immunoglobulin. This system placed 1st in the 2010 DREAM5 competition.

Second, we investigate the problem of biological network alignment. Aligning the biological networks of different species allows for the discovery of shared structures and conserved pathways. We introduce an original method for network alignment based on a novel spectral signature derived from the Laplacian matrices of subgraphs of the networks to be aligned. The pairwise global alignments of biological networks produced by our procedure, when evaluated under multiple metrics, are both more accurate and more robust to noise than those of previous work.

Next, we explore the problem of ancestral network reconstruction. Knowing the state of ancestral networks allows us to examine how biological pathways have evolved and how pathways in extant species have diverged from that of their common ancestor. We describe a new, combinatorial framework for representing the evolutionary histories of biological networks and present efficient algorithms for reconstructing either a single parsimonious evolutionary history, or an ensemble of near-optimal histories. Under multiple models of network evolution, our approaches are effective at inferring the ancestral network interactions. Additionally, the ensemble approach is robust to noisy input and can be used to impute missing interactions in experimental data.

Finally, we introduce a framework, GrowCode, for learning network growth models. While previous work focuses on developing growth models manually, or on procedures for learning parameters for existing models, GrowCode learns fundamentally new growth models that match target networks in a flexible way. We show that models learned by GrowCode produce networks whose target properties match those of real-world networks more closely than existing models. 

Examining Committee:

Committee Chair:                                Dr. Carl Kingsford

Dean's Representative:                      Dr. Wojciech Czaja

Committee Members:                        Dr. Hector Corrada Bravo

                                                                Dr. Mihai Pop

                                                                Dr. Amitabh Varshney