Extracting gene networks for low-dose radiation using graph theoretical algorithms

Genes with common functions often exhibit correlated expression levels, which can be used to identify sets of interacting genes from microarray data. Microarrays typically measure expression across genomic space, creating a massive matrix of co-expression that must be mined to extract only the most relevant gene interactions. We describe a graph theoretical approach to extracting co-expressed sets of genes, based on the computation of cliques. Unlike the results of traditional clustering algorithms, cliques are not disjoint and allow genes to be assigned to multiple sets of interacting partners, consistent with biological reality. A graph is created by thresholding the correlation matrix to include only the correlations most likely to signify functional relationships. Cliques computed from the graph correspond to sets of genes for which significant edges are present between all members of the set, representing potential members of common or interacting pathways. Clique membership can be used to infer function about poorly annotated genes, based on the known functions of better-annotated genes with which they share clique membership (i.e., “guilt-by-association”). We illustrate our method by applying it to microarray data collected from the spleens of mice exposed to low-dose ionizing radiation. Differential analysis is used to identify sets of genes whose interactions are impacted by radiation exposure. The correlation graph is also queried independently of clique to extract edges that are impacted by radiation. We present several examples of multiple gene interactions that are altered by radiation exposure and thus represent potential molecular pathways that mediate the radiation response.     

Stability of Metabolic Correlations under Changing Environmental Conditions in Escherichia coli – A Systems Approach

Background

Biological systems adapt to changing environments by reorganizing their cellular and physiological program with metabolites representing one important response level. Different stresses lead to both conserved and specific responses on the metabolite level which should be reflected in the underlying metabolic network.

Methodology/Principal Findings

Starting from experimental data obtained by a GC-MS based high-throughput metabolic profiling technology we here develop an approach that: (1) extracts network representations from metabolic condition-dependent data by using pairwise correlations, (2) determines the sets of stable and condition-dependent correlations based on a combination of statistical significance and homogeneity tests, and (3) can identify metabolites related to the stress response, which goes beyond simple observations about the changes of metabolic concentrations. The approach was tested with Escherichia coli as a model organism observed under four different environmental stress conditions (cold stress, heat stress, oxidative stress, lactose diauxie) and control unperturbed conditions. By constructing the stable network component, which displays a scale free topology and small-world characteristics, we demonstrated that: (1) metabolite hubs in this reconstructed correlation networks are significantly enriched for those contained in biochemical networks such as EcoCyc, (2) particular components of the stable network are enriched for functionally related biochemical pathways, and (3) independently of the response scale, based on their importance in the reorganization of the correlation network a set of metabolites can be identified which represent hypothetical candidates for adjusting to a stress-specific response.

Conclusions/Significance

Network-based tools allowed the identification of stress-dependent and general metabolic correlation networks. This correlation-network-based approach does not rely on major changes in concentration to identify metabolites important for stress adaptation, but rather on the changes in network properties with respect to metabolites. This should represent a useful complementary technique in addition to more classical approaches.     

Predicting Disease-Related Proteins Based on Clique Backbone in Protein-Protein Interaction Network

Network biology integrates different kinds of data, including physical or functional networks and disease gene sets, to interpret human disease. A clique (maximal complete subgraph) in a protein-protein interaction network is a topological module and possesses inherently biological significance. A disease-related clique possibly associates with complex diseases. Fully identifying disease components in a clique is conductive to uncovering disease mechanisms. This paper proposes an approach of predicting disease proteins based on cliques in a protein-protein interaction network. To tolerate false positive and negative interactions in protein networks, extending cliques and scoring predicted disease proteins with gene ontology terms are introduced to the clique-based method. Precisions of predicted disease proteins are verified by disease phenotypes and steadily keep to more than 95%. The predicted disease proteins associated with cliques can partly complement mapping between genotype and phenotype, and provide clues for understanding the pathogenesis of serious diseases.     

The origin of correlations in metabolomics data

