SHORTCUT BASED GRAPH COARSENING FOR PROTEIN INTERACTION NETWORK VISUALIZATION
Zhong Li · OhioLink ETD Center (Ohio Library and Information Network) · 2001
Protein-protein interactions play important role in various biological processes.These interactions inside an organism constitute a complex network.A global view of this network is very useful in providing molecular and genetic scientists with a reference guide to aid detailed exploration of the functions of proteins.In this thesis, we build up a network, named as CID(Connected Interaction Database), whose links are defined as the interactions between proteins in S.Cerevisiae.The topological properties of this CID network have been studied and compared with another network called CSD (Connected Similarity Database), in which a link denotes either a physical interaction or functional similarity.The topological results imply that both CID and CSD possess the "small world" structure, where shortcuts play important role in shortening the path length between different clusters.We propose a graph-coarsening algorithm based on these shortcuts and cut nodes to identify clusters presented in these network and generate a simplified "backbone" structure of CID and CSD.Studies on the "functional" distribution inside some clusters demonstrate that proteins with similar function (in broad sense as referring to both "cellular role" and "biological function") are more likely to be clustered together.Using the combination of physical interaction and sequence similarity data, we correctly predicted functional categories for 82.67% among the 3,116 characterized proteins with at least one partner (the proteins that have connections with the protein under study) of known function and functional categories for 907 previously uncharacterized proteins have been predicted.