Two new schematic rules for rate laws of enzyme-catalysed reactions

The schematic method, when applied to enzyme kinetics, can establish some direct relations between the calculation rules and the graphs expressing the enzyme-catalysed mechanisms. It not only makes the derivation of rate equations more convenient and intuitive, but also facilitates the analysis and discussion of the mechanisms.     

The evolution of helping and harming on graphs: the return of the inclusive fitness effect

Evolutionary graph theory has been proposed as providing new fundamental rules for the evolution of co‐operation and altruism. But how do these results relate to those of inclusive fitness theory? Here, we carry out a retrospective analysis of the models for the evolution of helping on graphs of Ohtsuki et al. [Nature (2006) 441, 502] and Ohtsuki & Nowak [Proc. R. Soc. Lond. Ser. B Biol. Sci (2006) 273, 2249]. We show that it is possible to translate evolutionary graph theory models into classical kin selection models without disturbing at all the mathematics describing the net effect of selection on helping. Model analysis further demonstrates that costly helping evolves on graphs through limited dispersal and overlapping generations. These two factors are well known to promote relatedness between interacting individuals in spatially structured populations. By allowing more than one individual to live at each node of the graph and by allowing interactions to vary with the distance between nodes, our inclusive fitness model allows us to consider a wider range of biological scenarios leading to the evolution of both helping and harming behaviours on graphs.     

Representing and defining patterns by graphs: applications to sol-gel patterns and to cytoskeleton

The problems of interdisciplinary interests--applying methods of graph theory to sol-gel patterns and to cytoskeleton--are discussed. The importance of sol-gel transition phenomena in living cells and the possibility of periodic sol-gel transition phenomena are briefly reviewed. Representing patterns by graphs and using graph probabilistic representation for calculating structure-property relationships are discussed and applied to sol-gel transition patterns.     

The replicator equation on graphs

We study evolutionary games on graphs. Each player is represented by a vertex of the graph. The edges denote who meets whom. A player can use any one of n strategies. Players obtain a payoff from interaction with all their immediate neighbors. We consider three different update rules, called 'birth-death', 'death-birth' and 'imitation'. A fourth update rule, 'pairwise comparison', is shown to be equivalent to birth-death updating in our model. We use pair approximation to describe the evolutionary game dynamics on regular graphs of degree k. In the limit of weak selection, we can derive a differential equation which describes how the average frequency of each strategy on the graph changes over time. Remarkably, this equation is a replicator equation with a transformed payoff matrix. Therefore, moving a game from a well-mixed population (the complete graph) onto a regular graph simply results in a transformation of the payoff matrix. The new payoff matrix is the sum of the original payoff matrix plus another matrix, which describes the local competition of strategies. We discuss the application of our theory to four particular examples, the Prisoner's Dilemma, the Snow-Drift game, a coordination game and the Rock-Scissors-Paper game.     

Oscillations in Biochemical Reaction Networks Arising from Pairs of Subnetworks

Biochemical reaction models show a variety of dynamical behaviors, such as stable steady states, multistability, and oscillations. Biochemical reaction networks with generalized mass action kinetics are represented as directed bipartite graphs with nodes for species and reactions. The bipartite graph of a biochemical reaction network usually contains at least one cycle, i.e., a sequence of nodes and directed edges which starts and ends at the same species node. Cycles can be positive or negative, and it has been shown that oscillations can arise as a result of either a positive cycle or a negative cycle. In earlier work it was shown that oscillations associated with a positive cycle can arise from subnetworks with an odd number of positive cycles. In this article we formulate a similar graph-theoretic condition, which generalizes the negative cycle condition for oscillations. This new graph-theoretic condition for oscillations involves pairs of subnetworks with an even number of positive cycles. An example of a calcium reaction network with generalized mass action kinetics is discussed in detail.     

Graph theoretical methods for comparing phytosociological structures

