Bipartite graphs as models of population structures in evolutionary multiplayer games

By combining evolutionary game theory and graph theory, "games on graphs" study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner's dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner's dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.     

Random-effects ordination: describing and predicting multivariate correlations and co-occurrences

Ecology is inherently multivariate, but high-dimensional data are difficult to understand. Dimension reduction with ordination analysis helps with both data exploration and clarification of the meaning of inferences (e.g., randomization tests, variation partitioning) about a statistical population. Most such inferences are asymmetric, in that variables are classified as either response or explanatory (e.g., factors, predictors). But this asymmetric approach has limitations (e.g., abiotic variables may not entirely explain correlations between interacting species). We study symmetric population-level inferences by modeling correlations and co-occurrences, using these models for out-of-sample prediction. Such modeling requires a novel treatment of ordination axes as random effects, because fixed effects only allow within-sample predictions. We advocate an iterative methodology for random-effects ordination: (1) fit a set of candidate models differing in complexity (e.g., number of axes); (2) use information criteria to choose among models; (3) compare model predictions with data; (4) explore dimension-reduced graphs (e.g., biplots); (5) repeat 1–4 if model performance is poor. We describe and illustrate random-effects ordination models (with software) for two types of data: multivariate-normal (e.g., log morphometric data) and presence–absence community data. A large simulation experiment with multivariate-normal data demonstrates good performance of (1) a small-sample-corrected information criterion and (2) factor analysis relative to principal component analysis. Predictive comparisons of multiple alternative models is a powerful form of scientific reasoning: we have shown that unconstrained ordination can be based on such reasoning.     

Computing paths and cycles in biological interaction graphs

Background  

Interaction graphs (signed directed graphs) provide an important qualitative modeling approach for Systems Biology. They enable the analysis of causal relationships in cellular networks and can even be useful for predicting qualitative aspects of systems dynamics. Fundamental issues in the analysis of interaction graphs are the enumeration of paths and cycles (feedback loops) and the calculation of shortest positive/negative paths. These computational problems have been discussed only to a minor extent in the context of Systems Biology and in particular the shortest signed paths problem requires algorithmic developments.     

PathFinder: reconstruction and dynamic visualization of metabolic pathways

MOTIVATION: Beyond methods for a gene-wise annotation and analysis of sequenced genomes new automated methods for functional analysis on a higher level are needed. The identification of realized metabolic pathways provides valuable information on gene expression and regulation. Detection of incomplete pathways helps to improve a constantly evolving genome annotation or discover alternative biochemical pathways. To utilize automated genome analysis on the level of metabolic pathways new methods for the dynamic representation and visualization of pathways are needed. RESULTS: PathFinder is a tool for the dynamic visualization of metabolic pathways based on annotation data. Pathways are represented as directed acyclic graphs, graph layout algorithms accomplish the dynamic drawing and visualization of the metabolic maps. A more detailed analysis of the input data on the level of biochemical pathways helps to identify genes and detect improper parts of annotations. As an Relational Database Management System (RDBMS) based internet application PathFinder reads a list of EC-numbers or a given annotation in EMBL- or Genbank-format and dynamically generates pathway graphs.     

Markov clustering versus affinity propagation for the partitioning of protein interaction graphs

Background  

Genome scale data on protein interactions are generally represented as large networks, or graphs, where hundreds or thousands of proteins are linked to one another. Since proteins tend to function in groups, or complexes, an important goal has been to reliably identify protein complexes from these graphs. This task is commonly executed using clustering procedures, which aim at detecting densely connected regions within the interaction graphs. There exists a wealth of clustering algorithms, some of which have been applied to this problem. One of the most successful clustering procedures in this context has been the Markov Cluster algorithm (MCL), which was recently shown to outperform a number of other procedures, some of which were specifically designed for partitioning protein interactions graphs. A novel promising clustering procedure termed Affinity Propagation (AP) was recently shown to be particularly effective, and much faster than other methods for a variety of problems, but has not yet been applied to partition protein interaction graphs.     

Constructing an enzyme-centric view of metabolism

