A model-based optimization framework for the inference on gene regulatory networks from DNA array data

MOTIVATION: Identification of the regulatory structures in genetic networks and the formulation of mechanistic models in the form of wiring diagrams is one of the significant objectives of expression profiling using DNA microarray technologies and it requires the development and application of identification frameworks. RESULTS: We have developed a novel optimization framework for identifying regulation in a genetic network using the S-system modeling formalism. We show that balance equations on both mRNA and protein species led to a formulation suitable for analyzing DNA-microarray data whereby protein concentrations have been eliminated and only mRNA relative concentrations are retained. Using this formulation, we examined if it is possible to infer a set of possible genetic regulatory networks consistent with observed mRNA expression patterns. Two origins of changes in mRNA expression patterns were considered. One derives from changes in the biophysical properties of the system that alter the molecular-interaction kinetics and/or message stability. The second is due to gene knock-outs. We reduced the identification problem to an optimization problem (of the so-called mixed-integer non-linear programming class) and we developed an algorithmic procedure for solving this optimization problem. Using simulated data generated by our mathematical model, we show that our method can actually find the regulatory network from which the data were generated. We also show that the number of possible alternate genetic regulatory networks depends on the size of the dataset (i.e. number of experiments), but this dependence is different for each of the two types of problems considered, and that a unique solution requires fewer datasets than previously estimated in the literature. This is the first method that also allows the identification of every possible regulatory network that could explain the data, when the number of experiments does not allow identification of unique regulatory structure.     

GenePath: a system for automated construction of genetic networks from mutant data

MOTIVATION: Genetic networks are often used in the analysis of biological phenomena. In classical genetics, they are constructed manually from experimental data on mutants. The field lacks formalism to guide such analysis, and accounting for all the data becomes complicated when large amounts of data are considered. RESULTS: We have developed GenePath, an intelligent assistant that automates the analysis of genetic data. GenePath employs expert-defined patterns to uncover gene relations from the data, and uses these relations as constraints in the search for a plausible genetic network. GenePath formalizes genetic data analysis, facilitates the consideration of all the available data in a consistent manner, and the examination of the large number of possible consequences of planned experiments. It also provides an explanation mechanism that traces every finding to the pertinent data. AVAILABILITY: GenePath can be accessed at http://genepath.org. SUPPLEMENTARY INFORMATION: Supplementary material is available at http://genepath.org/bi-.supp.     

Aromatic-Aromatic Interactions Database, A(2)ID: an analysis of aromatic π-networks in proteins

The geometrical arrangement of the aromatic rings of phenylalanine, tyrosine, tryptophan and histidine has been analyzed at a database level using the X-ray crystal structure of proteins from PDB in order to find out the aromatic-aromatic (π-π) networks in proteins and to understand how these aromatic rings are connected with each-other in a specific π-π network. A stringent examination of the 7848 proteins indicates that close to 89% of the proteins have occurrence of at least a network of 2π or a higher π-π network. The occurrence of π-π networks in various protein superfamilies based on SCOP, CATH and EC classifiers has also been probed in the present work. In general, we find that multidomain and membrane proteins as well as lyases show a more number of these networks. Analysis of the distribution of angle between planes of two proximal aromatic rings (?) distribution indicates that at a larger cutoff distance (between centroid of two aromatic rings), above 5?, C-H?π interactions (T-shaped orientation) are more prevalent, while π-π interactions (stacked orientation) are more prevalent at a smaller cutoff distance. The connectivity patterns of π-π networks propose strong propensity of finding arrangement of aromatic residues as clusters rather than linear arrangement. We have also made a public domain database "Aromatic-Aromatic Interactions Database" (A(2)ID) comprising of all types of π-π networks and their connectivity pattern present in proteins. It can be accessed by url http://203.199.182.73/gnsmmg/databases/aidb/aidb.html.     

PRED-CLASS: cascading neural networks for generalized protein classification and genome-wide applications.

A cascading system of hierarchical, artificial neural networks (named PRED-CLASS) is presented for the generalized classification of proteins into four distinct classes-transmembrane, fibrous, globular, and mixed-from information solely encoded in their amino acid sequences. The architecture of the individual component networks is kept very simple, reducing the number of free parameters (network synaptic weights) for faster training, improved generalization, and the avoidance of data overfitting. Capturing information from as few as 50 protein sequences spread among the four target classes (6 transmembrane, 10 fibrous, 13 globular, and 17 mixed), PRED-CLASS was able to obtain 371 correct predictions out of a set of 387 proteins (success rate approximately 96%) unambiguously assigned into one of the target classes. The application of PRED-CLASS to several test sets and complete proteomes of several organisms demonstrates that such a method could serve as a valuable tool in the annotation of genomic open reading frames with no functional assignment or as a preliminary step in fold recognition and ab initio structure prediction methods. Detailed results obtained for various data sets and completed genomes, along with a web sever running the PRED-CLASS algorithm, can be accessed over the World Wide Web at http://o2.biol.uoa.gr/PRED-CLASS.     

