Computational methods for discovering functional modules from protein interaction networks

Recent studies have suggested that molecular interaction networks within cells could be decomposed into different subnetworks of molecules that are involved in common biological processes. Such subnetworks are known as pathways, protein complexes or, in general, as functional modules. Many computational methods have been developed to discover functional modules based on various hypotheses. For example, network motifs are abundant subnetworks in natural networks but not random networks with similar global properties. Networks motifs have been utilized for comparing protein-protein interaction (PPI) networks of various organisms and for assessing the random models in terms of capturing the global and local properties of PPI networks. In another example, subnetwork markers are connected subnetworks from PPI networks in which member gene expressions correlate with labels of the samples. Such subnetwork markers could be used as predictors for phenotype of the samples such as the disease statuses of the patients. In this dissertation, I first present novel computational methods for discovering network motifs that use the confidence scores from protein interactions. Since there are many false positives and false negatives in the current binary PPI networks, utilizing confidence scores could result in better network motifs. I have used this algorithm to compare PPI networks of prokaryotic unicellular, eukaryotic unicellular and multicellular organisms. Later, I present two efficient and optimal computational approaches for identifying subnetwork markers. The first one utilizes confidence scores from PPIs. And the second one is a randomized algorithm for discovering the subnetworks markers with the best predicting performance. I have applied these algorithms to predict disease statuses of colon cancer and breast cancerpatients and treatment outcomes of a combinatory therapy for a breast cancer study.