Combinatorial complexity of pathway analysis in metabolic networks

Elementary flux mode analysis is a promising approach for a pathway-oriented perspective of metabolic networks. However, in larger networks it is hampered by the combinatorial explosion of possible routes. In this work we give some estimations on the combinatorial complexity including theoretical upper bounds for the number of elementary flux modes in a network of a given size. In a case study, we computed the elementary modes in the central metabolism of Escherichia coli while utilizing four different substrates. Interestingly, although the number of modes occurring in this complex network can exceed half a million, it is still far below the upper bound. Hence, to a certain extent, pathway analysis of central catabolism is feasible to assess network properties such as flexibility and functionality.     

Trade-off between Multiple Constraints Enables Simultaneous Formation of Modules and Hubs in Neural Systems

The formation of the complex network architecture of neural systems is subject to multiple structural and functional constraints. Two obvious but apparently contradictory constraints are low wiring cost and high processing efficiency, characterized by short overall wiring length and a small average number of processing steps, respectively. Growing evidence shows that neural networks are results from a trade-off between physical cost and functional value of the topology. However, the relationship between these competing constraints and complex topology is not well understood quantitatively. We explored this relationship systematically by reconstructing two known neural networks, Macaque cortical connectivity and C. elegans neuronal connections, from combinatory optimization of wiring cost and processing efficiency constraints, using a control parameter , and comparing the reconstructed networks to the real networks. We found that in both neural systems, the reconstructed networks derived from the two constraints can reveal some important relations between the spatial layout of nodes and the topological connectivity, and match several properties of the real networks. The reconstructed and real networks had a similar modular organization in a broad range of , resulting from spatial clustering of network nodes. Hubs emerged due to the competition of the two constraints, and their positions were close to, and partly coincided, with the real hubs in a range of values. The degree of nodes was correlated with the density of nodes in their spatial neighborhood in both reconstructed and real networks. Generally, the rebuilt network matched a significant portion of real links, especially short-distant ones. These findings provide clear evidence to support the hypothesis of trade-off between multiple constraints on brain networks. The two constraints of wiring cost and processing efficiency, however, cannot explain all salient features in the real networks. The discrepancy suggests that there are further relevant factors that are not yet captured here.     

Modelling gene networks at different organisational levels

Approaches to modelling gene regulation networks can be categorized, according to increasing detail, as network parts lists, network topology models, network control logic models, or dynamic models. We discuss the current state of the art for each of these approaches. There is a gap between the parts list and topology models on one hand, and control logic and dynamic models on the other hand. The first two classes of models have reached a genome-wide scale, while for the other model classes high throughput technologies are yet to make a major impact.     

Tree-average distances on certain phylogenetic networks have their weights uniquely determined

ABSTRACT: A phylogenetic network N has vertices corresponding to species and arcs corresponding to direct genetic inheritance from the species at the tail to the species at the head. Measurements of DNA are often made on species in the leaf set, and one seeks to infer properties of the network, possibly including the graph itself. In the case of phylogenetic trees, distances between extant species are frequently used to infer the phylogenetic trees by methods such as neighbor-joining. This paper proposes a "tree-average" distance for networks more general than trees. The notion requires a "weight" on each arc measuring the genetic change along the arc. For each displayed tree the distance between two leaves is the sum of the weights along the path joining them. At a hybrid vertex, each character is inherited from one of its parents. We will assume that for each hybrid there is a probability that the inheritance of a character is from a specified parent. Assume that the inheritance events at different hybrids are independent. Then for each displayed tree there will be a probability that the inheritance of a given character follows the tree; this probability may be interpreted as the probability of the tree. The "tree-average" distance between the leaves is defined to be the expected value of their distance in the displayed trees. For a class of rooted networks that includes rooted trees, it is shown that the weights and the probabilities at each hybrid vertex can be calculated given the network and the tree-average distances between the leaves. Hence these weights and probabilities are uniquely determined. The hypotheses on the networks include that hybrid vertices have indegree exactly 2 and that vertices that are not leaves have a tree-child.     