A phenomenon observed earlier in the development of metabolomics as a systems biology methodology, consists of a small but significant number of metabolites whose levels are highly correlated between biological replicates. Contrary to initial interpretations, these correlations are not necessarily only between neighboring metabolites in the metabolic network. Most metabolites that participate in common reactions are not correlated in this way, while some non-neighboring metabolites are highly correlated. Here we investigate the origin of such correlations using metabolic control analysis and computer simulation of biochemical networks. A series of cases is identified which lead to high correlation between metabolite pairs in replicate measurement. These are (1) chemical equilibrium, (2) mass conservation, (3) asymmetric control distribution, and (4) unusually high variance in the expression of a single gene. The importance of identifying metabolite correlations within a physiological state and changes of correlation between different states is discussed in the context of systems biology.     

Maximal clique method for the automated analysis of NMR TOCSY spectra of complex mixtures

Characterization of the chemical components of complex mixtures in solution is important in many areas of biochemistry and chemical biology, including metabolomics. The use of 2D NMR total correlation spectroscopy (TOCSY) experiments has proven very useful for the identification of known metabolites as well as for the characterization of metabolites that are unknown by taking advantage of the good resolution and high sensitivity of this homonuclear experiment. Due to the complexity of the resulting spectra, automation is critical to facilitate and speed-up their analysis and enable high-throughput applications. To better meet these emerging needs, an automated spin-system identification algorithm of TOCSY spectra is introduced that represents the cross-peaks and their connectivities as a mathematical graph, for which all subgraphs are determined that are maximal cliques. Each maximal clique can be assigned to an individual spin system thereby providing a robust deconvolution of the original spectrum for the easy extraction of critical spin system information. The approach is demonstrated for a complex metabolite mixture consisting of 20 compounds and for E. coli cell lysate.     

Observing local and global properties of metabolic pathways: 'load points' and 'choke points' in the metabolic networks

MOTIVATION: The local and global aspects of metabolic network analyses allow us to identify enzymes or reactions that are crucial for the survival of the organism(s), therefore directing us towards the discovery of potential drug targets. RESULTS: We demonstrate a new method ('load points') to rank the enzymes/metabolites in the metabolic network and propose a model to determine and rank the biochemical lethality in metabolic networks (enzymes/metabolites) through 'choke points'. Based on an extended form of the graph theory model of metabolic networks, metabolite structural information was used to calculate the k-shortest paths between metabolites (the presence of more than one competing path between substrate and product). On the basis of these paths and connectivity information, load points were calculated and used to empirically rank the importance of metabolites/enzymes in the metabolic network. The load point analysis emphasizes the role that the biochemical structure of a metabolite, rather than its connectivity (hubs), plays in the conversion pathway. In order to identify potential drug targets (based on the biochemical lethality of metabolic networks), the concept of choke points and load points was used to find enzymes (edges) which uniquely consume or produce a particular metabolite (nodes). A non-pathogenic bacterial strain Bacillus subtilis 168 (lactic acid producing bacteria) and a related pathogenic bacterial strain Bacillus anthracis Sterne (avirulent but toxigenic strain, producing the toxin Anthrax) were selected as model organisms. The choke point strategy was implemented on the pathogen bacterial network of B.anthracis Sterne. Potential drug targets are proposed based on the analysis of the top 10 choke points in the bacterial network. A comparative study between the reported top 10 bacterial choke points and the human metabolic network was performed. Further biological inferences were made on results obtained by performing a homology search against the human genome. AVAILABILITY: The load and choke point modules are introduced in the Pathway Hunter Tool (PHT), the basic version of which is available on http://www.pht.uni-koeln.de.     

Similarities and differences of gene expression in yeast stress conditions

MOTIVATION AND METHODS: All living organisms and the survival of all cells critically depend on their ability to sense and quickly adapt to changes in the environment and to other stress conditions. We study stress response mechanisms in Saccharomyces cerevisiae by identifying genes that, according to very stringent criteria, have persistent co-expression under a variety of stress conditions. This is enabled through a fast clique search method applied to the intersection of several co-expression graphs calculated over the data of Gasch et al. This method exploits the topological characteristics of these graphs. RESULTS: We observe cliques in the intersection graphs that are much larger than expected under a null model of changing gene identities for different stress conditions but maintaining the co-expression topology within each one. Persistent cliques are analyzed to identify enriched function as well as enriched regulation by a small number of TFs. These TFs, therefore, characterize a universal and persistent reaction to stress response. We further demonstrate that the vertices (genes) of many cliques in the intersection graphs are co-localized in the yeast genome, to a degree far beyond the random expectation. Co-localization can hypothetically contribute to a quick co-ordinated response. We propose the use of persistent cliques in further study of properties of co-regulation.     