This paper describes some methods that can be used to compare the phytosociological structure of plant communities using some graph theoretic properties of the directed graphs that represent them. In such a graph, the species are represented by points and the association of species A with species B is represented by a directed line segment going from B to A. Two communities can be compared using simple indices to measure the similarity of their species-lists (point similarity) and of the species associations in them (line similarity). A more sophisticated and informative measure of line similarity is the probability that, given the number of points shared by two graphs, they have at least as many lines in common as they are observed to have. A formula for calculating that probability is given here. The graphs of community structure can also be compared with respect to the homogeneity of the distribution of the lines among the points, a property related to the number of species that are important in determining the composition of the community. These techniques are illustrated using the graphs of the phytosociological structure of intertidal seaweed communities on the southeast coast of Nova Scotia.Nomenclature follows: South and Cardinal (1970)     

Using Random Walks to Generate Associations between Objects

Measuring similarities between objects based on their attributes has been an important problem in many disciplines. Object-attribute associations can be depicted as links on a bipartite graph. A similarity measure can be thought as a unipartite projection of this bipartite graph. The most widely used bipartite projection techniques make assumptions that are not often fulfilled in real life systems, or have the focus on the bipartite connections more than on the unipartite connections. Here, we define a new similarity measure that utilizes a practical procedure to extract unipartite graphs without making a priori assumptions about underlying distributions. Our similarity measure captures the relatedness between two objects via the likelihood of a random walker passing through these nodes sequentially on the bipartite graph. An important aspect of the method is that it is robust to heterogeneous bipartite structures and it controls for the transitivity similarity, avoiding the creation of unrealistic homogeneous degree distributions in the resulting unipartite graphs. We test this method using real world examples and compare the obtained results with alternative similarity measures, by validating the actual and orthogonal relations between the entities.     

Improved analysis of bacterial CGH data beyond the log-ratio paradigm

Background

While the theory of enzyme kinetics is fundamental to analyzing and simulating biochemical systems, the derivation of rate equations for complex mechanisms for enzyme-catalyzed reactions is cumbersome and error prone. Therefore, a number of algorithms and related computer programs have been developed to assist in such derivations. Yet although a number of algorithms, programs, and software packages are reported in the literature, one or more significant limitation is associated with each of these tools. Furthermore, none is freely available for download and use by the community.

Results

We have implemented an algorithm based on the schematic method of King and Altman (KA) that employs the topological theory of linear graphs for systematic generation of valid reaction patterns in a GUI-based stand-alone computer program called KAPattern. The underlying algorithm allows for the assumption steady-state, rapid equilibrium-binding, and/or irreversibility for individual steps in catalytic mechanisms. The program can automatically generate MathML and MATLAB output files that users can easily incorporate into simulation programs.

Conclusion

A computer program, called KAPattern, for generating rate equations for complex enzyme system is a freely available and can be accessed at http://www.biocoda.org.     

A graph-based reflexive artificial chemistry

The conceptual divide between formal systems of computation and abstract models of chemistry is considered. As an attempt to concretely bridge this divide, a formalism is proposed that describes a constructive artificial chemistry on a space of directed graph structures. The idea for the formalism originates in computer science theory, with the traditional abstraction of a physical machine, the finite-state machine (FSM). In the FSM, the machine (state-transition graph) and input string (series of binary digits) are fundamentally distinct objects, separated by nature of the underlying formalism. This distinction is dissolved in the proposed system, resulting in a construction process that is reflexive: graphs interact with their own topological structure to generate a product. It is argued that this property of reflexivity is a key element missing from earlier model chemistries. Examples demonstrate the continuous emergence complex self-similar topologies, novel reaction pathways, and seemingly open-ended diversity. Implications of these findings are discussed.     

XCSc: a novel approach to clustering with extended classifier system

In this paper, we propose a novel approach to clustering noisy and complex data sets based on the eXtend Classifier Systems (XCS). The proposed approach, termed XCSc, has three main processes: (a) a learning process to evolve the rule population, (b) a rule compacting process to remove redundant rules after the learning process, and (c) a rule merging process to deal with the overlapping rules that commonly occur between the clusters. In the first process, we have modified the clustering mechanisms of the current available XCS and developed a new accelerate learning method to improve the quality of the evolved rule population. In the second process, an effective rule compacting algorithm is utilized. The rule merging process is based on our newly proposed agglomerative hierarchical rule merging algorithm, which comprises the following steps: (i) all the generated rules are modeled by a graph, with each rule representing a node; (ii) the vertices in the graph are merged to form a number of sub-graphs (i.e. rule clusters) under some pre-defined criteria, which generates the final rule set to represent the clusters; (iii) each data is re-checked and assigned to a cluster that it belongs to, guided by the final rule set. In our experiments, we compared the proposed XCSc with CHAMELEON, a benchmark algorithm well known for its excellent performance, on a number of challenging data sets. The results show that the proposed approach outperforms CHAMELEON in the successful rate, and also demonstrates good stability.     

