NetMatch: a Cytoscape plugin for searching biological networks

Dissecting molecular network structures using a network subgraph approach

Biological processes are based on molecular networks, which exhibit biological functions through interactions of genetic elements or proteins. This study presents a graph-based method to characterize molecular networks by decomposing the networks into directed multigraphs: network subgraphs. Spectral graph theory, reciprocity and complexity measures were used to quantify the network subgraphs. Graph energy, reciprocity and cyclomatic complexity can optimally specify network subgraphs with some degree of degeneracy. Seventy-one molecular networks were analyzed from three network types: cancer networks, signal transduction networks, and cellular processes. Molecular networks are built from a finite number of subgraph patterns and subgraphs with large graph energies are not present, which implies a graph energy cutoff. In addition, certain subgraph patterns are absent from the three network types. Thus, the Shannon entropy of the subgraph frequency distribution is not maximal. Furthermore, frequently-observed subgraphs are irreducible graphs. These novel findings warrant further investigation and may lead to important applications. Finally, we observed that cancer-related cellular processes are enriched with subgraph-associated driver genes. Our study provides a systematic approach for dissecting biological networks and supports the conclusion that there are organizational principles underlying molecular networks.

A Guide to Conquer the Biological Network Era Using Graph Theory

Networks are one of the most common ways to represent biological systems as complex sets of binary interactions or relations between different bioentities. In this article, we discuss the basic graph theory concepts and the various graph types, as well as the available data structures for storing and reading graphs. In addition, we describe several network properties and we highlight some of the widely used network topological features. We briefly mention the network patterns, motifs and models, and we further comment on the types of biological and biomedical networks along with their corresponding computer- and human-readable file formats. Finally, we discuss a variety of algorithms and metrics for network analyses regarding graph drawing, clustering, visualization, link prediction, perturbation, and network alignment as well as the current state-of-the-art tools. We expect this review to reach a very broad spectrum of readers varying from experts to beginners while encouraging them to enhance the field further.

Non-coding RNA regulatory networks

It is well established that the vast majority of human RNA transcripts do not encode for proteins and that non-coding RNAs regulate cell physiology and shape cellular functions. A subset of them is involved in gene regulation at different levels, from epigenetic gene silencing to post-transcriptional regulation of mRNA stability. Notably, the aberrant expression of many non-coding RNAs has been associated with aggressive pathologies. Rapid advances in network biology indicates that the robustness of cellular processes is the result of specific properties of biological networks such as scale-free degree distribution and hierarchical modularity, suggesting that regulatory network analyses could provide new insights on gene regulation and dysfunction mechanisms. In this study we present an overview of public repositories where non-coding RNA-regulatory interactions are collected and annotated, we discuss unresolved questions for data integration and we recall existing resources to build and analyse networks.

A gene regulatory architecture that controls region-independent dynamics of oligodendrocyte differentiation

Oligodendrocytes (OLs) facilitate information processing in the vertebrate central nervous system via axonal ensheathment. The structure and dynamics of the regulatory network that mediates oligodendrogenesis are poorly understood. We employed bioinformatics and meta-analysis of high-throughput datasets to reconstruct a regulatory network underpinning OL differentiation. From this network, we identified families of feedforward loops comprising the transcription factors (TFs) Olig2, Sox10, and Tcf7l2 and their targets. Among the targets, we found eight other TFs related to OL differentiation, suggesting a hierarchical architecture in which some TFs (Olig2, Sox10, and Tcf7l2) regulate via feedforward loops the expression of others (Sox2, Sox6, Sox11, Nkx2-2, Nkx6-2, Hes5, Myt1, and Myrf). Model simulations with a kinetic model reproduced the mechanisms of OL differentiation only when in the model, Sox10-mediated repression of Tcf7l2 by miR-338/miR-155 was introduced, a prediction confirmed in genetic functional experiments. Additional model simulations suggested that OLs from dorsal regions emerge through BMP/Sox9 signaling.

Identifying miRNA synergistic regulatory networks in heterogeneous human data via network motifs

Understanding the synergism of multiple microRNAs (miRNAs) in gene regulation can provide important insights into the mechanisms of complex human diseases caused by miRNA regulation. Therefore, it is important to identify miRNA synergism and study miRNA characteristics in miRNA synergistic regulatory networks. A number of methods have been proposed to identify miRNA synergism. However, most of the methods only use downstream target genes of miRNAs to infer miRNA synergism when miRNAs can also be regulated by upstream transcription factors (TFs) at the transcriptional level. Additionally, most methods are based on statistical associations identified from data without considering the causal nature of gene regulation. In this paper, we present a causality based framework, called mirSRN (miRNA synergistic regulatory network), to infer miRNA synergism in human molecular systems by considering both downstream miRNA targets and upstream TF regulation. We apply the proposed framework to two real world datasets and discover that almost all the top 10 miRNAs with the largest node degree in the mirSRNs are associated with different human diseases, including cancer, and that the mirSRNs are approximately scale-free and small-world networks. We also find that most miRNAs in the networks are frequently synergistic with other miRNAs, and miRNAs related to the same disease are likely to be synergistic and in a cluster linked to a biological function. Synergistic miRNA pairs show higher co-expression level, and may have potential functional relationships indicating collaboration between the miRNAs. Functional validation of the identified synergistic miRNAs demonstrates that these miRNAs cause different kinds of diseases. These results deepen our understanding of the biological meaning of miRNA synergism.