Metabolomic correlation-network modules in Arabidopsis based on a graph-clustering approach

Background  

Deciphering the metabolome is essential for a better understanding of the cellular metabolism as a system. Typical metabolomics data show a few but significant correlations among metabolite levels when data sampling is repeated across individuals grown under strictly controlled conditions. Although several studies have assessed topologies in metabolomic correlation networks, it remains unclear whether highly connected metabolites in these networks have specific functions in known tissue- and/or genotype-dependent biochemical pathways.     

Observing and interpreting correlations in metabolomic networks

MOTIVATION: Metabolite profiling aims at an unbiased identification and quantification of all the metabolites present in a biological sample. Based on their pair-wise correlations, the data obtained from metabolomic experiments are organized into metabolic correlation networks and the key challenge is to deduce unknown pathways based on the observed correlations. However, the data generated is fundamentally different from traditional biological measurements and thus the analysis is often restricted to rather pragmatic approaches, such as data mining tools, to discriminate between different metabolic phenotypes. METHODS AND RESULTS: We investigate to what extent the data generated networks reflect the structure of the underlying biochemical pathways. The purpose of this work is 2-fold: Based on the theory of stochastic systems, we first introduce a framework which shows that the emergent correlations can be interpreted as a 'fingerprint' of the underlying biophysical system. This result leads to a systematic relationship between observed correlation networks and the underlying biochemical pathways. In a second step, we investigate to what extent our result is applicable to the problem of reverse engineering, i.e. to recover the underlying enzymatic reaction network from data. The implications of our findings for other bioinformatics approaches are discussed.     

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.     

Modular modeling of cellular systems with ProMoT/Diva

MOTIVATION: Need for software to setup and analyze complex mathematical models for cellular systems in a modular way, that also integrates the experimental environment of the cells. RESULTS: A computer framework is described which allows the building of modularly structured models using an abstract, modular and general modeling methodology. With this methodology, reusable modeling entities are introduced which lead to the development of a modeling library within the modeling tool ProMot. The simulation environment Diva is used for numerical analysis and parameter identification of the models. The simulation environment provides a number of tools and algorithms to simulate and analyze complex biochemical networks. The described tools are the first steps towards an integrated computer-based modeling, simulation and visualization environment Availability: Available on request to the authors. The software itself is free for scientific purposes but requires commercial libraries. SUPPLEMENTARY INFORMATION: http://www.mpi-magdeburg.mpg.de/projects/promot     

Statistically integrated metabonomic-proteomic studies on a human prostate cancer xenograft model in mice

A novel statistically integrated proteometabonomic method has been developed and applied to a human tumor xenograft mouse model of prostate cancer. Parallel 2D-DIGE proteomic and 1H NMR metabolic profile data were collected on blood plasma from mice implanted with a prostate cancer (PC-3) xenograft and from matched control animals. To interpret the xenograft-induced differences in plasma profiles, multivariate statistical algorithms including orthogonal projection to latent structure (OPLS) were applied to generate models characterizing the disease profile. Two approaches to integrating metabonomic data matrices are presented based on OPLS algorithms to provide a framework for generating models relating to the specific and common sources of variation in the metabolite concentrations and protein abundances that can be directly related to the disease model. Multiple correlations between metabolites and proteins were found, including associations between serotransferrin precursor and both tyrosine and 3-D-hydroxybutyrate. Additionally, a correlation between decreased concentration of tyrosine and increased presence of gelsolin was also observed. This approach can provide enhanced recovery of combination candidate biomarkers across multi-omic platforms, thus, enhancing understanding of in vivo model systems studied by multiple omic technologies.     