Spontaneous Mirror Symmetry Breaking in the Aldol Reaction and its Potential Relevance in Prebiotic Chemistry

The origin of the single chirality of most biomolecules is still a great puzzle. Carbohydrates could form in the formose reaction, which is proposed to be autocatalytic and contains aldol reaction steps. Based on our earlier observation of organoautocatalysis and spontaneous enantioenrichment in absence of deliberate chiral influences in the aldol reaction of acetone and p-nitrobenzaldehyde we suggest that a similar effect might be present also in the aldol reactions involved in gluconeogenesis. Herein we show that reactant precipitation observed in our earlier reported experiments does not affect the asymmetric autocatalysis in the aldol reaction we studied. We explain the phenomenon of spontaneous mirror symmetry breaking in such organocatalytic homogenous systems qualitatively by non-linear reaction network kinetics and classical transition state theory.     

Graph sharpening plus graph integration: a synergy that improves protein functional classification

MOTIVATION: Predicting protein function is a central problem in bioinformatics, and many approaches use partially or fully automated methods based on various combination of sequence, structure and other information on proteins or genes. Such information establishes relationships between proteins that can be modelled most naturally as edges in graphs. A priori, however, it is often unclear which edges from which graph may contribute most to accurate predictions. For that reason, one established strategy is to integrate all available sources, or graphs as in graph integration, in the hope that the positive signals will add to each other. However, in the problem of functional prediction, noise, i.e. the presence of inaccurate or false edges, can still be large enough that integration alone has little effect on prediction accuracy. In order to reduce noise levels and to improve integration efficiency, we present here a recent method in graph-based learning, graph sharpening, which provides a theoretically firm yet intuitive and practical approach for disconnecting undesirable edges from protein similarity graphs. This approach has several attractive features: it is quick, scalable in the number of proteins, robust with respect to errors and tolerant of very diverse types of protein similarity measures. RESULTS: We tested the classification accuracy in a test set of 599 proteins with remote sequence homology spread over 20 Gene Ontology (GO) functional classes. When compared to integration alone, graph sharpening plus integration of four vastly different molecular similarity measures improved the overall classification by nearly 30% [0.17 average increase in the area under the ROC curve (AUC)]. Moreover, and partially through the increased sparsity of the graphs induced by sharpening, this gain in accuracy came at negligible computational cost: sharpening and integration took on average 4.66 (+/-4.44) CPU seconds. AVAILABILITY: Software and Supplementary data will be available on http://mammoth.bcm.tmc.edu/     

Pattern computation in neural communication systems

Biological data suggests that activity patterns emerging in small- and large-scale neural systems may play an important role in performing the functions of the neural system, and in particular, neural computations. It is proposed in this paper that neural systems can be understood in terms of pattern computation and abstract communication systems theory. It is shown that analysing high-resolution surface EEG data, it is possible to determine abstract probabilistic rules that describe how emerging activity patterns follow earlier activity patterns. The results indicate the applicability of the proposed approach for understanding the working of complex neural systems.     

基于图自编码器和协同训练预测miRNA[]与疾病的关联

近年来,越来越多的生物学实验研究表明,microRNA (miRNA)在人类复杂疾病的发展中发挥着重要作用。因此,预测miRNA与疾病之间的关联有助于疾病的准确诊断和有效治疗。由于传统的生物学实验是一种昂贵且耗时的方式,于是许多基于生物学数据的计算模型被提出来预测miRNA与疾病的关联。本研究提出了一种端到端的深度学习模型来预测miRNA-疾病关联关系,称为MDAGAC。首先,通过整合疾病语义相似性,miRNA功能相似性和高斯相互作用谱核相似性,构建miRNA和疾病的相似性图。然后,通过图自编码器和协同训练来改善标签传播的效果。该模型分别在miRNA图和疾病图上建立了两个图自编码器,并对这两个图自编码器进行了协同训练。miRNA图和疾病图上的图自编码器能够通过初始关联矩阵重构得分矩阵,这相当于在图上传播标签。miRNA-疾病关联的预测概率可以从得分矩阵得到。基于五折交叉验证的实验结果表明,MDAGAC方法可靠有效,优于现有的几种预测miRNA-疾病关联的方法。     

