Selective integration of multiple biological data for supervised network inference

MOTIVATION: Inferring networks of proteins from biological data is a central issue of computational biology. Most network inference methods, including Bayesian networks, take unsupervised approaches in which the network is totally unknown in the beginning, and all the edges have to be predicted. A more realistic supervised framework, proposed recently, assumes that a substantial part of the network is known. We propose a new kernel-based method for supervised graph inference based on multiple types of biological datasets such as gene expression, phylogenetic profiles and amino acid sequences. Notably, our method assigns a weight to each type of dataset and thereby selects informative ones. Data selection is useful for reducing data collection costs. For example, when a similar network inference problem must be solved for other organisms, the dataset excluded by our algorithm need not be collected. RESULTS: First, we formulate supervised network inference as a kernel matrix completion problem, where the inference of edges boils down to estimation of missing entries of a kernel matrix. Then, an expectation-maximization algorithm is proposed to simultaneously infer the missing entries of the kernel matrix and the weights of multiple datasets. By introducing the weights, we can integrate multiple datasets selectively and thereby exclude irrelevant and noisy datasets. Our approach is favorably tested in two biological networks: a metabolic network and a protein interaction network. AVAILABILITY: Software is available on request.     

杂谷脑河流域河网统计自相似性

河网自相似性是水文尺度研究的重要方向,统计自相似研究不同尺度下河网参数概率分布函数的相似性.从统计自相似的角度,推导出河网参数、全河网分布和单级河道分布的关系,并用杂谷脑河DEM进行验证;对所得数据进行Kolmogorov Smirnov双样本检验,结果显示,推导结论与实际数据吻合,说明整个河网和单级河道之间是复杂的层叠关系,而不是简单的比例关系.     

Integrative network biology: graph prototyping for co-expression cancer networks

Network-based analysis has been proven useful in biologically-oriented areas, e.g., to explore the dynamics and complexity of biological networks. Investigating a set of networks allows deriving general knowledge about the underlying topological and functional properties. The integrative analysis of networks typically combines networks from different studies that investigate the same or similar research questions. In order to perform an integrative analysis it is often necessary to compare the properties of matching edges across the data set. This identification of common edges is often burdensome and computational intensive. Here, we present an approach that is different from inferring a new network based on common features. Instead, we select one network as a graph prototype, which then represents a set of comparable network objects, as it has the least average distance to all other networks in the same set. We demonstrate the usefulness of the graph prototyping approach on a set of prostate cancer networks and a set of corresponding benign networks. We further show that the distances within the cancer group and the benign group are statistically different depending on the utilized distance measure.     

Clustering under the line graph transformation: application to reaction network

Background  

Many real networks can be understood as two complementary networks with two kind of nodes. This is the case of metabolic networks where the first network has chemical compounds as nodes and the second one has nodes as reactions. In general, the second network may be related to the first one by a technique called line graph transformation (i.e., edges in an initial network are transformed into nodes). Recently, the main topological properties of the metabolic networks have been properly described by means of a hierarchical model. While the chemical compound network has been classified as hierarchical network, a detailed study of the chemical reaction network had not been carried out.     

Quantifying loopy network architectures

Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.     

RRW: repeated random walks on genome-scale protein networks for local cluster discovery

Background  

We propose an efficient and biologically sensitive algorithm based on repeated random walks (RRW) for discovering functional modules, e.g., complexes and pathways, within large-scale protein networks. Compared to existing cluster identification techniques, RRW implicitly makes use of network topology, edge weights, and long range interactions between proteins.     

Edge vulnerability in neural and metabolic networks

Biological networks, such as cellular metabolic pathways or networks of corticocortical connections in the brain, are intricately organized, yet remarkably robust toward structural damage. Whereas many studies have investigated specific aspects of robustness, such as molecular mechanisms of repair, this article focuses more generally on how local structural features in networks may give rise to their global stability. In many networks the failure of single connections may be more likely than the extinction of entire nodes, yet no analysis of edge importance (edge vulnerability) has been provided so far for biological networks. We tested several measures for identifying vulnerable edges and compared their prediction performance in biological and artificial networks. Among the tested measures, edge frequency in all shortest paths of a network yielded a particularly high correlation with vulnerability and identified intercluster connections in biological but not in random and scale-free benchmark networks. We discuss different local and global network patterns and the edge vulnerability resulting from them.     