Modularized study of human calcium signalling pathway

Signalling pathways are complex biochemical networks responsible for regulation of numerous cellular functions. These networks function by serial and successive interactions among a large number of vital biomolecules and chemical compounds. For deciphering and analysing the underlying mechanism of such networks,a modularized study is quite helpful. Here we propose an algorithm for modularization of calcium signalling pathway of H. sapiens .The idea that "a node whose function is dependent on maximum number of other nodes tends to be the center of a sub network" is used to divide a large signalling network into smaller sub networks. Inclusion of node(s) into sub networks(s) is dependent on the outdegree of the node(s). Here outdegree of a node refers to the number of relations of the considered node lying outside the constructed sub network. Node(s) having more than c relations lying outside the expanding sub network have to be excluded from it. Here c is a specified variable based on user preference, which is finally fixed during adjustments of created sub networks, so that certain biological significance can be conferred on them.     

Interplay between Graph Topology and Correlations of Third Order in Spiking Neuronal Networks

The study of processes evolving on networks has recently become a very popular research field, not only because of the rich mathematical theory that underpins it, but also because of its many possible applications, a number of them in the field of biology. Indeed, molecular signaling pathways, gene regulation, predator-prey interactions and the communication between neurons in the brain can be seen as examples of networks with complex dynamics. The properties of such dynamics depend largely on the topology of the underlying network graph. In this work, we want to answer the following question: Knowing network connectivity, what can be said about the level of third-order correlations that will characterize the network dynamics? We consider a linear point process as a model for pulse-coded, or spiking activity in a neuronal network. Using recent results from theory of such processes, we study third-order correlations between spike trains in such a system and explain which features of the network graph (i.e. which topological motifs) are responsible for their emergence. Comparing two different models of network topology—random networks of Erdős-Rényi type and networks with highly interconnected hubs—we find that, in random networks, the average measure of third-order correlations does not depend on the local connectivity properties, but rather on global parameters, such as the connection probability. This, however, ceases to be the case in networks with a geometric out-degree distribution, where topological specificities have a strong impact on average correlations.     

Algorithms for identifying Boolean networks and related biological networks based on matrix multiplication and fingerprint function.

Due to the recent progress of the DNA microarray technology, a large number of gene expression profile data are being produced. How to analyze gene expression data is an important topic in computational molecular biology. Several studies have been done using the Boolean network as a model of a genetic network. This paper proposes efficient algorithms for identifying Boolean networks of bounded indegree and related biological networks, where identification of a Boolean network can be formalized as a problem of identifying many Boolean functions simultaneously. For the identification of a Boolean network, an O(mnD+1) time naive algorithm and a simple O (mnD) time algorithm are known, where n denotes the number of nodes, m denotes the number of examples, and D denotes the maximum in degree. This paper presents an improved O(momega-2nD + mnD+omega-3) time Monte-Carlo type randomized algorithm, where omega is the exponent of matrix multiplication (currently, omega < 2.376). The algorithm is obtained by combining fast matrix multiplication with the randomized fingerprint function for string matching. Although the algorithm and its analysis are simple, the result is nontrivial and the technique can be applied to several related problems.     

On the Complexity of Life Cycle Inventory Networks: Role of Life Cycle Processes with Network Analysis

Determining the relevance and importance of a technosphere process or a cluster of processes in relation to the rest of the industrial network can provide insights into the sustainability of supply chains: those that need to be optimized or controlled/safeguarded. Network analysis (NA) can offer a broad framework of indicators to tackle this problem. In this article, we present a detailed analysis of a life cycle inventory (LCI) model from an NA perspective. Specifically, the network is represented as a directed graph and the “emergy” numeraire is used as the weight associated with the arcs of the network. The case study of a technological system for drinking water production is presented. We investigate the topological and structural characteristics of the network representation of this system and compare properties of its weighted and unweighted network, as well as the importance of nodes (i.e., life cycle unit processes). By identifying a number of advantages and limitations linked to the modeling complexity of such emergy‐LCI networks, we classify the LCI technosphere network of our case study as a complex network belonging to the scale‐free network family. The salient feature of this network family is represented by the presence of “hubs”: nodes that connect with many other nodes. Hub failures may imply relevant changes, decreases, or even breaks in the connectedness with other smaller hubs and nodes of the network. Hence, by identifying node centralities, we can rank and interpret the relevance of each node for its special role in the life cycle network.     