MOTIVATION: The current paradigm for viewing metabolism, such as the Boehringer Chart or KEGG, takes a metabolite-centric view that is not ideal for genomics analysis because the same enzyme can appear in multiple places. Therefore an enzyme-centric view is also required. RESULTS: We have eliminated synonymous compound names taken from the ENZYME database ensuring that it is computationally parseable at all levels. Based on these results, we have written a software to create enzyme-centric graphs from reaction data, and we have created a second dataset with hub molecules removed, allowing a greater depth of information to be extracted from these graphs. We also present a detailed analysis of the various stages of the reconditioning process and the characteristics of the subgraphs resulting from the application of our software to the revised datasets. AVAILABILITY: Complete datasets and supplementary material may be downloaded from http://helix.ex.ac.uk/metabolism. The software for the creation of enzyme-centric graphs from reaction data is available on request from the authors.     

medplot: A Web Application for Dynamic Summary and Analysis of Longitudinal Medical Data Based on R

In biomedical studies the patients are often evaluated numerous times and a large number of variables are recorded at each time-point. Data entry and manipulation of longitudinal data can be performed using spreadsheet programs, which usually include some data plotting and analysis capabilities and are straightforward to use, but are not designed for the analyses of complex longitudinal data. Specialized statistical software offers more flexibility and capabilities, but first time users with biomedical background often find its use difficult. We developed medplot, an interactive web application that simplifies the exploration and analysis of longitudinal data. The application can be used to summarize, visualize and analyze data by researchers that are not familiar with statistical programs and whose knowledge of statistics is limited. The summary tools produce publication-ready tables and graphs. The analysis tools include features that are seldom available in spreadsheet software, such as correction for multiple testing, repeated measurement analyses and flexible non-linear modeling of the association of the numerical variables with the outcome. medplot is freely available and open source, it has an intuitive graphical user interface (GUI), it is accessible via the Internet and can be used within a web browser, without the need for installing and maintaining programs locally on the user’s computer. This paper describes the application and gives detailed examples describing how to use the application on real data from a clinical study including patients with early Lyme borreliosis.     

Study of biological networks using graph theory

As an effective modeling, analysis and computational tool, graph theory is widely used in biological mathematics to deal with various biology problems. In the field of microbiology, graph can express the molecular structure, where cell, gene or protein can be denoted as a vertex, and the connect element can be regarded as an edge. In this way, the biological activity characteristic can be measured via topological index computing in the corresponding graphs. In our article, we mainly study the biology features of biological networks in terms of eccentric topological indices computation. By means of graph structure analysis and distance calculating, the exact expression of several important eccentric related indices of hypertree network and X-tree are determined. The conclusions we get in this paper illustrate that the bioengineering has the promising application prospects.     

MetaGen: 从KEGG建模代谢网络的新工具

为便于大规模代谢网络的计算,发展了一款方便实用的工具:MetaGen,对Kyoto Encyclopedia of Genesand Genomes(KEGG)中物种特异的各层次代谢系统进行建模,生成的代谢网络以酶图和通路图的方式表示.利用该工具,对人类代谢系统的bow-tie结构进行了初步研究,并以此为例展示了该工具广阔的应用前景.MetaGen利用KEGGweb服务保证建模数据的可靠性,依靠本地关系数据库加速网络建模过程并提供更多的数据管理和利用方式,并结合高级JAVA技术提高代码的可扩展性.MetaGen完全开源,可直接从http://bnct.sourceforge.net/下载.     

Local Difference Measures between Complex Networks for Dynamical System Model Evaluation

A faithful modeling of real-world dynamical systems necessitates model evaluation. A recent promising methodological approach to this problem has been based on complex networks, which in turn have proven useful for the characterization of dynamical systems. In this context, we introduce three local network difference measures and demonstrate their capabilities in the field of climate modeling, where these measures facilitate a spatially explicit model evaluation. Building on a recent study by Feldhoff et al. [1] we comparatively analyze statistical and dynamical regional climate simulations of the South American monsoon system. Three types of climate networks representing different aspects of rainfall dynamics are constructed from the modeled precipitation space-time series. Specifically, we define simple graphs based on positive as well as negative rank correlations between rainfall anomaly time series at different locations, and such based on spatial synchronizations of extreme rain events. An evaluation against respective networks built from daily satellite data provided by the Tropical Rainfall Measuring Mission 3B42 V7 reveals far greater differences in model performance between network types for a fixed but arbitrary climate model than between climate models for a fixed but arbitrary network type. We identify two sources of uncertainty in this respect. Firstly, climate variability limits fidelity, particularly in the case of the extreme event network; and secondly, larger geographical link lengths render link misplacements more likely, most notably in the case of the anticorrelation network; both contributions are quantified using suitable ensembles of surrogate networks. Our model evaluation approach is applicable to any multidimensional dynamical system and especially our simple graph difference measures are highly versatile as the graphs to be compared may be constructed in whatever way required. Generalizations to directed as well as edge- and node-weighted graphs are discussed.     