Ranking Competitors Using Degree-Neutralized Random Walks

Competition is ubiquitous in many complex biological, social, and technological systems, playing an integral role in the evolutionary dynamics of the systems. It is often useful to determine the dominance hierarchy or the rankings of the components of the system that compete for survival and success based on the outcomes of the competitions between them. Here we propose a ranking method based on the random walk on the network representing the competitors as nodes and competitions as directed edges with asymmetric weights. We use the edge weights and node degrees to define the gradient on each edge that guides the random walker towards the weaker (or the stronger) node, which enables us to interpret the steady-state occupancy as the measure of the node''s weakness (or strength) that is free of unwarranted degree-induced bias. We apply our method to two real-world competition networks and explore the issues of ranking stabilization and prediction accuracy, finding that our method outperforms other methods including the baseline win–loss differential method in sparse networks.     

Edge Principal Components and Squash Clustering: Using the Special Structure of Phylogenetic Placement Data for Sample Comparison

Principal components analysis (PCA) and hierarchical clustering are two of the most heavily used techniques for analyzing the differences between nucleic acid sequence samples taken from a given environment. They have led to many insights regarding the structure of microbial communities. We have developed two new complementary methods that leverage how this microbial community data sits on a phylogenetic tree. Edge principal components analysis enables the detection of important differences between samples that contain closely related taxa. Each principal component axis is a collection of signed weights on the edges of the phylogenetic tree, and these weights are easily visualized by a suitable thickening and coloring of the edges. Squash clustering outputs a (rooted) clustering tree in which each internal node corresponds to an appropriate “average” of the original samples at the leaves below the node. Moreover, the length of an edge is a suitably defined distance between the averaged samples associated with the two incident nodes, rather than the less interpretable average of distances produced by UPGMA, the most widely used hierarchical clustering method in this context. We present these methods and illustrate their use with data from the human microbiome.     

Hub-centered gene network reconstruction using automatic relevance determination

Network inference deals with the reconstruction of biological networks from experimental data. A variety of different reverse engineering techniques are available; they differ in the underlying assumptions and mathematical models used. One common problem for all approaches stems from the complexity of the task, due to the combinatorial explosion of different network topologies for increasing network size. To handle this problem, constraints are frequently used, for example on the node degree, number of edges, or constraints on regulation functions between network components. We propose to exploit topological considerations in the inference of gene regulatory networks. Such systems are often controlled by a small number of hub genes, while most other genes have only limited influence on the network's dynamic. We model gene regulation using a Bayesian network with discrete, Boolean nodes. A hierarchical prior is employed to identify hub genes. The first layer of the prior is used to regularize weights on edges emanating from one specific node. A second prior on hyperparameters controls the magnitude of the former regularization for different nodes. The net effect is that central nodes tend to form in reconstructed networks. Network reconstruction is then performed by maximization of or sampling from the posterior distribution. We evaluate our approach on simulated and real experimental data, indicating that we can reconstruct main regulatory interactions from the data. We furthermore compare our approach to other state-of-the art methods, showing superior performance in identifying hubs. Using a large publicly available dataset of over 800 cell cycle regulated genes, we are able to identify several main hub genes. Our method may thus provide a valuable tool to identify interesting candidate genes for further study. Furthermore, the approach presented may stimulate further developments in regularization methods for network reconstruction from data.     

The Shapley value of phylogenetic trees

Every weighted tree corresponds naturally to a cooperative game that we call a tree game; it assigns to each subset of leaves the sum of the weights of the minimal subtree spanned by those leaves. In the context of phylogenetic trees, the leaves are species and this assignment captures the diversity present in the coalition of species considered. We consider the Shapley value of tree games and suggest a biological interpretation. We determine the linear transformation M that shows the dependence of the Shapley value on the edge weights of the tree, and we also compute a null space basis of M. Both depend on the split counts of the tree. Finally, we characterize the Shapley value on tree games by four axioms, a counterpart to Shapley’s original theorem on the larger class of cooperative games. We also include a brief discussion of the core of tree games. Research of Francis Edward Su was partially supported by NSF Grants DMS-0301129 and DMS-0701308.     

Ongoing Processes in a Fitness Network Model under Restricted Resources