Flower‐visitor networks only partially predict the function of pollen transport by bees

Mutualistic networks display distinct structural and organizational features such as nestedness, power‐law degree distribution and asymmetric dependencies. Attention is now focused on how these structural properties influence network function. Most plant‐pollinator networks are constructed using records of animals contacting flowers, which is based on the assumption that all visitors to flowers are pollinators; however, animals may visit flowers as nectar robbers, florivores, or to prey upon other visitors. To differentiate potential pollinator interactions from other interaction types, we examined individual bees that had visited flowers to detect if they carried pollen. Using these data, we constructed visitation and pollen‐transport networks for a spinifex‐dominated arid zone grassland. To determine how the structure of the visitation network reflects pollen transport, we compared the two networks using a null model approach to account for differences in network size. Differences in number of species, nestedness and connectance observed between the visitation and pollen‐transport networks were within expected ranges generated under the null model. The pollen‐transport network was more specialized, had lower interaction evenness, and fewer links compared to the visitation network. Almost half the number of species of the visitation network participated in the pollen‐transport network, and one‐third of unique visitation interactions resulted in pollen transport, highlighting that visitation does not always result in pollination. Floral visitor data indicate potential pollen transporters, but inferring pollination function from visitation networks needs to be performed cautiously as pollen transport resulted from both common and rare interactions, and depended on visitor identity. Although visitation and pollen‐transport networks are structurally similar, the function of all species cannot be predicted from the visitation network alone. Considering pollen transport in visitation networks is a simple first step towards determining pollinators from non‐pollinators. This is fundamental for understanding how network structure relates to network function.     

Analyzing molecular reaction networks

Pathways are typically the central concept in the analysis of biochemical reaction networks. A pathway can be interpreted as a chain of enzymatical reactions performing a specific biological function. A common way to study metabolic networks are minimal pathways that can operate at steady state called elementary modes. The theory of chemical organizations has recently been used to decompose biochemical networks into algebraically closed and self-maintaining subnetworks termed organizations. The aim of this paper is to elucidate the relation between these two concepts. Whereas elementary modes represent the boundaries of the potential behavior of the network, organizations define metabolite compositions that are likely to be present in biological feasible situations. Hence, steady state organizations consist of combinations of elementary modes. On the other hand, it is possible to assign a unique (and possibly empty) set of organizations to each elementary mode, indicating the metabolites accompanying the active pathway in a feasible steady state.     

Network Analysis Tools: from biological networks to clusters and pathways

Network Analysis Tools (NeAT) is a suite of computer tools that integrate various algorithms for the analysis of biological networks: comparison between graphs, between clusters, or between graphs and clusters; network randomization; analysis of degree distribution; network-based clustering and path finding. The tools are interconnected to enable a stepwise analysis of the network through a complete analytical workflow. In this protocol, we present a typical case of utilization, where the tasks above are combined to decipher a protein-protein interaction network retrieved from the STRING database. The results returned by NeAT are typically subnetworks, networks enriched with additional information (i.e., clusters or paths) or tables displaying statistics. Typical networks comprising several thousands of nodes and arcs can be analyzed within a few minutes. The complete protocol can be read and executed in approximately 1 h.     

Tree-based networks: characterisations,metrics, and support trees

Phylogenetic networks generalise phylogenetic trees and allow for the accurate representation of the evolutionary history of a set of present-day species whose past includes reticulate events such as hybridisation and lateral gene transfer. One way to obtain such a network is by starting with a (rooted) phylogenetic tree T, called a base tree, and adding arcs between arcs of T. The class of phylogenetic networks that can be obtained in this way is called tree-based networks and includes the prominent classes of tree-child and reticulation-visible networks. Initially defined for binary phylogenetic networks, tree-based networks naturally extend to arbitrary phylogenetic networks. In this paper, we generalise recent tree-based characterisations and associated proximity measures for binary phylogenetic networks to arbitrary phylogenetic networks. These characterisations are in terms of matchings in bipartite graphs, path partitions, and antichains. Some of the generalisations are straightforward to establish using the original approach, while others require a very different approach. Furthermore, for an arbitrary tree-based network N, we characterise the support trees of N, that is, the tree-based embeddings of N. We use this characterisation to give an explicit formula for the number of support trees of N when N is binary. This formula is written in terms of the components of a bipartite graph.

     