A novel framework for inferring condition-specific TF and miRNA co-regulation of protein-protein interactions

Recent studies have shown that transcription factors (TFs) and microRNAs (miRNAs), while independently regulate their downstream targets, collaborate with each other to regulate gene expression. However, their synergistic roles in protein-protein interactions (PPIs) remain mostly unknown. In this paper, we present a novel framework (called CoRePPI) for inferring TF and miRNA co-regulation of PPIs. Particularly, CoRePPI is aimed at discovering the co-regulation specific to a condition of interest, by using heterogeneous data, including miRNA and messenger RNA (mRNA) expression profiles, putative miRNA targets, TF targets and PPIs. CoRePPI firstly finds the network motifs indicating the co-regulation of PPIs by TFs and miRNAs in tumor and normal conditions separately. Then by identifying the differential motifs found in one condition but not in the other, it builds the networks consisting of TFs, miRNAs and their co-regulated PPIs specific to different conditions respectively. To validate CoRePPI, we apply it to the Pan-Cancer dataset which includes the expression profiles of 12 cancer types from TCGA. Through network topology analysis, we found that the tumor and normal CoRePPI networks are scale-free. Furthermore, the results of differential and intersected network analysis between the tumor and normal CoRePPI networks suggest that only a small fraction of the regulatory relationships between TFs and miRNAs are conserved in both conditions but they co-regulate different downstream PPIs in tumor and normal conditions; and in different conditions the majority of the regulatory relationships between TFs and miRNAs are different although they may regulate the same PPIs in their respective conditions. The CoRePPI sub-networks constructed for the three types of cancers (breast cancer, lung cancer and ovarian cancer) are all scale-free, and the intersection of these CoRePPI sub-networks can be utilized as the biomarker CoRePPI sub-network of the three types of cancers. The PPI enrichment analyses of the tumor and normal CoRePPI networks suggest that the co-regulating TFs and miRNAs are significantly associated with the specific biological processes, diseases and pathways. In addition, comparing with the two non-condition-specific approaches, the tumor CoRePPI network is found to have the most enriched cancer-related PPIs. Altogether, the results uncover the combined regulatory patterns of TFs and miRNAs on the PPIs, and may provide new insights for research in cancer-associated TFs and miRNAs.

Indexing a protein-protein interaction network expedites network alignment

BACKGROUND

Network query problem aligns a small query network with an arbitrarily large target network. The complexity of this problem grows exponentially with the number of nodes in the query network if confidence in the optimality of result is desired. Scaling this problem to large query and target networks remains to be a challenge.

RESULTS

In this article, we develop a novel index structure that dramatically reduces the cost of the network query problem. Our index structure maintains a small set of reference networks where each reference network is a small, carefully chosen subnetwork from the target network. Along with each reference, we also store all of its non-overlapping and statistically significant alignments with the target network. Given a query network, we first align the query with the reference networks. If the alignment with a reference network yields a sufficiently large score, we compute an upper-bound to the alignment score between the query and the target using the alignments of that reference and the target (which is stored in our index). If the upper-bound is large enough, we employ a second round of alignment between the query and the target by respecting the mapping found in the first alignment. Our experiments on protein-protein interaction networks demonstrate that our index achieves a significant speed-up in running time over the state-of-the-art methods such as ColT. The alignment subnetworks obtained by our method are also statistically significant. Finally, we observe that our method finds biologically and statistically significant alignments across multiple species.

CONCLUSIONS

We developed a reference network based indexing structure that accelerates network query and produces functionally and statistically significant results.

NetMatchStar: an enhanced Cytoscape network querying app

We present NetMatchStar, a Cytoscape app to find all the occurrences of a query graph in a network and check for its significance as a motif with respect to seven different random models. The query can be uploaded or built from scratch using Cytoscape facilities. The app significantly enhances the previous NetMatch in style, performance and functionality. Notably NetMatchStar allows queries with wildcards.

NetMatchStar: an enhanced Cytoscape network querying app

We present NetMatchStar, a Cytoscape app to find all the occurrences of a query graph in a network and check for its significance as a motif with respect to seven different random models. The query can be uploaded or built from scratch using Cytoscape facilities. The app significantly enhances the previous NetMatch in style, performance and functionality. Notably NetMatchStar allows queries with wildcards.

SPECTRA: An Integrated Knowledge Base for Comparing Tissue and Tumor-Specific PPI Networks in Human