EZ-FIT: a practical curve-fitting microcomputer program for the analysis of enzyme kinetic data on IBM-PC compatible computers

EZ-FIT, an interactive microcomputer software package, has been developed for the analysis of enzyme kinetic and equilibrium binding data. EZ-FIT was designed as a user-friendly menu-driven package that has the facility for data entry, editing, and filing. Data input permits the conversion of cpm, dpm, or optical density to molar per minute per milligram protein. Data can be fit to any of 14 model equations including Michaelis-Menten, Hill, isoenzyme, inhibition, dual substrate, agonist, antagonist, and modified integrated Michaelis-Menten. The program uses the Nelder-Mead simplex and Marquardt nonlinear regression algorithms sequentially. A report of the results includes the parameter estimates with standard errors, a Student t test to determine the accuracy of the parameter values, a Runs statistic test of the residuals, identification of outlying data, an Akaike information criterion test for goodness-of-fit, and, when the experimental variance is included, a chi 2 statistic test for goodness-of-fit. Several different graphs can be displayed: an X-Y, a Scatchard, an Eadie-Hofstee, a Lineweaver-Burk, a semilogarithmic, and a residual plot. A data analysis report and graphs are designed to evaluate the goodness-of-fit of the data to a particular model.     

Phenostat: visualization and statistical tool for analysis of phenotyping data

The effective extraction of information from multidimensional data sets derived from phenotyping experiments is a growing challenge in biology. Data visualization tools are important resources that can aid in exploratory data analysis of complex data sets. Phenotyping experiments of model organisms produce data sets in which a large number of phenotypic measures are collected for each individual in a group. A critical initial step in the analysis of such multidimensional data sets is the exploratory analysis of data distribution and correlation. To facilitate the rapid visualization and exploratory analysis of multidimensional complex trait data, we have developed a user-friendly, web-based software tool called Phenostat. Phenostat is composed of a dynamic graphical environment that allows the user to inspect the distribution of multiple variables in a data set simultaneously. Individuals can be selected by directly clicking on the graphs and thus displaying their identity, highlighting corresponding values in all graphs, allowing their inclusion or exclusion from the analysis. Statistical analysis is provided by R package functions. Phenostat is particularly suited for rapid distribution and correlation analysis of subsets of data. An analysis of behavioral and physiologic data stemming from a large mouse phenotyping experiment using Phenostat reveals previously unsuspected correlations. Phenostat is freely available to academic institutions and nonprofit organizations and can be used from our website at .     

BicAT: a biclustering analysis toolbox

SUMMARY: Besides classical clustering methods such as hierarchical clustering, in recent years biclustering has become a popular approach to analyze biological data sets, e.g. gene expression data. The Biclustering Analysis Toolbox (BicAT) is a software platform for clustering-based data analysis that integrates various biclustering and clustering techniques in terms of a common graphical user interface. Furthermore, BicAT provides different facilities for data preparation, inspection and postprocessing such as discretization, filtering of biclusters according to specific criteria or gene pair analysis for constructing gene interconnection graphs. The possibility to use different biclustering algorithms inside a single graphical tool allows the user to compare clustering results and choose the algorithm that best fits a specific biological scenario. The toolbox is described in the context of gene expression analysis, but is also applicable to other types of data, e.g. data from proteomics or synthetic lethal experiments. AVAILABILITY: The BicAT toolbox is freely available at http://www.tik.ee.ethz.ch/sop/bicat and runs on all operating systems. The Java source code of the program and a developer's guide is provided on the website as well. Therefore, users may modify the program and add further algorithms or extensions.     

Local modeling of global interactome networks