FluxAnalyzer: exploring structure,pathways, and flux distributions in metabolic networks on interactive flux maps

MOTIVATION: The analysis of structure, pathways and flux distributions in metabolic networks has become an important approach for understanding the functionality of metabolic systems. The need of a user-friendly platform for stoichiometric modeling of metabolic networks in silico is evident. RESULTS: The FluxAnalyzer is a package for MATLAB and facilitates integrated pathway and flux analysis for metabolic networks within a graphical user interface. Arbitrary metabolic network models can be composed by instances of four types of network elements. The abstract network model is linked with network graphics leading to interactive flux maps which allow for user input and display of calculation results within a network visualization. Therein, a large and powerful collection of tools and algorithms can be applied interactively including metabolic flux analysis, flux optimization, detection of topological features and pathway analysis by elementary flux modes or extreme pathways. The FluxAnalyzer has been applied and tested for complex networks with more than 500,000 elementary modes. Some aspects of the combinatorial complexity of pathway analysis in metabolic networks are discussed. AVAILABILITY: Upon request from the corresponding author. Free for academic users (license agreement). Special contracts are available for industrial corporations. SUPPLEMENTARY INFORMATION: http://www.mpi-magdeburg.mpg.de/projects/fluxanalyzer.     

'Gatherings' of social grooming among wild chimpanzees: implications for evolution of sociality

Chimpanzees (Pan troglodytes) often groom in gatherings that cannot simply be divided into unilateral dyadic grooming interactions. This feature of grooming is studied at two different levels: grooming cliques and grooming clusters. Grooming cliques are defined as directly connected configurations of grooming interactions at any given moment, and when any member of a clique successively grooms any member of another clique within 5min and within a distance of 3m, all the members of both cliques are defined as being in the same grooming cluster. Twenty-seven types of cliques are observed, with the largest one consisting of seven individuals. Mutual and/or polyadic cliques account for more than 25% of all cliques. The size of grooming clusters varies from two to 23 individuals, and almost 70% of the grooming time is spent in polyadic clusters. Although adult males groom the longest in relatively smaller clusters (size=2-4), adult females groomed the longest in clusters of five or more individuals. A review of the literature implies that mutual and polyadic cliques occur less often in other primate species than in chimpanzees. The importance of overlapping interactions for these kinds of gatherings and its possible significance in the evolution of sociality is discussed in this article.     

Equilibrium Distributions of Populations of Biological Species on Networks of Social Sites

ABSTRACT

We investigate the problem of how a population of biological species would distribute over a given network of social sites so that their social contacts through the connected sites can be maximized (or minimized). This problem has applications in modelling the behaviours of social (or solitary) species such as the development of social groups in human society and the spread of solitary animals in distant habitats. We show that this problem can be formulated as an evolutionary game, with the equilibrium state of the game corresponding to a strategy for choosing the residing sites, each with a certain probability, or equivalently, to a distribution of the population on these sites. The game has a symmetric payoff matrix, and can therefore be analyzed via the solution of a corresponding quadratic programme: An equilibrium strategy of the game is a KKT point of the quadratic programme, which may be a local maximizer, local minimizer, or saddle point, but it is evolutionarily stable if and only if it is a strict local maximizer. In general, with a goal to maximize the social contacts, the species tend to spread on network sites where there are dense connections such as a complete subnetwork or in other words, a network clique. We show that at equilibrium, the population may or may not distribute on a network clique, but the stability of the equilibrium state does depend on the structure of the selected subnetwork. In particular, we show that the distribution of the population on a maximal network clique is evolutionarily stable unless the clique is ‘attached’ to another clique of the same or larger size, when the population may be able to switch or expand to the neighbouring clique to increase or at least maintain its total amount of contacts. However, the distribution of the population on a non-clique subnetwork is always evolutionarily unstable or weakly evolutionarily stable at the very best, for the population can always move away from its current distribution without decreasing its total amount of contacts. We conclude that the strategies to spread on maximal network cliques are not only equilibrium strategies but also evolutionarily more stable than those on non-clique subnetworks, thus theoretically reaffirming the evolutionary advantages of joining social cliques in social networks for social species.