DualAligner: a dual alignment-based strategy to align protein interaction networks.

MOTIVATION: Given the growth of large-scale protein-protein interaction (PPI) networks obtained across multiple species and conditions, network alignment is now an important research problem. Network alignment performs comparative analysis across multiple PPI networks to understand their connections and relationships. However, PPI data in high-throughput experiments still suffer from significant false-positive and false-negatives rates. Consequently, high-confidence network alignment across entire PPI networks is not possible. At best, local network alignment attempts to alleviate this problem by completely ignoring low-confidence mappings; global network alignment, on the other hand, pairs all proteins regardless. To this end, we propose an alternative strategy: instead of full alignment across the entire network or completely ignoring low-confidence regions, we aim to perform highly specific protein-to-protein alignments where data confidence is high, and fall back on broader functional region-to-region alignment where detailed protein-protein alignment cannot be ascertained. The basic idea is to provide an alignment of multiple granularities to allow biological predictions at varying specificity. RESULTS: DualAligner performs dual network alignment, in which both region-to-region alignment, where whole subgraph of one network is aligned to subgraph of another, and protein-to-protein alignment, where individual proteins in networks are aligned to one another, are performed to achieve higher accuracy network alignments. Dual network alignment is achieved in DualAligner via background information provided by a combination of Gene Ontology annotation information and protein interaction network data. We tested DualAligner on the global networks from IntAct and demonstrated the superiority of our approach compared with state-of-the-art network alignment methods. We studied the effects of parameters in DualAligner in controlling the quality of the alignment. We also performed a case study that illustrates the utility of our approach. AVAILABILITY AND IMPLEMENTATION: http://www.cais.ntu.edu.sg/∼assourav/DualAligner/.

DiffNet: automatic differential functional summarization of dE-MAP networks.

The study of genetic interaction networks that respond to changing conditions is an emerging research problem. Recently, Bandyopadhyay et al. (2010) proposed a technique to construct a differential network (dE-MAPnetwork) from two static gene interaction networks in order to map the interaction differences between them under environment or condition change (e.g., DNA-damaging agent). This differential network is then manually analyzed to conclude that DNA repair is differentially effected by the condition change. Unfortunately, manual construction of differential functional summary from a dE-MAP network that summarizes all pertinent functional responses is time-consuming, laborious and error-prone, impeding large-scale analysis on it. To this end, we propose DiffNet, a novel data-driven algorithm that leverages Gene Ontology (go) annotations to automatically summarize a dE-MAP network to obtain a high-level map of functional responses due to condition change. We tested DiffNet on the dynamic interaction networks following MMS treatment and demonstrated the superiority of our approach in generating differential functional summaries compared to state-of-the-art graph clustering methods. We studied the effects of parameters in DiffNet in controlling the quality of the summary. We also performed a case study that illustrates its utility.

FACETS: multi-faceted functional decomposition of protein interaction networks.

MOTIVATION: The availability of large-scale curated protein interaction datasets has given rise to the opportunity to investigate higher level organization and modularity within the protein-protein interaction (PPI) network using graph theoretic analysis. Despite the recent progress, systems level analysis of high-throughput PPIs remains a daunting task because of the amount of data they present. In this article, we propose a novel PPI network decomposition algorithm called FACETS in order to make sense of the deluge of interaction data using Gene Ontology (GO) annotations. FACETS finds not just a single functional decomposition of the PPI network, but a multi-faceted atlas of functional decompositions that portray alternative perspectives of the functional landscape of the underlying PPI network. Each facet in the atlas represents a distinct interpretation of how the network can be functionally decomposed and organized. Our algorithm maximizes interpretative value of the atlas by optimizing inter-facet orthogonality and intra-facet cluster modularity. RESULTS: We tested our algorithm on the global networks from IntAct, and compared it with gold standard datasets from MIPS and KEGG. We demonstrated the performance of FACETS. We also performed a case study that illustrates the utility of our approach. SUPPLEMENTARY INFORMATION: Supplementary data are available at the Bioinformatics online. AVAILABILITY: Our software is available freely for non-commercial purposes from: http://www.cais.ntu.edu.sg/~assourav/Facets/

FUSE: a profit maximization approach for functional summarization of biological networks.

BACKGROUND: The availability of large-scale curated protein interaction datasets has given rise to the opportunity to investigate higher level organization and modularity within the protein interaction network (PPI) using graph theoretic analysis. Despite the recent progress, systems level analysis of PPIS remains a daunting task as it is challenging to make sense out of the deluge of high-dimensional interaction data. Specifically, techniques that automatically abstract and summarize PPIS at multiple resolutions to provide high level views of its functional landscape are still lacking. We present a novel data-driven and generic algorithm called FUSE (Functional Summary Generator) that generates functional maps of a PPI at different levels of organization, from broad process-process level interactions to in-depth complex-complex level interactions, through a pro t maximization approach that exploits Minimum Description Length (MDL) principle to maximize information gain of the summary graph while satisfying the level of detail constraint. RESULTS: We evaluate the performance of FUSE on several real-world PPIS. We also compare FUSE to state-of-the-art graph clustering methods with GO term enrichment by constructing the biological process landscape of the PPIS. Using AD network as our case study, we further demonstrate the ability of FUSE to quickly summarize the network and identify many different processes and complexes that regulate it. Finally, we study the higher-order connectivity of the human PPI. CONCLUSION: By simultaneously evaluating interaction and annotation data, FUSE abstracts higher-order interaction maps by reducing the details of the underlying PPI to form a functional summary graph of interconnected functional clusters. Our results demonstrate its effectiveness and superiority over state-of-the-art graph clustering methods with GO term enrichment.