Robustness and information propagation in attractors of random boolean networks

Attractors represent the long-term behaviors of Random Boolean Networks. We study how the amount of information propagated between the nodes when on an attractor, as quantified by the average pairwise mutual information ([Formula: see text]), relates to the robustness of the attractor to perturbations ([Formula: see text]). We find that the dynamical regime of the network affects the relationship between [Formula: see text] and [Formula: see text]. In the ordered and chaotic regimes, [Formula: see text] is anti-correlated with [Formula: see text], implying that attractors that are highly robust to perturbations have necessarily limited information propagation. Between order and chaos (for so-called "critical" networks) these quantities are uncorrelated. Finite size effects cause this behavior to be visible for a range of networks, from having a sensitivity of 1 to the point where [Formula: see text] is maximized. In this region, the two quantities are weakly correlated and attractors can be almost arbitrarily robust to perturbations without restricting the propagation of information in the network.     

Community Structure and Multi-Modal Oscillations in Complex Networks

In many types of network, the relationship between structure and function is of great significance. We are particularly interested in community structures, which arise in a wide variety of domains. We apply a simple oscillator model to networks with community structures and show that waves of regular oscillation are caused by synchronised clusters of nodes. Moreover, we show that such global oscillations may arise as a direct result of network topology. We also observe that additional modes of oscillation (as detected through frequency analysis) occur in networks with additional levels of topological hierarchy and that such modes may be directly related to network structure. We apply the method in two specific domains (metabolic networks and metropolitan transport) demonstrating the robustness of our results when applied to real world systems. We conclude that (where the distribution of oscillator frequencies and the interactions between them are known to be unimodal) our observations may be applicable to the detection of underlying community structure in networks, shedding further light on the general relationship between structure and function in complex systems.     

Motifs in brain networks

Complex brains have evolved a highly efficient network architecture whose structural connectivity is capable of generating a large repertoire of functional states. We detect characteristic network building blocks (structural and functional motifs) in neuroanatomical data sets and identify a small set of structural motifs that occur in significantly increased numbers. Our analysis suggests the hypothesis that brain networks maximize both the number and the diversity of functional motifs, while the repertoire of structural motifs remains small. Using functional motif number as a cost function in an optimization algorithm, we obtain network topologies that resemble real brain networks across a broad spectrum of structural measures, including small-world attributes. These results are consistent with the hypothesis that highly evolved neural architectures are organized to maximize functional repertoires and to support highly efficient integration of information.     

Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium

Traffic optimization of railroad networks was considered using an algorithm that was biologically inspired by an amoeba-like organism, plasmodium of the true slime mold, Physarum polycephalum. The organism developed a transportation network consisting of a tubular structure to transport protoplasm. It was reported that plasmodium can find the shortest path interconnecting multiple food sites during an adaptation process (Nakagaki et al., 2001. Biophys. Chem. 92, 47-52). By mimicking the adaptation process a path finding algorithm was developed by Tero et al. (2007). In this paper, the algorithm is newly modified for applications of traffic distribution optimization in transportation networks of infrastructure such as railroads under the constraint that the network topology is given. Application of the algorithm to a railroad in metropolitan Tokyo, Japan is demonstrated. The results are evaluated using three performance functions related to cost, traveling efficiency, and network weakness. The traffic distribution suggests that the modified Physarum algorithm balances the performances under a certain parameter range, indicating a biological process.     

Investigating the properties of bio-chemical networks of artificial organisms with opposing behaviours