Protein–protein interaction (PPI) networks available in public repositories usually represent relationships between proteins within the cell. They ignore the specific set of tissues or tumors where the interactions take place. Indeed, proteins can form tissue-selective complexes, while they remain inactive in other tissues. For these reasons, a great attention has been recently paid to tissue-specific PPI networks, in which nodes are proteins of the global PPI network whose corresponding genes are preferentially expressed in specific tissues. In this paper, we present SPECTRA, a knowledge base to build and compare tissue or tumor-specific PPI networks. SPECTRA integrates gene expression and protein interaction data from the most authoritative online repositories. We also provide tools for visualizing and comparing such networks, in order to identify the expression and interaction changes of proteins across tissues, or between the normal and pathological states of the same tissue. SPECTRA is available as a web server at http://alpha.dmi.unict.it/spectra.

Systems biology approaches for advancing the discovery of effective drug combinations

Complex diseases like cancer are regulated by large, interconnected networks with many pathways affecting cell proliferation, invasion, and drug resistance. However, current cancer therapy predominantly relies on the reductionist approach of one gene-one disease. Combinations of drugs may overcome drug resistance by limiting mutations and induction of escape pathways, but given the enormous number of possible drug combinations, strategies to reduce the search space and prioritize experiments are needed. In this review, we focus on the use of computational modeling, bioinformatics and high-throughput experimental methods for discovery of drug combinations. We highlight cutting-edge systems approaches, including large-scale modeling of cell signaling networks, network motif analysis, statistical association-based models, identifying correlations in gene signatures, functional genomics, and high-throughput combination screens. We also present a list of publicly available data and resources to aid in discovery of drug combinations. Integration of these systems approaches will enable faster discovery and translation of clinically relevant drug combinations.

Graphical abstract

Transcription factor and microRNA-regulated network motifs for cancer and signal transduction networks

Abstract

Conclusions

To validate the role of network motifs in cancer formation, several examples are presented which demonstrated the effectiveness of the present approach. A web-based platform has been set up which can be accessed at: http://ppi.bioinfo.asia.edu.tw/pathway/. It is very likely that our results can supply very specific CMS missing information for certain cancer types, it is an indispensable tool for cancer biology research.

Morphisms of reaction networks that couple structure to function

BACKGROUND

The mechanisms underlying complex biological systems are routinely represented as networks. Network kinetics is widely studied, and so is the connection between network structure and behavior. However, similarity of mechanism is better revealed by relationships between network structures.

RESULTS

We define morphisms (mappings) between reaction networks that establish structural connections between them. Some morphisms imply kinetic similarity, and yet their properties can be checked statically on the structure of the networks. In particular we can determine statically that a complex network will emulate a simpler network: it will reproduce its kinetics for all corresponding choices of reaction rates and initial conditions. We use this property to relate the kinetics of many common biological networks of different sizes, also relating them to a fundamental population algorithm.

CONCLUSIONS

Structural similarity between reaction networks can be revealed by network morphisms, elucidating mechanistic and functional aspects of complex networks in terms of simpler networks.

GASOLINE: a Greedy And Stochastic algorithm for optimal Local multiple alignment of Interaction NEtworks

The analysis of structure and dynamics of biological networks plays a central role in understanding the intrinsic complexity of biological systems. Biological networks have been considered a suitable formalism to extend evolutionary and comparative biology. In this paper we present GASOLINE, an algorithm for multiple local network alignment based on statistical iterative sampling in connection to a greedy strategy. GASOLINE overcomes the limits of current approaches by producing biologically significant alignments within a feasible running time, even for very large input instances. The method has been extensively tested on a database of real and synthetic biological networks. A comprehensive comparison with state-of-the art algorithms clearly shows that GASOLINE yields the best results in terms of both reliability of alignments and running time on real biological networks and results comparable in terms of quality of alignments on synthetic networks. GASOLINE has been developed in Java, and is available, along with all the computed alignments, at the following URL: http://ferrolab.dmi.unict.it/gasoline/gasoline.html.

Searching for repetitions in biological networks: methods, resources and tools

We present here a compact overview of the data, models and methods proposed for the analysis of biological networks based on the search for significant repetitions. In particular, we concentrate on three problems widely studied in the literature: 'network alignment', 'network querying' and 'network motif extraction'. We provide (i) details of the experimental techniques used to obtain the main types of interaction data, (ii) descriptions of the models and approaches introduced to solve such problems and (iii) pointers to both the available databases and software tools. The intent is to lay out a useful roadmap for identifying suitable strategies to analyse cellular data, possibly based on the joint use of different interaction data types or analysis techniques.

Novel factors in the pathogenesis of psoriasis and potential drug candidates are found with systems biology approach