Consistency of network modules in resting-state FMRI connectome data

At rest, spontaneous brain activity measured by fMRI is summarized by a number of distinct resting state networks (RSNs) following similar temporal time courses. Such networks have been consistently identified across subjects using spatial ICA (independent component analysis). Moreover, graph theory-based network analyses have also been applied to resting-state fMRI data, identifying similar RSNs, although typically at a coarser spatial resolution. In this work, we examined resting-state fMRI networks from 194 subjects at a voxel-level resolution, and examined the consistency of RSNs across subjects using a metric called scaled inclusivity (SI), which summarizes consistency of modular partitions across networks. Our SI analyses indicated that some RSNs are robust across subjects, comparable to the corresponding RSNs identified by ICA. We also found that some commonly reported RSNs are less consistent across subjects. This is the first direct comparison of RSNs between ICAs and graph-based network analyses at a comparable resolution.     

Incorporating Disease and Population Structure into Models of SIR Disease in Contact Networks

We consider the recently introduced edge-based compartmental models (EBCM) for the spread of susceptible-infected-recovered (SIR) diseases in networks. These models differ from standard infectious disease models by focusing on the status of a random partner in the population, rather than a random individual. This change in focus leads to simple analytic models for the spread of SIR diseases in random networks with heterogeneous degree. In this paper we extend this approach to handle deviations of the disease or population from the simplistic assumptions of earlier work. We allow the population to have structure due to effects such as demographic features or multiple types of risk behavior. We allow the disease to have more complicated natural history. Although we introduce these modifications in the static network context, it is straightforward to incorporate them into dynamic network models. We also consider serosorting, which requires using dynamic network models. The basic methods we use to derive these generalizations are widely applicable, and so it is straightforward to introduce many other generalizations not considered here. Our goal is twofold: to provide a number of examples generalizing the EBCM method for various different population or disease structures and to provide insight into how to derive such a model under new sets of assumptions.     

Linking Plant Specialization to Dependence in Interactions for Seed Set in Pollination Networks

Studies on pollination networks have provided valuable information on the number, frequency, distribution and identity of interactions between plants and pollinators. However, little is still known on the functional effect of these interactions on plant reproductive success. Information on the extent to which plants depend on such interactions will help to make more realistic predictions of the potential impacts of disturbances on plant-pollinator networks. Plant functional dependence on pollinators (all interactions pooled) can be estimated by comparing seed set with and without pollinators (i.e. bagging flowers to exclude them). Our main goal in this study was thus to determine whether plant dependence on current insect interactions is related to plant specialization in a pollination network. We studied two networks from different communities, one in a coastal dune and one in a mountain. For ca. 30% of plant species in each community, we obtained the following specialization measures: (i) linkage level (number of interactions), (ii) diversity of interactions, and (iii) closeness centrality (a measure of how much a species is connected to other plants via shared pollinators). Phylogenetically controlled regression analyses revealed that, for the largest and most diverse coastal community, plants highly dependent on pollinators were the most generalists showing the highest number and diversity of interactions as well as occupying central positions in the network. The mountain community, by contrast, did not show such functional relationship, what might be attributable to their lower flower-resource heterogeneity and diversity of interactions. We conclude that plants with a wide array of pollinator interactions tend to be those that are more strongly dependent upon them for seed production and thus might be those more functionally vulnerable to the loss of network interaction, although these outcomes might be context-dependent.     

Emergence,Evolution and Scaling of Online Social Networks

Online social networks have become increasingly ubiquitous and understanding their structural, dynamical, and scaling properties not only is of fundamental interest but also has a broad range of applications. Such networks can be extremely dynamic, generated almost instantaneously by, for example, breaking-news items. We investigate a common class of online social networks, the user-user retweeting networks, by analyzing the empirical data collected from Sina Weibo (a massive twitter-like microblogging social network in China) with respect to the topic of the 2011 Japan earthquake. We uncover a number of algebraic scaling relations governing the growth and structure of the network and develop a probabilistic model that captures the basic dynamical features of the system. The model is capable of reproducing all the empirical results. Our analysis not only reveals the basic mechanisms underlying the dynamics of the retweeting networks, but also provides general insights into the control of information spreading on such networks.     

