home · mobile · calendar · defenses · 2010-2011 · 

Thesis Defense - Gallagher

Graph Connectivity: Approximation Algorithms and Applications to Protein-Protein Interaction Networks
Computer Science PhD Candidate

A graph is connected if there is a path between any two of its vertices and k-connected if there are at least k disjoint paths between any two vertices. A graph is k-edge-connected if none of the k paths share any edges and k-vertex-connected (or k-connected) if they do not share any intermediate vertices. We examine some problems related to k-connectivity and an application.

We have looked at the k-edge-connected spanning subgraph problem: given a k-edge-connected graph, find the smallest spanning subgraph that is still k-edge-connected. We improved two algorithms for approximating solutions to this problem. The first algorithm transforms the problem into an integer linear program, relaxes it into a real-valued linear program and solves it, then obtains an approximate solution to the original problem by rounding non-integer values. We have improved the approximation ratio by giving a better scheme for rounding the edges and bounding the number of fractional edges. The second algorithm finds a subgraph where every vertex has a minimum degree, then augments the subgraph by adding edges until it is k-edge-connected. We improve this algorithm by bounding the number of edges that could be added in the augmentation step.

We have also applied the idea of k-connectivity to protein-protein interaction (PPI) networks, biological graphs where vertices represent proteins and edges represent experimentally determined physical interactions. Because few PPI networks are even 1-connected, we developed algorithms to find the most highly connected subgraphs of a graph. We applied our algorithms to a large network of yeast protein interactions and found that the most highly connected subgraph was a 16-connected subgraph of membrane proteins that had never before been identified as a module and is of interest to biologists. We also looked at graphs of proteins known to be co-complexed and found that a significant number contained 3-connected subgraphs, one of the features that most differentiated complexes from random graphs.

Committee: Debra Goldberg, Assistant Professor (Co-Chair)
Harold (Hal) Gabow, Professor (Co-Chair)
John Black, Associate Professor
Andrzej Ehrenfeucht, Distinguished Professor
Lawrence Hunter, University of Colorado School of Medicine
San Skulrattanakulchai, Gustavus Adolphus College
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)