The Detection Of Functional Modules And Protein Function Prediction Based On Protein-protein Interaction Networks

With the development of high-throughput methods, more and more genome-scale protein-protein interaction(PPI) networks are now available, enabling us to systematically analyze the behaviors and properties of biological molecules. The researches on PPI network, including the prediction of meaningful structures(i.e. protein complexes and functional modules) in PPI networks, and the prediction of protein function using protein interaction data, are essential to reveal the underline mechanisms of life on the molecular level, and to aid explaining various diseases and identifying potential drug target. Recent advances in high-throughput experimental technologies have generated enormous amounts of data and provided valuable resources for studying protein interactions. However, these technologies suffer from high error rates because of their inherent limitations; moreover, the mechanism of protein interactions is complex, and the size of PPI data is extremely huge, which is a challenge to bioinformatics research. The main contents and creative contributions of the dissertation are summarized as follows:(1) Research on the detection of functional modules based on HKCPPI networks are modular, and contain modules that are densely connected within themselves but sparsely connected with the rest of the network. Detecting functional modules from PPI networks could sharply reduce the high complexity of PPI networks, meanwhile, those detected modules take a critical initial step towards the understanding of the composition and structure of the whole PPI network and can also helps to predict the function of unknown proteins. Due to the high level of noise as well as the topological features of PPI networks, traditional clustering techniques in a metric space cannot successfully detect functional modules in PPI networks, thus in this dissertation, we present a novel topology-based algorithm, HKC, to detect functional modules in genome-scale PPI networks. HKC algorithm mainly uses the concepts of highest k-core and cohesion to predict functional modules by identifying overlapping clusters. The experiments on two data sets and two benchmarks show that our algorithm has relatively high F-measure and exhibits better performance compared with some other methods.(2) Research on different weighting methods of PPIThe PPI data generated by high-throughput methods contains many false positives and false negatives. Thus, flexible and cheap computing methods are in great need to assess PPI data reasonably and correct the errors. In this dissertation, we propose two weighting methods for PPI, one is weighting vector based on random walk algorithm, the other is the integrated use of GO annotation information and network topology based on the concept of protein similarity. To validate the effectiveness of these two weighting methods we use MCL algorithm to detect functional modules in both weighted and unweighted PPI networks and measure the performance in many ways. The experiments show that both weighting methods can improve the performance of MCL algorithm in terms of functional module prediction.(3) Research on prediction of functional modules based on different weighting methodsBased on the effective PPI weighting methods, we propose a new algorithm named Expander for predicting functional modules, which uses the concept of affinity and find functional modules through expanding cores. Affinity uses the weights of PPI to compute the proximity between a protein and a cluster, and could be established on the basis of different weighting schemes. Therefore Expander algorithm could be used as an open framework, and we can use various information to weight PPI and then predict functional modules with this framework. Further more better performance could be achieved with appropriate weighting scheme purposively chosen for different experiment aims.(4) Research on protein function predictionPredicting function of unknown proteins is one of the biggest challenges in the post-genome era, and the ability to predict protein function efficiently is of vital importance to reveal principles of cellular organization and function, and to analyze the role of proteins in metabolic pathway, as well as providing useful information for drug design and the understanding of organism behaviors. In this dissertation, we propose an innovative iterative algorithm to predict protein function, which is called PPIPredict algorithm. Based on the functional modules detected by Expander algorithm, the PPIPredict algorithm predict the function of unannotated proteins iteratively considering each functional module as a separate PPI subgraph and all functions appearing in the module as the candidate functions. The experiments show that PPIPredict outperforms some existing methods.The researches on the above aspects constitute the main content of this dissertation, providing some new perspectives and novel approaches for related researches on PPI networks.