Organisms, be it singled-celled organisms or multi-cellular organisms, are constantly faced with opposing objectives requiring different sets of behaviours. These behaviours can be classified into two, predatory behaviours or anti-prey behaviours, with one set of behaviours causing an opposite effect to the other. A healthy organism aims to achieve its equilibrium state or to be in homeostasis. Homeostasis is achieved when a balance between the two opposing behaviours is created and maintained. This raises some questions: is there an innate mechanism that encodes for these categories of behaviours? Is there also an innate mechanism(s) that resolves conflicts and allows switching between these two opposing behaviours? If we consider artificial organisms as single-celled organisms, how do the organisms’ gene regulatory network, metabolic network and/or signalling network (their biochemical networks) maintain homeostasis of the organisms? This paper investigates the properties of the networks of best evolved artificial organisms, in order to help answer these questions, and guide the evolutionary development of controllers for artificial systems.     

Tension and robustness in multitasking cellular networks

Cellular networks multitask by exhibiting distinct, context-dependent dynamics. However, network states (parameters) that generate a particular dynamic are often sub-optimal for others, defining a source of "tension" between them. Though multitasking is pervasive, it is not clear where tension arises, what consequences it has, and how it is resolved. We developed a generic computational framework to examine the source and consequences of tension between pairs of dynamics exhibited by the well-studied RB-E2F switch regulating cell cycle entry. We found that tension arose from task-dependent shifts in parameters associated with network modules. Although parameter sets common to distinct dynamics did exist, tension reduced both their accessibility and resilience to perturbation, indicating a trade-off between "one-size-fits-all" solutions and robustness. With high tension, robustness can be preserved by dynamic shifting of modules, enabling the network to toggle between tasks, and by increasing network complexity, in this case by gene duplication. We propose that tension is a general constraint on the architecture and operation of multitasking biological networks. To this end, our work provides a framework to quantify the extent of tension between any network dynamics and how it affects network robustness. Such analysis would suggest new ways to interfere with network elements to elucidate the design principles of cellular networks.     

A novel approach for assessing factors affecting biodiversity based on networks analysis

We propose in this work a novel approach aiming at assessing cause and effect relationships between variables that can affect target biodiversity issues. These cause–effect relations are used to build a network whose nodes represent variables linked by directed arcs. The arcs have associated a value that represents trends of cause–effect relations. An important novelty of this approach is the use of product and addition operations between trends of cause–effect relations for assessing factors that can affect target variables. For the analysis of the network we use the concept of paths. Paths are defined as sequences of cause–effect relations from source variables to target variables. For example, the path from population increment that causes effects on the increment of transport routes, which in turn causes effects on the loss of vegetation cover. This approach was applied to the assessment of vegetation cover in the Morelos State, México during the period 2000–2010. The results show a promising practical alternative to assess the potential effects on biodiversity issues based on the analysis of the paths represented in the network.     

Counting motifs in dynamic networks

Background

A network motif is a sub-network that occurs frequently in a given network. Detection of such motifs is important since they uncover functions and local properties of the given biological network. Finding motifs is however a computationally challenging task as it requires solving the costly subgraph isomorphism problem. Moreover, the topology of biological networks change over time. These changing networks are called dynamic biological networks. As the network evolves, frequency of each motif in the network also changes. Computing the frequency of a given motif from scratch in a dynamic network as the network topology evolves is infeasible, particularly for large and fast evolving networks.

Results

In this article, we design and develop a scalable method for counting the number of motifs in a dynamic biological network. Our method incrementally updates the frequency of each motif as the underlying network’s topology evolves. Our experiments demonstrate that our method can update the frequency of each motif in orders of magnitude faster than counting the motif embeddings every time the network changes. If the network evolves more frequently, the margin with which our method outperforms the existing static methods, increases.

Conclusions

We evaluated our method extensively using synthetic and real datasets, and show that our method is highly accurate(≥?96%) and that it can be scaled to large dense networks. The results on real data demonstrate the utility of our method in revealing interesting insights on the evolution of biological processes.