Neighborhood Density based Topological Network Alignment for Protein Interaction Networks

Abstract

Either natural or engineered complex systems can be represented by using networks (i.e. biological, social, computer, electrical type networks). Among various types of biological networks, protein-protein interaction (PPI) networks are considered as valuable groupings. This is because of their ability to convey interesting insights about underlying biological systems and phenomena. Proteins make up PPI networks since they naturally interact with other proteins to perform vital cellular functions inside biological systems. The recent advancement of experimental high-throughput technologies has resulted in producing large sets of biological network (e.g. PPI) data and inspired the need for devising computational techniques (i.e. alignment, integration) to analyze biological networks. Akin to biological sequence alignment, network alignment has a similar impact for improving our understanding about evolution, function and disease aspects of biological systems. But due to the computationally intractable nature (i.e. sub-graph isomorphism problem) of biological network alignment, heuristics have to be used for devising efficient network alignment approaches. Biological network alignment is twofold as, topology only and using prior knowledge (i.e. sequence, evolutionary relationships) with topology alignment. In this study we are trying to address the inherent limitations of the currently optimal topology only network alignment approach under bioinformatics and to extend it. For that we are devising a pair-wise global topology only network alignment methodology by mainly using PPI data of yeast and human species. Here, we introduce the use of novel neighborhood-density(nd) concept used for network neighborhood analysis to be incorporated with the network scoring scheme of the current optimal topology only alignment approach as heuristics for our alignment methodology. We evaluated the topological and biological quality of our nd-based methodology via 5 different criteria with the aid of yeast and human PPI networks, Gene Ontology data and protists networks. From this work, we found that our methodology exposes a higher topological quality value with an average edge correctness(EC) of 20.92%, outperforming all existing approaches for functionally similar yeast-human networks. We successfully applied our alignment methodology for predicting functions of unannotated proteins and validated them with the literature. We also reconstructed an evolutionary significant phylogenetic tree by using the completely new source of EC values, to uncover phylogeny. Likewise, while accomplishing a higher topological quality we were able to obtain a competitive biological quality compared to all other topology only network alignment approaches. Since our topology based similarity measure (i.e. nd-based) is better than other topology only alignment approaches we were able to outperform their topological qualities.