Machine learning approaches for extracting protein complexes from protein-protein interaction networks

Abstract

Recent advances in molecular biology have led to the accumulation of large amounts of data on Protein-Protein Interaction (PPI) networks in different species, such as yeast and humans. Due to the inherent complexity, analysing such volumes of data to extract knowledge, such as protein complexes or regulatory pathways, represents not only an enormous challenge but also a great opportunity.

This Thesis explores the application of machine learning approaches to detecting protein complexes from PPI networks obtained by Tandem Affinity Purification/Mass Spectrometry (TAP-MS) experiments. TAP-MS PPI networks are usually constructed as binary, and the co-complex relations are largely ignored. In order to take into account the non-binary information of co-complex relations in TAP-MS PPI networks, a new framework for detecting protein complexes has been proposed. Under this framework, two types of graph clustering algorithms and an integrative evaluation platform combining data-driven and knowledge-based quality measures have been proposed and studied.

One type of the proposed graph clustering algorithms is random walk based graph clustering, resulting in Enhanced Random Walk with Restart (ERWR) and Random Walk with Restarting Baits (RWRB). The other type is based on the modelling of TAP-MS PPI networks as bipartite graphs, resulting in the Bipartite Graph based Clustering Algorithm (BGCA).

The ERWR algorithm has been developed from the Random Walk with Restart (RWR). The key contribution of the ERWR is the introduction of a tuning factor into the random walk process. The tuning factor strengthens connections between nodes that are closer and weakens those that are distant, so that the random walker prefers moving to nodes which are potentially in the same clusters with the starting node.

The RWRB algorithm has been developed based on the ERWR algorithm. The main contribution of RWRB is the incorporation of co-complex relations in TAP-MS PPI networks into the clustering process, by implementing a new restarting strategy during the random walk process.

The BGCA algorithm aims to detect groups of prey proteins that are significantly co-associated with the same set of bait proteins. To further improve the performance of BGCA, a strategy for combining topological features and domain knowledge, which is represented as a form of Gene Ontology (GO) based semantic similarity, has been proposed and developed.

An evaluation platform, which includes both data-driven and knowledge-based quality measures, has been developed and implemented. A total of three gold-standard datasets have also been employed to assist in the evaluation of the proposed algorithms in the Thesis. The proposed algorithms have been evaluated on large TAP-MS PPI networks. Experimental results obtained have shown that, in comparison to several state-of-the-art clustering algorithms, the proposed algorithms not only achieve best performance according to most of the quality measures but also are more robust to noise in the networks.

Date of Award	2013
Original language	English
Supervisor	Haiying Wang (Supervisor), Huiru (Jane) Zheng (Supervisor) & Hui Wang (Supervisor)