In real networks, the resources that make up the nodes and edges are finite. This constraint poses a serious problem for network modeling, namely, the compatibility between robustness and efficiency. However, these concepts are generally in conflict with each other. In this study, we propose a new fitness-driven network model for finite resources. In our model, each individual has its own fitness, which it tries to increase. The main assumption in fitness-driven networks is that incomplete estimation of fitness results in a dynamical growing network. By taking into account these internal dynamics, nodes and edges emerge as a result of exchanges between finite resources. We show that our network model exhibits exponential distributions in the in- and out-degree distributions and a power law distribution of edge weights. Furthermore, our network model resolves the trade-off relationship between robustness and efficiency. Our result suggests that growing and anti-growing networks are the result of resolving the trade-off problem itself.     

Recurrent fractal neural networks: a strategy for the exchange of local and global information processing in the brain

The regulation of biological networks relies significantly on convergent feedback signaling loops that render a global output locally accessible. Ideally, the recurrent connectivity within these systems is self-organized by a time-dependent phase-locking mechanism. This study analyzes recurrent fractal neural networks (RFNNs), which utilize a self-similar or fractal branching structure of dendrites and downstream networks for phase-locking of reciprocal feedback loops: output from outer branch nodes of the network tree enters inner branch nodes of the dendritic tree in single neurons. This structural organization enables RFNNs to amplify re-entrant input by over-the-threshold signal summation from feedback loops with equivalent signal traveling times. The columnar organization of pyramidal neurons in the neocortical layers V and III is discussed as the structural substrate for this network architecture. RFNNs self-organize spike trains and render the entire neural network output accessible to the dendritic tree of each neuron within this network. As the result of a contraction mapping operation, the local dendritic input pattern contains a downscaled version of the network output coding structure. RFNNs perform robust, fractal data compression, thus coping with a limited number of feedback loops for signal transport in convergent neural networks. This property is discussed as a significant step toward the solution of a fundamental problem in neuroscience: how is neuronal computation in separate neurons and remote brain areas unified as an instance of experience in consciousness? RFNNs are promising candidates for engaging neural networks into a coherent activity and provide a strategy for the exchange of global and local information processing in the human brain, thereby ensuring the completeness of a transformation from neuronal computation into conscious experience.     

MTMO: an efficient network-centric algorithm for subtree counting and enumeration

Background: The frequency of small subtrees in biological, social, and other types of networks could shed light into the structure, function, and evolution of such networks. However, counting all possible subtrees of a prescribed size can be computationally expensive because of their potentially large number even in small, sparse networks. Moreover, most of the existing algorithms for subtree counting belong to the subtree-centric approaches, which search for a specific single subtree type at a time, potentially taking more time by searching again on the same network. Methods: In this paper, we propose a network-centric algorithm (MTMO) to efficiently count k-size subtrees. Our algorithm is based on the enumeration of all connected sets of k–1 edges, incorporates a labeled rooted tree data structure in the enumeration process to reduce the number of isomorphism tests required, and uses an array-based indexing scheme to simplify the subtree counting method. Results: The experiments on three representative undirected complex networks show that our algorithm is roughly an order of magnitude faster than existing subtree-centric approaches and base network-centric algorithm which does not use rooted tree, allowing for counting larger subtrees in larger networks than previously possible. We also show major differences between unicellular and multicellular organisms. In addition, our algorithm is applied to find network motifs based on pattern growth approach. Conclusions: A network-centric algorithm which allows for a faster counting of non-induced subtrees is proposed. This enables us to count larger motif in larger networks than previously.     

Network analysis of dendritic fields of pyramidal cells in neocortex and Purkinje cells in the cerebellum of the rat.

The connectivity within the dendritic array of Purkinje cells in the cerebellum and pyramidal cells of the neocortex of the rat, stained by the Golgi-Cox method, has been quantified by the method of network analysis. Connectivity was characterized either by applying the system of Strahler ordering, which assigns a relative order of magnitude to each branch of the arborescence or by the identification of unique topological branching patterns within the tree. The former method has been used to define the entire dendritic array of the Purkinje cell and the apical system of neocortical pyramids. It has been shown that the relation between the numbers of branches of successive Strahler order in Purkinje cells form an inverse geometric series in which the highest order is unity and the ratio between successive orders approximates to 3. On the other hand, the apical dendrites of neocortical pyramids exhibit two bifurcation ratios, i.e. a ratio of 3 between low orders and a ratio of 4 between higher orders. A computer simulation technique was used to generate networks of a size comparable with the Purkinje cell networks and grown according to two hypotheses namely, a 'terminal growth model' in which additional segments were added randomly to the terminal branches only and a 'segmental growth model' in which additional segments were added randomly to any branch within the array including terminal branches. Subsequent ordering of the simulated trees revealed that the relation between the numbers of successive orders for networks generated according to the 'segmental model' tended towards an inverse geometric series with a ratio of 4 and that generated according to the 'terminal model' tended towards a ratio of 3. This result showed that the dendritic tree of Purkinje cells grow in a manner indistinguishable from a system adding branches to random terminal segments and that neocortical apical dendrites add their collateral branches to random segments of the apical shaft but that the collateral branches themselves grow by random terminal branching. The possibility that such conclusions may be influenced by loss of branches incurred by either a failure of impregnation, by sectioning, or by environmental influences was investigated by means of a computer technique...     