Psoriasis is a multifactorial inflammatory skin disease characterized by increased proliferation of keratinocytes, activation of immune cells and susceptibility to metabolic syndrome. Systems biology approach makes it possible to reveal novel important factors in the pathogenesis of the disease. Protein-protein, protein-DNA, merged (containing both protein-protein and protein-DNA interactions) and chemical-protein interaction networks were constructed consisting of differentially expressed genes (DEG) between lesional and non-lesional skin samples of psoriatic patients and/or the encoded proteins. DEGs were determined by microarray meta-analysis using MetaOMICS package. We used STRING for protein-protein, CisRED for protein-DNA and STITCH for chemical-protein interaction network construction. General network-, cluster- and motif-analysis were carried out in each network. Many DEG-coded proteins (CCNA2, FYN, PIK3R1, CTGF, F3) and transcription factors (AR, TFDP1, MEF2A, MECOM) were identified as central nodes, suggesting their potential role in psoriasis pathogenesis. CCNA2, TFDP1 and MECOM might play role in the hyperproliferation of keratinocytes, whereas FYN may be involved in the disturbed immunity in psoriasis. AR can be an important link between inflammation and insulin resistance, while MEF2A has role in insulin signaling. A controller sub-network was constructed from interlinked positive feedback loops that with the capability to maintain psoriatic lesional phenotype. Analysis of chemical-protein interaction networks detected 34 drugs with previously confirmed disease-modifying effects, 23 drugs with some experimental evidences, and 21 drugs with case reports suggesting their positive or negative effects. In addition, 99 unpublished drug candidates were also found, that might serve future treatments for psoriasis.

GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures

Biological applications, from genomics to ecology, deal with graphs that represents the structure of interactions. Analyzing such data requires searching for subgraphs in collections of graphs. This task is computationally expensive. Even though multicore architectures, from commodity computers to more advanced symmetric multiprocessing (SMP), offer scalable computing power, currently published software implementations for indexing and graph matching are fundamentally sequential. As a consequence, such software implementations (i) do not fully exploit available parallel computing power and (ii) they do not scale with respect to the size of graphs in the database. We present GRAPES, software for parallel searching on databases of large biological graphs. GRAPES implements a parallel version of well-established graph searching algorithms, and introduces new strategies which naturally lead to a faster parallel searching system especially for large graphs. GRAPES decomposes graphs into subcomponents that can be efficiently searched in parallel. We show the performance of GRAPES on representative biological datasets containing antiviral chemical compounds, DNA, RNA, proteins, protein contact maps and protein interactions networks.

Pattern search in BioPAX models

Motivation: BioPAX is a standard language for representing complex cellular processes, including metabolic networks, signal transduction and gene regulation. Owing to the inherent complexity of a BioPAX model, searching for a specific type of subnetwork can be non-trivial and difficult.

Results: We developed an open source and extensible framework for defining and searching graph patterns in BioPAX models. We demonstrate its use with a sample pattern that captures directed signaling relations between proteins. We provide search results for the pattern obtained from the Pathway Commons database and compare these results with the current data in signaling databases SPIKE and SignaLink. Results show that a pattern search in public pathway data can identify a substantial amount of signaling relations that do not exist in signaling databases.

Availability: BioPAX-pattern software was developed in Java. Source code and documentation is freely available at http://code.google.com/p/biopax-pattern under Lesser GNU Public License.

Contact:patternsearch@cbio.mskcc.org

Supplementary information:Supplementary data are available at Bioinformatics online.

RMOD: a tool for regulatory motif detection in signaling network

Regulatory motifs are patterns of activation and inhibition that appear repeatedly in various signaling networks and that show specific regulatory properties. However, the network structures of regulatory motifs are highly diverse and complex, rendering their identification difficult. Here, we present a RMOD, a web-based system for the identification of regulatory motifs and their properties in signaling networks. RMOD finds various network structures of regulatory motifs by compressing the signaling network and detecting the compressed forms of regulatory motifs. To apply it into a large-scale signaling network, it adopts a new subgraph search algorithm using a novel data structure called path-tree, which is a tree structure composed of isomorphic graphs of query regulatory motifs. This algorithm was evaluated using various sizes of signaling networks generated from the integration of various human signaling pathways and it showed that the speed and scalability of this algorithm outperforms those of other algorithms. RMOD includes interactive analysis and auxiliary tools that make it possible to manipulate the whole processes from building signaling network and query regulatory motifs to analyzing regulatory motifs with graphical illustration and summarized descriptions. As a result, RMOD provides an integrated view of the regulatory motifs and mechanism underlying their regulatory motif activities within the signaling network. RMOD is freely accessible online at the following URL: http://pks.kaist.ac.kr/rmod.

Structure and dynamics of molecular networks: a novel paradigm of drug discovery: a comprehensive review

