Cross-species analysis of genome-wide PPI networks has been a significant role in understanding the principles deriving evolution of cellular organizations and functions. Recently, network alignment algorithms have been proposed to predict protein functions and conserved interactions and modules. These approaches are based on the assumption that the interactions between orthologous proteins are conserved across species. However, increasing accuracy and scalability of network alignment is still challenging. We propose a global network alignment algorithm, called PrimAlign, and a local network alignment algorithm, called LePrimAlign. PrimAlign is modeled based on a Markov chain that is iteratively transited until convergence. It also incorporates the principles of the PageRank technique. LePrimAlign exploits the results of PrimAlign with many-to-many node mapping. It also applies the concept of graph entropy to detect initial cluster pairs from two networks. The initial clusters are expanded to increase the local alignment score that is formulated by a combination of intra-network and inter-network scores. The experimental results demonstrate that PrimAlign outperforms several prevalent methods with statistically significant differences in many biological and topological evaluation measures, and LePrimAlign outperforms in terms of accuracy of identified protein complexes. Furthermore, PrimAlign has superior performance in runtime to its competitors.
Reconstruction of signaling pathways is a crucial topic in current bioinformatics. Because dysregulation of biological processes by aberrant signal transduction typically causes diseases such as cancer, the pathways determined provide significant insights into disease mechanisms. A pathway is represented as a path of a signaling cascade involving a series of proteins to perform a particular function. Since a protein pair involved in signaling and response have a strong interaction, putative pathways can be detected by linkage patterns hidden in the PPI data set. Recent advances of high-throughput experimental techniques have generated PPI data on the scale of the entire genome, collectively referred to as the interactome. The availability of interactome has catalyzed the development of computational approaches to elucidate functional behaviors of proteins on a system level. We propose a novel computational approach to efficiently predict functional pathways from PPI networks given a starting protein and an ending protein. Our approach employs the integration of topological analysis of the PPI networks and semantic analysis of interacting protein pairs using Gene Ontology (GO) data. Our preliminary results show that the proposed algorithm has higher accuracy in predicting MAPK signaling pathways of S. cerevisiae than other existing methods.
PPI networks have been characterized by intrinsic features, such as modularity and existence of hubs. The concepts of modules and hubs, extending from specific (local) to general (global), suggest hierarchical structures hidden in the complex networks. Retrieving a PPI network into the hierarchical structure is thus a crucial process for better understanding of functional organizations. We propose a novel approach for restructuring a PPI network to reveal hierarchically organized functional modules and hubs. Our algorithm measures functional similarity between proteins based on the path strength model, and dynamically convert a PPI network into a hub-oriented tree structure using centrality measures. Structural hubs and potential functional modules are identified from the tree structure generated by our algorithm. The experimental results demonstrate that the proteins selected as structural hubs are essential for performing functions. In network topology, they have a role in bridging different modules as intermodule hubs.