The Role of Community Mixing Styles in Shaping Epidemic Behaviors in Weighted Networks

The dynamics of infectious diseases that are spread through direct contact have been proven to depend on the strength of community structure or modularity within the underlying network. It has been recently shown that weighted networks with similar modularity values may exhibit different mixing styles regarding the number of connections among communities and their respective weights. However, the effect of mixing style on epidemic behavior was still unclear. In this paper, we simulate the spread of disease within networks with different mixing styles: a dense-weak style (i.e., many edges among the communities with small weights) and a sparse-strong style (i.e., a few edges among the communities with large weights). Simulation results show that, with the same modularity: 1) the mixing style significantly influences the epidemic size, speed, pattern and immunization strategy; 2) the increase of the number of communities amplifies the effect of the mixing style; 3) when the mixing style changes from sparse-strong to dense-weak, there is a ‘saturation point’, after which the epidemic size and pattern become stable. We also provide a mean-field solution of the epidemic threshold and size on weighted community networks with arbitrary external and internal degree distribution. The solution explains the effect of the second moment of the degree distribution, and a symmetric effect of internal and external connections (incl. degree distribution and weight). Our study has both potential significance for designing more accurate metrics for the community structure and exploring diffusion dynamics on metapopulation networks.     

Combinatorial properties of RNA secondary structures.

The secondary structure of an RNA molecule is of great importance and possesses influence, e.g., on the interaction of tRNA molecules with proteins or on the stabilization of mRNA molecules. The classification of secondary structures by means of their order proved useful with respect to numerous applications. In 1978, Waterman, who gave the first precise formal framework for the topic, suggested to determine the number a(n,p) of secondary structures of size n and given order p. Since then, no satisfactory result has been found. Based on an observation due to Viennot et al., we will derive generating functions for the secondary structures of order p from generating functions for binary tree structures with Horton-Strahler number p. These generating functions enable us to compute a precise asymptotic equivalent for a(n,p). Furthermore, we will determine the related number of structures when the number of unpaired bases shows up as an additional parameter. Our approach proves to be general enough to compute the average order of a secondary structure together with all the r-th moments and to enumerate substructures such as hairpins or bulges in dependence on the order of the secondary structures considered.     

Hierarchy measure for complex networks

Nature, technology and society are full of complexity arising from the intricate web of the interactions among the units of the related systems (e.g., proteins, computers, people). Consequently, one of the most successful recent approaches to capturing the fundamental features of the structure and dynamics of complex systems has been the investigation of the networks associated with the above units (nodes) together with their relations (edges). Most complex systems have an inherently hierarchical organization and, correspondingly, the networks behind them also exhibit hierarchical features. Indeed, several papers have been devoted to describing this essential aspect of networks, however, without resulting in a widely accepted, converging concept concerning the quantitative characterization of the level of their hierarchy. Here we develop an approach and propose a quantity (measure) which is simple enough to be widely applicable, reveals a number of universal features of the organization of real-world networks and, as we demonstrate, is capable of capturing the essential features of the structure and the degree of hierarchy in a complex network. The measure we introduce is based on a generalization of the m-reach centrality, which we first extend to directed/partially directed graphs. Then, we define the global reaching centrality (GRC), which is the difference between the maximum and the average value of the generalized reach centralities over the network. We investigate the behavior of the GRC considering both a synthetic model with an adjustable level of hierarchy and real networks. Results for real networks show that our hierarchy measure is related to the controllability of the given system. We also propose a visualization procedure for large complex networks that can be used to obtain an overall qualitative picture about the nature of their hierarchical structure.