Despite considerable progress in genome- and proteome-based high-throughput screening methods and in rational drug design, the increase in approved drugs in the past decade did not match the increase of drug development costs. Network description and analysis not only give a systems-level understanding of drug action and disease complexity, but can also help to improve the efficiency of drug design. We give a comprehensive assessment of the analytical tools of network topology and dynamics. The state-of-the-art use of chemical similarity, protein structure, protein-protein interaction, signaling, genetic interaction and metabolic networks in the discovery of drug targets is summarized. We propose that network targeting follows two basic strategies. The "central hit strategy" selectively targets central nodes/edges of the flexible networks of infectious agents or cancer cells to kill them. The "network influence strategy" works against other diseases, where an efficient reconfiguration of rigid networks needs to be achieved by targeting the neighbors of central nodes/edges. It is shown how network techniques can help in the identification of single-target, edgetic, multi-target and allo-network drug target candidates. We review the recent boom in network methods helping hit identification, lead selection optimizing drug efficacy, as well as minimizing side-effects and drug toxicity. Successful network-based drug development strategies are shown through the examples of infections, cancer, metabolic diseases, neurodegenerative diseases and aging. Summarizing >1200 references we suggest an optimized protocol of network-aided drug development, and provide a list of systems-level hallmarks of drug quality. Finally, we highlight network-related drug development trends helping to achieve these hallmarks by a cohesive, global approach.

A subgraph isomorphism algorithm and its application to biochemical data

Background

Graphs can represent biological networks at the molecular, protein, or species level. An important query is to find all matches of a pattern graph to a target graph. Accomplishing this is inherently difficult (NP-complete) and the efficiency of heuristic algorithms for the problem may depend upon the input graphs. The common aim of existing algorithms is to eliminate unsuccessful mappings as early as and as inexpensively as possible.

Results

We propose a new subgraph isomorphism algorithm which applies a search strategy to significantly reduce the search space without using any complex pruning rules or domain reduction procedures. We compare our method with the most recent and efficient subgraph isomorphism algorithms (VFlib, LAD, and our C++ implementation of FocusSearch which was originally distributed in Modula2) on synthetic, molecules, and interaction networks data. We show a significant reduction in the running time of our approach compared with these other excellent methods and show that our algorithm scales well as memory demands increase.

Conclusions

