Metabolic Pathway Prediction Based On Protein-Protein Interaction Network

Bioinformatics is an interdisciplinary subject with start-up of the Human Genome Project at the end of1980s. It is one of the great frontiers of life sciences and natural sciences. Pathway prediction is the basis of various types of omics in post-genomic era. With the extreme importance, it has become one of the focuses of bioinformatics in recent years. Because of its excellent capabilities in the large-scale data processing, data mining methods prevail in the field of computer science. This thesis aims to use computational methods to exploit the metabolic pathway elements in the target species. Around the theme of analyzing protein-protein interaction network, we do some researches on PPI network analysis model, related clustering methods and the evaluation of prediction results.The main jobs include the following three aspects:1. We propose a new idea of predicting pathway indirectly through protein-protein interaction datasets. We first construct PPI network through protein-protein interaction dataset, then utilize data mining methods to mine its modular structures, namely, protein clusters. Gene corresponds to protein, by which can predict pathway in the target species.2. A relativity definition is optimized, and we improves Samanta’s method which is a hierarchical clustering algorithm based on probabilistic models. After comparing PPI network with random probability model, we discuss the selection of threshold and the redefinition of relativity in the hierarchical clustering. In order to improve the accuracy of the prediction, we do some comprehensive statistical analysis of the PPI network. When redefining the relativity, we further consider one-order and second-order interaction, adding its biological significance. We experiment on DIP dataset of E.coli, and find19clusters. Genes, corresponding to proteins in the same cluster, appear in the same pathway, which proves the effectiveness of this method.3. Spectral clustering method is used to detect the community structure in the PPI network. As the actual modular structure of protein-protein interaction network seems not so clear intuitively, we consider the global graph partitioning methods, and focus on the spectral bisection method which is based on normalized matrix(i.e. normalized Laplacian matrix) and we discuss the specific application of spectral clustering algorithm in the PPI network analysis. The experimental result indicates the practical significance of the spectral clustering algorithm.