Computationally Comparing Biological Networks and Reconstructing Their Evolution
| dc.contributor.advisor | Kingsford, Carleton L | en_US |
| dc.contributor.author | Patro, Robert | en_US |
| dc.contributor.department | Computer Science | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2012-10-11T05:55:42Z | |
| dc.date.available | 2012-10-11T05:55:42Z | |
| dc.date.issued | 2012 | en_US |
| dc.description.abstract | 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 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 procedure for network alignment based on a novel topological node signature. 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 novel 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 and user-defined way. We show that models learned by GrowCode produce networks whose target properties match those of real-world networks more closely than existing models. | en_US |
| dc.identifier.uri | http://hdl.handle.net/1903/13189 | |
| dc.subject.pqcontrolled | Computer science | en_US |
| dc.subject.pqcontrolled | Bioinformatics | en_US |
| dc.subject.pquncontrolled | algorithms | en_US |
| dc.subject.pquncontrolled | evolution | en_US |
| dc.subject.pquncontrolled | graphs | en_US |
| dc.subject.pquncontrolled | networks | en_US |
| dc.title | Computationally Comparing Biological Networks and Reconstructing Their Evolution | en_US |
| dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1