Subnetwork hierarchies of biochemical pathways

MOTIVATION: The vastness and complexity of the biochemical networks that have been mapped out by modern genomics calls for decomposition into subnetworks. Such networks can have inherent non-local features that require the global structure to be taken into account in the decomposition procedure. Furthermore, basic questions such as to what extent the network (graph theoretically) can be said to be built by distinct subnetworks are little studied. RESULTS: We present a method to decompose biochemical networks into subnetworks based on the global geometry of the network. This method enables us to analyze the full hierarchical organization of biochemical networks and is applied to 43 organisms from the WIT database. Two types of biochemical networks are considered: metabolic networks and whole-cellular networks (also including for example information processes). Conceptual and quantitative ways of describing the hierarchical ordering are discussed. The general picture of the metabolic networks arising from our study is that of a few core-clusters centred around the most highly connected substances enclosed by other substances in outer shells, and a few other well-defined subnetworks. AVAILABILITY: An implementation of our algorithm and other programs for analyzing the data is available from http://www.tp.umu.se/forskning/networks/meta/ SUPPLEMENTARY INFORMATION: Supplementary material is available at http://www.tp.umu.se/forskning/networks/meta/     

Exploring biological network structure using exponential random graph models

MOTIVATION: The functioning of biological networks depends in large part on their complex underlying structure. When studying their systemic nature many modeling approaches focus on identifying simple, but prominent, structural components, as such components are easier to understand, and, once identified, can be used as building blocks to succinctly describe the network. RESULTS: In recent social network studies, exponential random graph models have been used extensively to model global social network structure as a function of their 'local features'. Starting from those studies, we describe the exponential random graph models and demonstrate their utility in modeling the architecture of biological networks as a function of the prominence of local features. We argue that the flexibility, in terms of the number of available local feature choices, and scalability, in terms of the network sizes, make this approach ideal for statistical modeling of biological networks. We illustrate the modeling on both genetic and metabolic networks and provide a novel way of classifying biological networks based on the prevalence of their local features.     

Normalization for probabilistic inference with neurons

Recently, there have been a number of proposals regarding how biologically plausible neural networks might perform probabilistic inference (Rao, Neural Computation, 16(1):1-38, 2004; Eliasmith and Anderson, Neural engineering: computation, representation and dynamics in neurobiological systems, 2003; Ma et?al., Nature Neuroscience, 9(11):1432-1438, 2006; Sahani and Dayan, Neural Computation, 15(10):2255-2279, 2003). To be able to repeatedly perform such inference, it is essential that the represented distributions be appropriately normalized. Past approaches have considered normalization mechanisms independently of inference, often leaving them unexplored, or appealing to a notion of divisive normalization that requires pooling across many neurons. Here, we demonstrate how normalization and inference can be combined into an appropriate connection matrix, eliminating the need for pooling or a division-like operation. We algebraically demonstrate that such a solution is available regardless of the inference being performed. We show that such a solution is relevant to neural computation by implementing it in a recurrent spiking neural network.     

Using indirect protein-protein interactions for protein complex prediction

Protein complexes are fundamental for understanding principles of cellular organizations. As the sizes of protein-protein interaction (PPI) networks are increasing, accurate and fast protein complex prediction from these PPI networks can serve as a guide for biological experiments to discover novel protein complexes. However, it is not easy to predict protein complexes from PPI networks, especially in situations where the PPI network is noisy and still incomplete. Here, we study the use of indirect interactions between level-2 neighbors (level-2 interactions) for protein complex prediction. We know from previous work that proteins which do not interact but share interaction partners (level-2 neighbors) often share biological functions. We have proposed a method in which all direct and indirect interactions are first weighted using topological weight (FS-Weight), which estimates the strength of functional association. Interactions with low weight are removed from the network, while level-2 interactions with high weight are introduced into the interaction network. Existing clustering algorithms can then be applied to this modified network. We have also proposed a novel algorithm that searches for cliques in the modified network, and merge cliques to form clusters using a "partial clique merging" method. Experiments show that (1) the use of indirect interactions and topological weight to augment protein-protein interactions can be used to improve the precision of clusters predicted by various existing clustering algorithms; and (2) our complex-finding algorithm performs very well on interaction networks modified in this way. Since no other information except the original PPI network is used, our approach would be very useful for protein complex prediction, especially for prediction of novel protein complexes.