MOTIVATION: Systems biology requires accurate models of protein complexes, including physical interactions that assemble and regulate these molecular machines. Yeast two-hybrid (Y2H) and affinity-purification/mass-spectrometry (AP-MS) technologies measure different protein-protein relationships, and issues of completeness, sensitivity and specificity fuel debate over which is best for high-throughput 'interactome' data collection. Static graphs currently used to model Y2H and AP-MS data neglect dynamic and spatial aspects of macromolecular complexes and pleiotropic protein function. RESULTS: We apply the local modeling methodology proposed by Scholtens and Gentleman (2004) to two publicly available datasets and demonstrate its uses, interpretation and limitations. Specifically, we use this technology to address four major issues pertaining to protein-protein networks. (1) We motivate the need to move from static global interactome graphs to local protein complex models. (2) We formally show that accurate local interactome models require both Y2H and AP-MS data, even in idealized situations. (3) We briefly discuss experimental design issues and how bait selection affects interpretability of results. (4) We point to the implications of local modeling for systems biology including functional annotation, new complex prediction, pathway interactivity and coordination with gene-expression data. AVAILABILITY: The local modeling algorithm and all protein complex estimates reported here can be found in the R package apComplex, available at http://www.bioconductor.org CONTACT: dscholtens@northwestern.edu SUPPLEMENTARY INFORMATION: http://daisy.prevmed.northwestern.edu/~denise/pubs/LocalModeling     

BioNetSim: a Petri net-based modeling tool for simulations of biochemical processes

BioNetSim, a Petri net-based software for modeling and simulating biochemistry processes, is developed, whose design and implement are presented in this paper, including logic construction, real-time access to KEGG (Kyoto Encyclopedia of Genes and Genomes), and BioModel database. Furthermore, glycolysis is simulated as an example of its application. BioNetSim is a helpful tool for researchers to download data, model biological network, and simulate complicated biochemistry processes. Gene regulatory networks, metabolic pathways, signaling pathways, and kinetics of cell interaction are all available in BioNetSim, which makes modeling more efficient and effective. Similar to other Petri net-based softwares, BioNetSim does well in graphic application and mathematic construction. Moreover, it shows several powerful predominances. (1) It creates models in database. (2) It realizes the real-time access to KEGG and BioModel and transfers data to Petri net. (3) It provides qualitative analysis, such as computation of constants. (4) It generates graphs for tracing the concentration of every molecule during the simulation processes.     

New concentration measures as kinds of the quadratic entropy

We introduced two new quadratic entropy indices and performed numerical experimentation on biological data sets to reveal their properties. The difference between two individuals was postulated in both cases on the basis of occurrence probabilities of the species concerned. The new measures summarize a different aspect of community properties than biodiversity indices. They may play a critical role among others in population dynamic models and in the analysis of dominance in ecology. The numerical experimentation was based in part on the characteristics of so-called sensitivity graphs. The graphs related to the new indices are very similar to the opposites of sensitivity graphs of diversity indices, generally used in statistical ecology. Further relations between the new indices and concentration indices were analysed on plot diagrams originating from simulated data. From these analyses, we conclude that the new quadratic entropies are close to concentration measures.     

A flexible annealing chaotic neural network to maximum clique problem

Based on the analysis and comparison of several annealing strategies, we present a flexible annealing chaotic neural network which has flexible controlling ability and quick convergence rate to optimization problem. The proposed network has rich and adjustable chaotic dynamics at the beginning, and then can converge quickly to stable states. We test the network on the maximum clique problem by some graphs of the DIMACS clique instances, p-random and k random graphs. The simulations show that the flexible annealing chaotic neural network can get satisfactory solutions at very little time and few steps. The comparison between our proposed network and other chaotic neural networks denotes that the proposed network has superior executive efficiency and better ability to get optimal or near-optimal solution.     

PATIKAmad: putting microarray data into pathway context

High-throughput experiments, most significantly DNA microarrays, provide us with system-scale profiles. Connecting these data with existing biological networks poses a formidable challenge to uncover facts about a cell's proteome. Studies and tools with this purpose are limited to networks with simple structure, such as protein-protein interaction graphs, or do not go much beyond than simply displaying values on the network. We have built a microarray data analysis tool, named PATIKAmad, which can be used to associate microarray data with the pathway models in mechanistic detail, and provides facilities for visualization, clustering, querying, and navigation of biological graphs related with loaded microarray experiments. PATIKAmad is freely available to noncommercial users as a new module of PATIKAweb at http://web.patika.org.