Mathematical approaches to differentiation and gene regulation

We consider some mathematical issues raised by the modelling of gene networks. The expression of genes is governed by a complex set of regulations, which is often described symbolically by interaction graphs. These are finite oriented graphs where vertices are the genes involved in the biological system of interest and arrows describe their interactions: a positive (resp. negative) arrow from a gene to another represents an activation (resp. inhibition) of the expression of the latter gene by some product of the former. Once such an interaction graph has been established, there remains the difficult task to decide which dynamical properties of the gene network can be inferred from it, in the absence of precise quantitative data about their regulation. There mathematical tools, among others, can be of some help. In this paper we discuss a rule proposed by Thomas according to which the possibility for the network to have several stationary states implies the existence of a positive circuit in the corresponding interaction graph. We prove that, when properly formulated in rigorous terms, this rule becomes a theorem valid for several different types of formal models of gene networks. This result is already known for models of differential [C. Soulé, Graphic requirements for multistationarity, ComPlexUs 1 (2003) 123-133] or Boolean [E. Rémy, P. Ruet, D. Thieffry, Graphic requirements for multistability and attractive cycles in a boolean dynamical framework, 2005, Preprint] type. We show here that a stronger version of it holds in the differential setup when the decay of protein concentrations is taken into account. This allows us to verify also the validity of Thomas' rule in the context of piecewise-linear models. We then discuss open problems.     

Structure and Growth of the Leeward Kohala Field System: An Analysis with Directed Graphs

This study illustrates how the theory of directed graphs can be used to investigate the structure and growth of the leeward Kohala field system, a traditional Hawaiian archaeological site that presents an unparalleled opportunity to investigate relative chronology. The relative chronological relationships of agricultural walls and trails in two detailed study areas are represented as directed graphs and then investigated using graph theoretic concepts including cycle, level, and connectedness. The structural properties of the directed graphs reveal structure in the field system at several spatial scales. A process of deduction yields a history of construction in each detailed study area that is different than the history produced by an earlier investigation. These results indicate that it is now possible to study the structure and growth of the entire field system remnant using computer software implementations of graph theoretic concepts applied to observations of agricultural wall and trail intersections made on aerial imagery and/or during fieldwork. A relative chronology of field system development with a resolution of one generation is a possible result.     

Evolutionary games on cycles

Traditional evolutionary game theory explores frequency-dependent selection in well-mixed populations without spatial or stochastic effects. But recently there has been much interest in studying the evolutionary game dynamics in spatial settings, on lattices and other graphs. Here, we present an analytic approach for the stochastic evolutionary game dynamics on the simplest possible graph, the cycle. For three different update rules, called 'birth-death' (BD), 'death-birth' (DB) and 'imitation' (IM), we derive exact conditions for natural selection to favour one strategy over another. As specific examples, we consider a coordination game and Prisoner's Dilemma. In the latter case, selection can favour cooperators over defectors for DB and IM updating. We also study the case where the replacement graph of evolutionary updating remains a cycle, but the interaction graph for playing the game is a complete graph. In this setting, all three update rules lead to identical conditions in the limit of weak selection, where we find the '1/3-law' of well-mixed populations.     

Three dimensional DNA structures in computing

We show that 3-dimensional graph structures can be used for solving computational problems with DNA molecules. Vertex building blocks consisting of k-armed (k = 3 or 4) branched junction molecules are used to form graphs. We present procedures for the 3-SAT and 3-vertex-colorability problems. Construction of one graph structure (in many copies) is sufficient to determine the solution to the problem. In our proposed procedure for 3-SAT, the number of steps required is equal to the number of variables in the formula. For the 3-vertex-colorability problem, the procedure requires a constant number of steps regardless of the size of the graph.