RNA Graph Partitioning for the Discovery of RNA Modularity: A Novel Application of Graph Partition Algorithm to Biology

Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG) framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2) corresponding to the second eigenvalues (λ2) associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2′s components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2′s components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼220 nucleotides). While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs also suggest design strategies for novel RNA motifs.     

Functional network organization of the human brain

Real-world complex systems may be mathematically modeled as graphs, revealing properties of the system. Here we study graphs of functional brain organization in healthy adults using resting state functional connectivity MRI. We propose two novel brain-wide graphs, one of 264 putative functional areas, the other a modification of voxelwise networks that eliminates potentially artificial short-distance relationships. These graphs contain many subgraphs in good agreement with known functional brain systems. Other subgraphs lack established functional identities; we suggest possible functional characteristics for these subgraphs. Further, graph measures of the areal network indicate that the default mode subgraph shares network properties with sensory and motor subgraphs: it is internally integrated but isolated from other subgraphs, much like a "processing" system. The modified voxelwise graph also reveals spatial motifs in the patterning of systems across the cortex.     

Biomolecular network motif counting and discovery by color coding

Protein-protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k < or = 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k > or = 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the 'color coding' technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G' with k vertices in a network G with n vertices in time polynomial with n, provided k = O(log n). We use our algorithm to obtain 'treelet' distributions for k < or = 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the 'duplication model' but are quite different from that of the 'preferential attachment model'. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%.     

Unique Determination of Some Homoplasies at Hybridization Events

Phylogenetic relationships may be represented by rooted acyclic directed graphs in which each vertex, corresponding to a taxon, possesses a genome. Assume the characters are all binary. A homoplasy occurs if a particular character changes its state more than once in the graph. A vertex is “regular” if it has only one parent and “hybrid” if it has more than one parent. A “regular path” is a directed path such that all vertices after the first are regular. Assume that the network is given and that the genomes are known for all leaves and for the root. Assume that all homoplasies occur only at hybrid vertices and each character has at most one homoplasy. Assume that from each vertex there is a regular path leading to a leaf. In this idealized setting, with other mild assumptions, it is proved that the genome at each vertex is uniquely determined. Hence, for each character the vertex at which a homoplasy occurs in the character is uniquely determined. Without the assumption on regular paths, an example shows that the genomes and homoplasies need not be uniquely determined.     

Model for Heterogeneous Random Networks Using Continuous Latent Variables and an Application to a Tree–Fungus Network

Summary The mixture model is a method of choice for modeling heterogeneous random graphs, because it contains most of the known structures of heterogeneity: hubs, hierarchical structures, or community structure. One of the weaknesses of mixture models on random graphs is that, at the present time, there is no computationally feasible estimation method that is completely satisfying from a theoretical point of view. Moreover, mixture models assume that each vertex pertains to one group, so there is no place for vertices being at intermediate positions. The model proposed in this article is a grade of membership model for heterogeneous random graphs, which assumes that each vertex is a mixture of extremal hypothetical vertices. The connectivity properties of each vertex are deduced from those of the extreme vertices. In this new model, the vector of weights of each vertex are fixed continuous parameters. A model with a vector of parameters for each vertex is tractable because the number of observations is proportional to the square of the number of vertices of the network. The estimation of the parameters is given by the maximum likelihood procedure. The model is used to elucidate some of the processes shaping the heterogeneous structure of a well‐resolved network of host/parasite interactions.     

SING: Subgraph search In Non-homogeneous Graphs

Background  

Finding the subgraphs of a graph database that are isomorphic to a given query graph has practical applications in several fields, from cheminformatics to image understanding. Since subgraph isomorphism is a computationally hard problem, indexing techniques have been intensively exploited to speed up the process. Such systems filter out those graphs which cannot contain the query, and apply a subgraph isomorphism algorithm to each residual candidate graph. The applicability of such systems is limited to databases of small graphs, because their filtering power degrades on large graphs.     

Applications of neural networks to colour recognition

