Undergraduate Thesis Defense: Inferring Mechanisms of Compensation from E-MAP and SGA Data Using Local Search Algorithms for Max Cut

April 29, 2011
Halligan 111b
Speaker: Max Leiserson, Tufts University


The between-pathway model (BPM) is a well-studied motif of genetic interaction networks that provides a framework for understanding fault-tolerance of genetic functions. This work presents a new method based on a mathematically natural local search framework for max cut to uncover functionally coherent module and BPM motifs in high-throughput genetic interaction data, the likes of which has only become available in the last few years. Unlike previous methods, which also consider physical protein-protein interaction data, our method utilizes genetic interaction data only; this becomes increasingly important as high-throughput genetic interaction data is becoming available in settings where less is known about physical interaction data. We compare modules and BPMs obtained to previous methods and across different datasets. Despite needing no physical interaction information, the BPMs produced by our method are competitive with previous methods. In addition, we rigorously analyze the effects of genetic interactions of varying intensities and categories in order to develop an understanding of how differing types of genetic interaction can be understood in the larger context of genetic fault-tolerance. We find that our algorithm for generating putative instances of the BPM motif is strongest when interactions of all types and intensities are included. Finally, we present an intuitive method for identifying representative instances of BPMs from sets of nearly equivalent BPMs and examine instances of BPMs that are supported by strong biological evidence.