PageRank Based Core-Attachment Model to Detect Protein Complexes by Analysing Protein Networks

Abstract

Virtually all major biological processes in cells are performed by assemblies of physically interacting proteins which are commonly known as protein complexes. Hence, the detection of protein complexes has become a fundamental task in understanding the higher order biological functions in living organisms. Recent advances in highthroughput techniques to infer protein-protein interactions (PPI) data have facilitated the need of computational approaches to analyse them e ciently, and to reconstruct protein complexes accurately. Analysing protein interaction networks (PPI networks) to detect community structures is a popular computational approach to detect protein complexes. Most of the existing complex detection algorithms based on this approach, are not robust against the sparse and noisy nature of the PPI networks, thus failing to achieve the desired level of performance. Furthermore, most of these techniques are primarily relied on the topological properties of the network and have incorporated a minimal number of biological insights with their algorithms, which further contribute to the limitations in their performance. In this thesis, we address some of these issues by proposing WMCORERanker, a novel protein complex detection algorithm which incorporates multiple forms of biological insights to accurately reconstruct protein complexes. In particular, we designed the core mechanism of our algorithm, based on the experimentally observed \Core-Attachment" organizational structure of protein complexes. Core-Attachment model essentially requires the identi cation of core proteins which are central and critical to the functioning of a particular protein complex. A common approach to identify central proteins is to use network centrality measures. PageRank technique, which initially emerged from the web science, is one such successful centrality measure, extensively used across various disciplines. Based on this background we hypothesise, that with su cient biological prior knowledge, PageRank algorithm can accurately capture these core proteins, leading to the accurate reconstruction of protein complexes. Speci cally, we have incorporated evolutionary relationship based information of proteins with the PageRank algorithm, and successfully demonstrated that it can accurately capture core proteins. WMCORERanker is the rst algorithm iii ever to use PageRank to detect core proteins and reconstruct the protein complexes based on the Core-Attachment model. WMCORERanker outperforms all the existing methods in recall, while remaining competitive at the precision rate. The best recall rate we achieved can accurately quantify the capability of our algorithm to retrieve the largest number of benchmark complexes than any other method, indicating that the other predicted, yet unmatched complexes also hold a high potential to be actual protein complexes.