Colour specification and matching are important tasks used in a number of different industries. However, current methods can employ very complicated, elaborate pieces of laboratory equipment which are not portable, such as spectrophotometers with combinations of calibrated light sources and a large number of narrow band filters. Simpler, portable devices are typically not sophisticated enough to give a high degree of quality control due to the less sophisticated light sources and the necessarily smaller number of filters employed. Lastly, techniques such as the `match by eye' method can lead to deceptive metameric matches. This paper outlines the beginning of the development of a colour measurement system which is portable, easy to use, and more accurate than other portable devices by virtue of an artificial neural network used to analyze the data. With specialized training of the neural network, it could even be used in applications such as teeth and skin colour measurements. Received: 6 November 1996 / Accepted in revised form: 13 July 1998     

Principal Networks

Graph representations of brain connectivity have attracted a lot of recent interest, but existing methods for dividing such graphs into connected subnetworks have a number of limitations in the context of neuroimaging. This is an important problem because most cognitive functions would be expected to involve some but not all brain regions. In this paper we outline a simple approach for decomposing graphs, which may be based on any measure of interregional association, into coherent “principal networks”. The technique is based on an eigendecomposition of the association matrix, and is closely related to principal components analysis. We demonstrate the technique using cortical thickness and diffusion tractography data, showing that the subnetworks which emerge are stable, meaningful and reproducible. Graph-theoretic measures of network cost and efficiency may be calculated separately for each principal network. Unlike some other approaches, all available connectivity information is taken into account, and vertices may appear in none or several of the subnetworks. Subject-by-subject “scores” for each principal network may also be obtained, under certain circumstances, and related to demographic or cognitive variables of interest.     

Local and collective transitions in sparsely-interacting ecological communities

Interactions in natural communities can be highly heterogeneous, with any given species interacting appreciably with only some of the others, a situation commonly represented by sparse interaction networks. We study the consequences of sparse competitive interactions, in a theoretical model of a community assembled from a species pool. We find that communities can be in a number of different regimes, depending on the interaction strength. When interactions are strong, the network of coexisting species breaks up into small subgraphs, while for weaker interactions these graphs are larger and more complex, eventually encompassing all species. This process is driven by the emergence of new allowed subgraphs as interaction strength decreases, leading to sharp changes in diversity and other community properties, and at weaker interactions to two distinct collective transitions: a percolation transition, and a transition between having a unique equilibrium and having multiple alternative equilibria. Understanding community structure is thus made up of two parts: first, finding which subgraphs are allowed at a given interaction strength, and secondly, a discrete problem of matching these structures over the entire community. In a shift from the focus of many previous theories, these different regimes can be traversed by modifying the interaction strength alone, without need for heterogeneity in either interaction strengths or the number of competitors per species.     

The impacts of network topology on disease spread

Individuals in a population susceptible to a disease may be represented as vertices in a network, with the edges that connect vertices representing social and/or spatial contact between individuals. Networks, which explicitly included six different patterns of connection between vertices, were created. Both scale-free networks and random graphs showed a different response in path level to increasing levels of clustering than regular lattices. Clustering promoted short path lengths in all network types, but randomly assembled networks displayed a logarithmic relationship between degree and path length; whereas this response was linear in regular lattices. In all cases, small-world models, generated by rewiring the connections of a regular lattice, displayed properties, which spanned the gap between random and regular networks.Simulation of a disease in these networks showed a strong response to connectance pattern, even when the number of edges and vertices were approximately equal. Epidemic spread was fastest, and reached the largest size, in scale-free networks, then in random graphs. Regular lattices were the slowest to be infected, and rewired lattices were intermediate between these two extremes. Scale-free networks displayed the capacity to produce an epidemic even at a likelihood of infection, which was too low to produce an epidemic for the other network types. The interaction between the statistical properties of the network and the results of epidemic spread provides a useful tool for assessing the risk of disease spread in more realistic networks.     

Reconstruction of Some Hybrid Phylogenetic Networks with Homoplasies from Distances

Suppose G is a phylogenetic network given as a rooted acyclic directed graph. Let X be a subset of the vertex set containing the root, all leaves, and all vertices of outdegree 1. A vertex is “regular” if it has a unique parent, and “hybrid” if it has two parents. Consider the case where each gene is binary. Assume an idealized system of inheritance in which no homoplasies occur at regular vertices, but homoplasies can occur at hybrid vertices. Under our model, the distances between taxa are shown to be described using a system of numbers called “originating weights” and “homoplasy weights.” Assume that the distances are known between all members of X. Sufficient conditions are given such that the graph G and all the originating and homoplasy weights can be reconstructed from the given distances.     

Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs

SUMMARY: Biological and engineered networks have recently been shown to display network motifs: a small set of characteristic patterns that occur much more frequently than in randomized networks with the same degree sequence. Network motifs were demonstrated to play key information processing roles in biological regulation networks. Existing algorithms for detecting network motifs act by exhaustively enumerating all subgraphs with a given number of nodes in the network. The runtime of such algorithms increases strongly with network size. Here, we present a novel algorithm that allows estimation of subgraph concentrations and detection of network motifs at a runtime that is asymptotically independent of the network size. This algorithm is based on random sampling of subgraphs. Network motifs are detected with a surprisingly small number of samples in a wide variety of networks. Our method can be applied to estimate the concentrations of larger subgraphs in larger networks than was previously possible with exhaustive enumeration algorithms. We present results for high-order motifs in several biological networks and discuss their possible functions. AVAILABILITY: A software tool for estimating subgraph concentrations and detecting network motifs (mfinder 1.1) and further information is available at http://www.weizmann.ac.il/mcb/UriAlon/     

How accurate and statistically robust are catalytic site predictions based on closeness centrality?

Background  

We examine the accuracy of enzyme catalytic residue predictions from a network representation of protein structure. In this model, amino acid α-carbons specify vertices within a graph and edges connect vertices that are proximal in structure. Closeness centrality, which has shown promise in previous investigations, is used to identify important positions within the network. Closeness centrality, a global measure of network centrality, is calculated as the reciprocal of the average distance between vertex i and all other vertices.     

Coupled map lattice simulation of epileptogenesis in hippocampal slices

Bioelectric activity of a nervous tissue and its synchronization with formating epileptiform bursts are simulated by a coupled map lattice. The functional units of the map located in the lattice sites represent neural masses which consist of current sources and sinks. The sources lead to depolarization of neurons, and sinks provide hyperpolarization. The map describes a single variable – the bioelectric potential. This potential is created by the interplay of all current sources and sinks in the neural masses. The neural masses are diffusively coupled with each other both by electrotonic influence and synaptic coupling. Both mechanisms mentioned are suggested to be essential for the formation of synchronous bursts. The transition from chaotic activity to bursts was studied. Received: 30 September 1997 / Accepted in revised from: 11 March 1998     

Inverse folding with RNA-As-Graphs produces a large pool of candidate sequences with target topologies

We present an RNA-As-Graphs (RAG) based inverse folding algorithm, RAG-IF, to design novel RNA sequences that fold onto target tree graph topologies. The algorithm can be used to enhance our recently reported computational design pipeline (Jain et al., NAR 2018). The RAG approach represents RNA secondary structures as tree and dual graphs, where RNA loops and helices are coarse-grained as vertices and edges, opening the usage of graph theory methods to study, predict, and design RNA structures. Our recently developed computational pipeline for design utilizes graph partitioning (RAG-3D) and atomic fragment assembly (F-RAG) to design sequences to fold onto RNA-like tree graph topologies; the atomic fragments are taken from existing RNA structures that correspond to tree subgraphs. Because F-RAG may not produce the target folds for all designs, automated mutations by RAG-IF algorithm enhance the candidate pool markedly. The crucial residues for mutation are identified by differences between the predicted and the target topology. A genetic algorithm then mutates the selected residues, and the successful sequences are optimized to retain only the minimal or essential mutations. Here we evaluate RAG-IF for 6 RNA-like topologies and generate a large pool of successful candidate sequences with a variety of minimal mutations. We find that RAG-IF adds robustness and efficiency to our RNA design pipeline, making inverse folding motivated by graph topology rather than secondary structure more productive.     

Coordinated force production in multi-finger tasks: finger interaction and neural network modeling

During maximal voluntary contraction (MVC) with several fingers, the following three phenomena are observed: (1) the total force produced by all the involved fingers is shared among the fingers in a specific manner (sharing); (2) the force produced by a given finger in a multi-finger task is smaller than the force generated by this finger in a single-finger task (force deficit); (3) the fingers that are not required to produce any force by instruction are involuntary activated (enslaving). We studied involuntary force production by individual fingers (enslaving effects, EE) during tasks when (an)other finger(s) of the hand generated maximal voluntary pressing force in isometric conditions. The subjects (n = 10) were instructed to press as hard as possible on the force sensors with one, two, three and four fingers acting in parallel in all possible combinations. The EE were (A) large, the slave fingers always producing a force ranging from 10.9% to 54.7% of the maximal force produced by the finger in the single-finger task; (B) nearly symmetrical; (C) larger for the neighboring fingers; and (D) non-additive. In most cases, the EE from two or three fingers were smaller than the EE from at least one finger (this phenomenon was coined occlusion). The occlusion cannot be explained only by anatomical musculo-tendinous connections. Therefore, neural factors contribute substantially to the EE. A neural network model that accounts for all the three effects has been developed. The model consists of three layers: the input layer that models a central neural drive; the hidden layer modeling transformation of the central drive into an input signal to the muscles serving several fingers simultaneously (multi-digit muscles); and the output layer representing finger force output. The output of the hidden layer is set inversely proportional to the number of fingers involved. In addition, direct connections between the input and output layers represent signals to the hand muscles serving individual fingers (uni-digit muscles). The network was validated using three different training sets. Single digit muscles contributed from 25% to 50% of the total finger force. The master matrix and the enslaving matrix were computed; they characterize the ability of a given finger to enslave other fingers and its ability to be enslaved. Overall, the neural network modeling suggests that no direct correspondence exists between neural command to an individual finger and finger force. To produce a desired finger force, a command sent to an intended finger should be scaled in accordance with the commands sent to the other fingers. Received: 17 October 1997 / Accepted in revised form: 12 May 1998     

The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration

Subgraph matching algorithms are used to find and enumerate specific interconnection structures in networks. By enumerating these specific structures/subgraphs, the fundamental properties of the network can be derived. More specifically in biological networks, subgraph matching algorithms are used to discover network motifs, specific patterns occurring more often than expected by chance. Finding these network motifs yields information on the underlying biological relations modelled by the network. In this work, we present the Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS), an improved version of the Index-based Subgraph Matching Algorithm (ISMA). ISMA quickly finds all instances of a predefined motif in a network by intelligently exploring the search space and taking into account easily identifiable symmetric structures. However, more complex symmetries (possibly involving switching multiple nodes) are not taken into account, resulting in superfluous output. ISMAGS overcomes this problem by using a customised symmetry analysis phase to detect all symmetric structures in the network motif subgraphs. These structures are then converted to symmetry-breaking constraints used to prune the search space and speed up calculations. The performance of the algorithm was tested on several types of networks (biological, social and computer networks) for various subgraphs with a varying degree of symmetry. For subgraphs with complex (multi-node) symmetric structures, high speed-up factors are obtained as the search space is pruned by the symmetry-breaking constraints. For subgraphs with no or simple symmetric structures, ISMAGS still reduces computation times by optimising set operations. Moreover, the calculated list of subgraph instances is minimal as it contains no instances that differ by only a subgraph symmetry. An implementation of the algorithm is freely available at https://github.com/mhoubraken/ISMAGS.     

A Graph Algorithmic Approach to Separate Direct from Indirect Neural Interactions

Network graphs have become a popular tool to represent complex systems composed of many interacting subunits; especially in neuroscience, network graphs are increasingly used to represent and analyze functional interactions between multiple neural sources. Interactions are often reconstructed using pairwise bivariate analyses, overlooking the multivariate nature of interactions: it is neglected that investigating the effect of one source on a target necessitates to take all other sources as potential nuisance variables into account; also combinations of sources may act jointly on a given target. Bivariate analyses produce networks that may contain spurious interactions, which reduce the interpretability of the network and its graph metrics. A truly multivariate reconstruction, however, is computationally intractable because of the combinatorial explosion in the number of potential interactions. Thus, we have to resort to approximative methods to handle the intractability of multivariate interaction reconstruction, and thereby enable the use of networks in neuroscience. Here, we suggest such an approximative approach in the form of an algorithm that extends fast bivariate interaction reconstruction by identifying potentially spurious interactions post-hoc: the algorithm uses interaction delays reconstructed for directed bivariate interactions to tag potentially spurious edges on the basis of their timing signatures in the context of the surrounding network. Such tagged interactions may then be pruned, which produces a statistically conservative network approximation that is guaranteed to contain non-spurious interactions only. We describe the algorithm and present a reference implementation in MATLAB to test the algorithm’s performance on simulated networks as well as networks derived from magnetoencephalographic data. We discuss the algorithm in relation to other approximative multivariate methods and highlight suitable application scenarios. Our approach is a tractable and data-efficient way of reconstructing approximative networks of multivariate interactions. It is preferable if available data are limited or if fully multivariate approaches are computationally infeasible.     

Estimating genomic coexpression networks using first-order conditional independence

We describe a computationally efficient statistical framework for estimating networks of coexpressed genes. This framework exploits first-order conditional independence relationships among gene-expression measurements to estimate patterns of association. We use this approach to estimate a coexpression network from microarray gene-expression measurements from Saccharomyces cerevisiae. We demonstrate the biological utility of this approach by showing that a large number of metabolic pathways are coherently represented in the estimated network. We describe a complementary unsupervised graph search algorithm for discovering locally distinct subgraphs of a large weighted graph. We apply this algorithm to our coexpression network model and show that subgraphs found using this approach correspond to particular biological processes or contain representatives of distinct gene families.