Subgraph isomorphism algorithms are intensively used by biochemical tools. Our analysis gives a comprehensive comparison of different software approaches to subgraph isomorphism highlighting their weaknesses and strengths. This will help researchers make a rational choice among methods depending on their application. We also distribute an open-source package including our system and our own C++ implementation of FocusSearch together with all the used datasets (http://ferrolab.dmi.unict.it/ri.html). In future work, our findings may be extended to approximate subgraph isomorphism algorithms.

CySBGN: a Cytoscape plug-in to integrate SBGN maps

Background

A standard graphical notation is essential to facilitate exchange of network representations of biological processes. Towards this end, the Systems Biology Graphical Notation (SBGN) has been proposed, and it is already supported by a number of tools. However, support for SBGN in Cytoscape, one of the most widely used platforms in biology to visualise and analyse networks, is limited, and in particular it is not possible to import SBGN diagrams.

Results

We have developed CySBGN, a Cytoscape plug-in that extends the use of Cytoscape visualisation and analysis features to SBGN maps. CySBGN adds support for Cytoscape users to visualize any of the three complementary SBGN languages: Process Description, Entity Relationship, and Activity Flow. The interoperability with other tools (CySBML plug-in and Systems Biology Format Converter) was also established allowing an automated generation of SBGN diagrams based on previously imported SBML models. The plug-in was tested using a suite of 53 different test cases that covers almost all possible entities, shapes, and connections. A rendering comparison with other tools that support SBGN was performed. To illustrate the interoperability with other Cytoscape functionalities, we present two analysis examples, shortest path calculation, and motif identification in a metabolic network.

Conclusions

CySBGN imports, modifies and analyzes SBGN diagrams in Cytoscape, and thus allows the application of the large palette of tools and plug-ins in this platform to networks and pathways in SBGN format.

CySBML: a Cytoscape plugin for SBML

SUMMARY

CySBML is a plugin designed to work with Systems Biology Markup Language (SBML) in Cytoscape having the following features: SBML import, support of the SBML layout and qualitative model packages, navigation in network layouts based on SBML structure, access to MIRIAM and SBO-based annotations and SBML validation. CySBML includes an importer for BioModels to load SBML from standard repositories.

AVAILABILITY AND IMPLEMENTATION

Freely available for non-commercial purposes through the Cytoscape plugin manager or for download at http://sourceforge.net/projects/cysbml/.

CONTACT

cysbml-team@lists.sourceforge.net

SUPPLEMENTARY INFORMATION

Tutorial, usage guide, installation instructions and additional figures are available for download at http://www.charite.de/sysbio/people/koenig/software/cysbml/.

RESQUE: network reduction using semi-Markov random walk scores for efficient querying of biological networks

MOTIVATION

Recent technological advances in measuring molecular interactions have resulted in an increasing number of large-scale biological networks. Translation of these enormous network data into meaningful biological insights requires efficient computational techniques that can unearth the biological information that is encoded in the networks. One such example is network querying, which aims to identify similar subnetwork regions in a large target network that are similar to a given query network. Network querying tools can be used to identify novel biological pathways that are homologous to known pathways, thereby enabling knowledge transfer across different organisms.

RESULTS

In this article, we introduce an efficient algorithm for querying large-scale biological networks, called RESQUE. The proposed algorithm adopts a semi-Markov random walk (SMRW) model to probabilistically estimate the correspondence scores between nodes that belong to different networks. The target network is iteratively reduced based on the estimated correspondence scores, which are also iteratively re-estimated to improve accuracy until the best matching subnetwork emerges. We demonstrate that the proposed network querying scheme is computationally efficient, can handle any network query with an arbitrary topology and yields accurate querying results.

AVAILABILITY

The source code of RESQUE is freely available at http://www.ece.tamu.edu/~bjyoon/RESQUE/

RefNetBuilder: a platform for construction of integrated reference gene regulatory networks from expressed sequence tags

Background

Gene Regulatory Networks (GRNs) provide integrated views of gene interactions that control biological processes. Many public databases contain biological interactions extracted from experimentally validated literature reports, but most furnish only information for a few genetic model organisms. In order to provide a bioinformatic tool for researchers who work with non-model organisms, we developed RefNetBuilder, a new platform that allows construction of putative reference pathways or GRNs from expressed sequence tags (ESTs).

Results

RefNetBuilder was designed to have the flexibility to extract and archive pathway or GRN information from public databases such as the Kyoto Encyclopedia of Genes and Genomes (KEGG). It features sequence alignment tools such as BLAST to allow mapping ESTs to pathways and GRNs in model organisms. A scoring algorithm was incorporated to rank and select the best match for each query EST. We validated RefNetBuilder using DNA sequences of Caenorhabditis elegans, a model organism having manually curated KEGG pathways. Using the earthworm Eisenia fetida as an example, we demonstrated the functionalities and features of RefNetBuilder.

Conclusions

The RefNetBuilder provides a standalone application for building reference GRNs for non-model organisms on a number of operating system platforms with standard desktop computer hardware. As a new bioinformatic tool aimed for constructing putative GRNs for non-model organisms that have only ESTs available, RefNetBuilder is especially useful to explore pathway- or network-related information in these organisms.

NetDS: a Cytoscape plugin to analyze the robustness of dynamics and feedforward/feedback loop structures of biological networks

SUMMARY

NetDS is a novel Cytoscape plugin that conveniently simulates dynamics related to robustness, and examines structural properties with respect to feedforward/feedback loops. It can evaluate how robustly a network sustains a stable state against mutations by employing a Boolean network model. In addition, the plugin can examine all feedforward/feedback loops appearing in a network and determine whether or not a pair of loops is coupled. Random networks can also be generated to evaluate whether or not an interesting finding in real biological networks is significantly random.

AVAILABILITY

NetDS is freely available for non-commercial purposes at http://netds.sourceforge.net/.

CONTACT

kwonyk@ulsan.ac.kr

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

RINQ: Reference-based Indexing for Network Queries

We consider the problem of similarity queries in biological network databases. Given a database of networks, similarity query returns all the database networks whose similarity (i.e. alignment score) to a given query network is at least a specified similarity cutoff value. Alignment of two networks is a very costly operation, which makes exhaustive comparison of all the database networks with a query impractical. To tackle this problem, we develop a novel indexing method, named RINQ (Reference-based Indexing for Biological Network Queries). Our method uses a set of reference networks to eliminate a large portion of the database quickly for each query. A reference network is a small biological network. We precompute and store the alignments of all the references with all the database networks. When our database is queried, we align the query network with all the reference networks. Using these alignments, we calculate a lower bound and an approximate upper bound to the alignment score of each database network with the query network. With the help of upper and lower bounds, we eliminate the majority of the database networks without aligning them to the query network. We also quickly identify a small portion of these as guaranteed to be similar to the query. We perform pairwise alignment only for the remaining networks. We also propose a supervised method to pick references that have a large chance of filtering the unpromising database networks. Extensive experimental evaluation suggests that (i) our method reduced the running time of a single query on a database of around 300 networks from over 2 days to only 8 h; (ii) our method outperformed the state of the art method Closure Tree and SAGA by a factor of three or more; and (iii) our method successfully identified statistically and biologically significant relationships across networks and organisms.

Asymmetric comparison and querying of biological networks

Comparing and querying the protein-protein interaction (PPI) networks of different organisms is important to infer knowledge about conservation across species. Known methods that perform these tasks operate symmetrically, i.e., they do not assign a distinct role to the input PPI networks. However, in most cases, the input networks are indeed distinguishable on the basis of how the corresponding organism is biologically well characterized. In this paper a new idea is developed, that is, to exploit differences in the characterization of organisms at hand in order to devise methods for comparing their PPI networks. We use the PPI network (called Master) of the best characterized organism as a fingerprint to guide the alignment process to the second input network (called Slave), so that generated results preferably retain the structural characteristics of the Master network. Technically, this is obtained by generating from the Master a finite automaton, called alignment model, which is then fed with (a linearization of) the Slave for the purpose of extracting, via the Viterbi algorithm, matching subgraphs. We propose an approach able to perform global alignment and network querying, and we apply it on PPI networks. We tested our method showing that the results it returns are biologically relevant.

Biological network querying techniques: analysis and comparison

Research in systems biology has made available large amounts of data about interactions among cell building blocks (e.g., proteins, genes). To properly look up these data and mine useful information, the design and development of automatic tools has become crucial. These tools leverage Biological Networks as a formal model to encode molecular interactions. Biological networks can be fed as input to graph-based techniques useful to infer new information about cellular activity and evolutive processes of the species. In this context, a rather interesting family of techniques is that of network querying. Network querying tools search a whole biological network to identify conserved occurrences of a given query module for transferring biological knowledge. Indeed, inasmuch as the query network generally encodes a well-characterized functional module, its occurrences in the queried network suggest that the latter (and, as such, the corresponding organism) features the function encoded by the former. The aim of this paper is that of analyzing and comparing tools devised to query biological networks. This analysis is intended to help in understanding problems and research issues, state of the art and opportunities for researchers working in this area.

Displaying chemical information on a biological network using Cytoscape

Cytoscape is an open-source software package that is widely used to integrate and visualize diverse data sets in biology. This chapter explains how to use Cytoscape to integrate open-source chemical information with a biological network. By visualizing information about known compound-target interactions in the context of a biological network of interest, one can rapidly identify novel avenues to perturb the system with compounds and, for example, potentially identify therapeutically relevant targets. Herein, two different protocols are explained in detail, with no prior knowledge of Cytoscape assumed, which demonstrate how to incorporate data from the ChEMBL database with either a gene-gene or a protein-protein interaction network. ChEMBL is a very large, open-source repository of compound-target information available from the European Molecular Biology Laboratory.

Early Career Research Award Lecture. Structure, evolution and dynamics of transcriptional regulatory networks

The availability of entire genome sequences and the wealth of literature on gene regulation have enabled researchers to model an organism's transcriptional regulation system in the form of a network. In such a network, TFs (transcription factors) and TGs (target genes) are represented as nodes and regulatory interactions between TFs and TGs are represented as directed links. In the present review, I address the following topics pertaining to transcriptional regulatory networks. (i) Structure and organization: first, I introduce the concept of networks and discuss our understanding of the structure and organization of transcriptional networks. (ii) Evolution: I then describe the different mechanisms and forces that influence network evolution and shape network structure. (iii) Dynamics: I discuss studies that have integrated information on dynamics such as mRNA abundance or half-life, with data on transcriptional network in order to elucidate general principles of regulatory network dynamics. In particular, I discuss how cell-to-cell variability in the expression level of TFs could permit differential utilization of the same underlying network by distinct members of a genetically identical cell population. Finally, I conclude by discussing open questions for future research and highlighting the implications for evolution, development, disease and applications such as genetic engineering.

Topology-free querying of protein interaction networks

In the network querying problem, one is given a protein complex or pathway of species A and a protein-protein interaction network of species B; the goal is to identify subnetworks of B that are similar to the query in terms of sequence, topology, or both. Existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species A; however, in practice, this topology is often not known. To address this problem, we develop a topology-free querying algorithm, which we call Torque. Given a query, represented as a set of proteins, Torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. The algorithm uses alternatively dynamic programming and integer linear programming for the search task. We test Torque with queries from yeast, fly, and human, where we compare it to the QNet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. Torque detects many more matches than QNet, while giving results that are highly functionally coherent.

Investigating transcriptional regulation: from analysis of complex networks to discovery of cis-regulatory elements

Regulation of gene expression at the transcriptional level is a fundamental mechanism that is well conserved in all cellular systems. Due to advances in large-scale experimental analyses, we now have a wealth of information on gene regulation such as mRNA expression level across multiple conditions, genome-wide location data of transcription factors and data on transcription factor binding sites. This knowledge can be used to reconstruct transcriptional regulatory networks. Such networks are usually represented as directed graphs where regulatory interactions are depicted as directed edges from the transcription factor nodes to the target gene nodes. This abstract representation allows us to apply graph theory to study transcriptional regulation at global and local levels, to predict regulatory motifs and regulatory modules such as regulons and to compare the regulatory network of different genomes. Here we review some of the available computational methodologies for studying transcriptional regulatory networks as well as their interpretation.

Organization of physical interactomes as uncovered by network schemas

Large-scale protein-protein interaction networks provide new opportunities for understanding cellular organization and functioning. We introduce network schemas to elucidate shared mechanisms within interactomes. Network schemas specify descriptions of proteins and the topology of interactions among them. We develop algorithms for systematically uncovering recurring, over-represented schemas in physical interaction networks. We apply our methods to the S. cerevisiae interactome, focusing on schemas consisting of proteins described via sequence motifs and molecular function annotations and interacting with one another in one of four basic network topologies. We identify hundreds of recurring and over-represented network schemas of various complexity, and demonstrate via graph-theoretic representations how more complex schemas are organized in terms of their lower-order constituents. The uncovered schemas span a wide range of cellular activities, with many signaling and transport related higher-order schemas. We establish the functional importance of the schemas by showing that they correspond to functionally cohesive sets of proteins, are enriched in the frequency with which they have instances in the H. sapiens interactome, and are useful for predicting protein function. Our findings suggest that network schemas are a powerful paradigm for organizing, interrogating, and annotating cellular networks.

Integrating and annotating the interactome using the MiMI plugin for cytoscape

The MiMI molecular interaction repository integrates data from multiple sources, resolves interactions to standard gene names and symbols, links to annotation data from GO, MeSH and PubMed and normalizes the descriptions of interaction type. Here, we describe a Cytoscape plugin that retrieves interaction and annotation data from MiMI and links out to multiple data sources and tools. Community annotation of the interactome is supported.

AVAILABILITY

MiMI plugin v3.0.1 can be installed from within Cytoscape 2.6 using the Cytoscape plugin manager in 'Network and Attribute I/0' category. The plugin is also preloaded when Cytoscape is launched using Java WebStart at http://mimi.ncibi.org by querying a gene and clicking 'View in MiMI Plugin for Cytoscape' link.

NetGrep: fast network schema searches in interactomes

NetGrep (http://genomics.princeton.edu/singhlab/netgrep/) is a system for searching protein interaction networks for matches to user-supplied 'network schemas'. Each schema consists of descriptions of proteins (for example, their molecular functions or putative domains) along with the desired topology and types of interactions among them. Schemas can thus describe domain-domain interactions, signaling and regulatory pathways, or more complex network patterns. NetGrep provides an advanced graphical interface for specifying schemas and fast algorithms for extracting their matches.

Mapping the human protein interactome

Interactions are the essence of all biomolecules because they cannot fulfill their roles without interacting with other molecules. Hence, mapping the interactions of biomolecules can be useful for understanding their roles and functions. Furthermore, the development of molecular based systems biology requires an understanding of the biomolecular interactions. In recent years, the mapping of protein-protein interactions in different species has been reported, but few reports have focused on the large-scale mapping of protein-protein interactions in human. Here, we review the developments in protein interaction mapping and we discuss issues and strategies for the mapping of the human protein interactome.

GraphFind: enhancing graph searching by low support data mining techniques

BACKGROUND

Biomedical and chemical databases are large and rapidly growing in size. Graphs naturally model such kinds of data. To fully exploit the wealth of information in these graph databases, a key role is played by systems that search for all exact or approximate occurrences of a query graph. To deal efficiently with graph searching, advanced methods for indexing, representation and matching of graphs have been proposed.

RESULTS

This paper presents GraphFind. The system implements efficient graph searching algorithms together with advanced filtering techniques that allow approximate search. It allows users to select candidate subgraphs rather than entire graphs. It implements an effective data storage based also on low-support data mining.

CONCLUSIONS

GraphFind is compared with Frowns, GraphGrep and gIndex. Experiments show that GraphFind outperforms the compared systems on a very large collection of small graphs. The proposed low-support mining technique which applies to any searching system also allows a significant index space reduction.

Biomolecular network querying: a promising approach in systems biology

The rapid accumulation of various network-related data from multiple species and conditions (e.g. disease versus normal) provides unprecedented opportunities to study the function and evolution of biological systems. Comparison of biomolecular networks between species or conditions is a promising approach to understanding the essential mechanisms used by living organisms. Computationally, the basic goal of this network comparison or 'querying' is to uncover identical or similar subnetworks by mapping the queried network (e.g. a pathway or functional module) to another network or network database. Such comparative analysis may reveal biologically or clinically important pathways or regulatory networks. In particular, we argue that user-friendly tools for network querying will greatly enhance our ability to study the fundamental properties of biomolecular networks at a system-wide level.

Integration of biological networks and gene expression data using Cytoscape

Cytoscape is a free software package for visualizing, modeling and analyzing molecular and genetic interaction networks. This protocol explains how to use Cytoscape to analyze the results of mRNA expression profiling, and other functional genomics and proteomics experiments, in the context of an interaction network obtained for genes of interest. Five major steps are described: (i) obtaining a gene or protein network, (ii) displaying the network using layout algorithms, (iii) integrating with gene expression and other functional attributes, (iv) identifying putative complexes and functional modules and (v) identifying enriched Gene Ontology annotations in the network. These steps provide a broad sample of the types of analyses performed by Cytoscape.