On the use of qualitative reasoning to simulate and identify metabolic pathways

MOTIVATION: Perhaps the greatest challenge of modern biology is to develop accurate in silico models of cells. To do this we require computational formalisms for both simulation (how according to the model the state of the cell evolves over time) and identification (learning a model cell from observation of states). We propose the use of qualitative reasoning (QR) as a unified formalism for both tasks. The two most commonly used alternative methods of modelling biochemical pathways are ordinary differential equations (ODEs), and logical/graph-based (LG) models. RESULTS: The QR formalism we use is an abstraction of ODEs. It enables the behaviour of many ODEs, with different functional forms and parameters, to be captured in a single QR model. QR has the advantage over LG models of explicitly including dynamics. To simulate biochemical pathways we have developed 'enzyme' and 'metabolite' QR building blocks that fit together to form models. These models are finite, directly executable, easy to interpret and robust. To identify QR models we have developed heuristic chemoinformatics graph analysis and machine learning procedures. The graph analysis procedure is a series of constraints and heuristics that limit the number of ways metabolites can combine to form pathways. The machine learning procedure is generate-and-test inductive logic programming. We illustrate the use of QR for modelling and simulation using the example of glycolysis. AVAILABILITY: All data and programs used are available on request.     

Neural system modeling and simulation using Hybrid Functional Petri Net

The Petri net formalism has been proved to be powerful in biological modeling. It not only boasts of a most intuitive graphical presentation but also combines the methods of classical systems biology with the discrete modeling technique. Hybrid Functional Petri Net (HFPN) was proposed specially for biological system modeling. An array of well-constructed biological models using HFPN yielded very interesting results. In this paper, we propose a method to represent neural system behavior, where biochemistry and electrical chemistry are both included using the Petri net formalism. We built a model for the adrenergic system using HFPN and employed quantitative analysis. Our simulation results match the biological data well, showing that the model is very effective. Predictions made on our model further manifest the modeling power of HFPN and improve the understanding of the adrenergic system. The file of our model and more results with their analysis are available in our supplementary material.     

Load monitoring and system-traffic-aware live VM migration-based load balancing in cloud data center using graph theoretic solutions

This paper proposes solutions to monitor the load and to balance the load of cloud data center. The proposed solutions work in two phases and graph theoretical concepts are applied in both phases. In the first phase, cloud data center is modeled as a network graph. This network graph is augmented with minimum dominating set concept of graph theory for monitoring its load. For constructing minimum dominating set, this paper proposes a new variant of minimum dominating set (V-MDS) algorithm and is compared with existing construction algorithms proposed by Rooji and Fomin. The V-MDS approach of querying cloud data center load information is compared with Central monitor approach. The second phase focuses on system and network-aware live virtual machine migration for load balancing cloud data center. For this, a new system and traffic-aware live VM migration for load balancing (ST-LVM-LB) algorithm is proposed and is compared with existing benchmarked algorithms dynamic management algorithm (DMA) and Sandpiper. To study the performance of the proposed algorithms, CloudSim3.0.3 simulator is used. The experimental results show that, V-MDS algorithm takes quadratic time complexity, whereas Rooji and Fomin algorithms take exponential time complexity. Then the V-MDS approach for querying Cloud Data Center load information is compared with the Central monitor approach and the experimental result shows that the proposed approach reduces the number of message updates by half than the Central monitor approach. The experimental results show on load balancing that the developed ST-LVM-LB algorithm triggers lesser Virtual Machine migrations, takes lesser time and migration cost to migrate with minimum network overhead. Thus the proposed algorithms improve the service delivery performance of cloud data center by incorporating graph theoretical solutions in monitoring and balancing the load.     

Probability models and the applicability of statistical procedures in the identification of chromosomal fragile sites

Summary. Böhm et al. (1995, Human Genetics 95 , 249–256) introduced a statistical model (named FSM–fragile site model) specifically designed for the identification of fragile sites from chromosomal breakage data. In response to claims to the contrary (Hou et al., 1999, Human Genetics 104 , 350–355; Hou et al., 2001, Biometrics 57 , 435–440), we show how the FSM model is correctly modified for application under the assumption that the probability of random breakage is proportional to chromosomal band length and how the purportedly alternative procedures proposed by Hou, Chang, and Tai (1999, 2001) are variations of the correctly modified FSM algorithm. With the exception of the test statistic employed, the procedure described by Hou et al. (1999) is shown to be functionally identical to the correctly modified FSM and the application of an incorrectly modified FSM is shown to invalidate all of the comparisons of FSM to the alternatives proposed by Hou et al. (1999, 2001). Last, we discuss the statistical implications of the methodological variations proposed by Hou et al. (2001) and emphasize the logical and statistical necessity for fragile site identifications to be based on data from single individuals.     

A Memory-Efficient Deterministic Finite Automaton-Based Bit-Split String Matching Scheme Using Pattern Uniqueness in Deep Packet Inspection

This paper proposes a memory-efficient bit-split string matching scheme for deep packet inspection (DPI). When the number of target patterns becomes large, the memory requirements of the string matching engine become a critical issue. The proposed string matching scheme reduces the memory requirements using the uniqueness of the target patterns in the deterministic finite automaton (DFA)-based bit-split string matching. The pattern grouping extracts a set of unique patterns from the target patterns. In the set of unique patterns, a pattern is not the suffix of any other patterns. Therefore, in the DFA constructed with the set of unique patterns, when only one pattern can be matched in an output state. In the bit-split string matching, multiple finite-state machine (FSM) tiles with several input bit groups are adopted in order to reduce the number of stored state transitions. However, the memory requirements for storing the matching vectors can be large because each bit in the matching vector is used to identify whether its own pattern is matched or not. In our research, the proposed pattern grouping is applied to the multiple FSM tiles in the bit-split string matching. For the set of unique patterns, the memory-based bit-split string matching engine stores only the pattern match index for each state to indicate the match with its own unique pattern. Therefore, the memory requirements are significantly decreased by not storing the matching vectors in the string matchers for the set of unique patterns. The experimental results show that the proposed string matching scheme can reduce the storage cost significantly compared to the previous bit-split string matching methods.     

Recovery,visualization, and analysis of actin and tubulin polymer flow in live cells: a fluorescent speckle microscopy study

Fluorescent speckle microscopy (FSM) is becoming the technique of choice for analyzing in vivo the dynamics of polymer assemblies, such as the cytoskeleton. The massive amount of data produced by this method calls for computational approaches to recover the quantities of interest; namely, the polymerization and depolymerization activities and the motions undergone by the cytoskeleton over time. Attempts toward this goal have been hampered by the limited signal-to-noise ratio of typical FSM data, by the constant appearance and disappearance of speckles due to polymer turnover, and by the presence of flow singularities characteristic of many cytoskeletal polymer assemblies. To deal with these problems, we present a particle-based method for tracking fluorescent speckles in time-lapse FSM image series, based on ideas from operational research and graph theory. Our software delivers the displacements of thousands of speckles between consecutive frames, taking into account that speckles may appear and disappear. In this article we exploit this information to recover the speckle flow field. First, the software is tested on synthetic data to validate our methods. We then apply it to mapping filamentous actin retrograde flow at the front edge of migrating newt lung epithelial cells. Our results confirm findings from previously published kymograph analyses and manual tracking of such FSM data and illustrate the power of automated tracking for generating complete and quantitative flow measurements. Third, we analyze microtubule poleward flux in mitotic metaphase spindles assembled in Xenopus egg extracts, bringing new insight into the dynamics of microtubule assemblies in this system.     

Mathematical folding of node chains in a molecular network

Under the framework of network artificial chemistry (NAC), a method to construct a phenotypic machine from genotypic information is proposed. The genotype is expressed as a sequence of nodes (a node chain) with symbol data. According to an implemented algorithm, a chain is agglomerated, tangled, and finally folded into a node cluster that works as a control-flow machine in the network. Two examples of control-flow clusters, splitase and replicase, are presented and their functionality is demonstrated. Several meanings and future research directions are discussed.     

Uterine Synchronization Analysis During Pregnancy and Labor Using Graph Theory,Classification Based on Neural Network and Deep Learning

1) ObjectivesPreterm birth caused by preterm labor is one of the major health problems in the world. In this article, we present a new framework for dealing with this problem through the processing of electrohysterographic signals (EHG) that are recorded during labor and pregnancy. The objective in this research is to improve the classification between labor and pregnancy contractions by using a new approach that focuses on the connectivity analysis based on graph parameters, representative of uterine synchronization, and comparing neural network and machine learning methods in order to classify between labor and pregnancy.2) Material and methodsafter denoising of the 16 EHG signals recorded from pregnant women abdomen, we applied different connectivity methods to obtain connectivity matrices; then by using the graph theory, we extracted some graph parameters from the connectivity matrices; finally, we tested different neural network and machine learning methods on the features obtained from both graph and connectivity methods in order to classify between labor and pregnancy.3) ResultsThe best results were obtained by using the logistic regression method. We also evidence the power of graph parameters extracted from the connectivity matrices to improve the classification results.4) ConclusionThe use of graph analysis associated with machine learning methods can be a powerful tool to improve labor and pregnancy classification based on the analysis of EHG signals.     

The Relativistic Quantum Defect Orbital Method and some of its Applications

Justification of a simple and reliable relativistic procedure for the prediction of a large body of transition probability data is made. The main features of the Relativistic Quantum Defect Orbital (RQDO) formalism are described, and several examples of the data yielded by this method are presented in tabular and graph forms.     

Replacing soybean meal with flax seed meal: effects on nutrient digestibility,rumen microbial protein synthesis and growth performance in sheep

Flax seed meal (FSM) is rich in various nutrients, especially CP and energy, and can be used as animal protein feed. In animal husbandry production, it is a long-term goal to replace soybean meal (SBM) in animal feed with other plant protein feed. However, studies on the effects of replacing SBM with FSM in fattening sheep are limited. The aim of this experiment was to study the effects of replacing a portion of SBM with FSM on nutrient digestibility, rumen microbial protein synthesis and growth performance in sheep. Thirty-six Dorper × Small Thin-Tailed crossbred rams (BW = 40.4 ± 1.73 kg, mean ± SD) were randomly assigned into four groups. The dietary treatments (forage/concentrate, 45 : 55) were isocaloric according to the nutrient requirements of rams. Soybean meal was replaced with FSM at different levels (DM basis): (1) 18% SBM (18SBM), (2) 12% SBM and 6% FSM (6FSM), (3) 6% SBM and 12% FSM (12FSM) and (4) 18% FSM (18FSM). The rams were fed in individual pens for 60 days, with the first 10 days for adaptation to diets, and then the digestibility of nutrients was determined. There was no significant difference in DM intake, but quadratic (P < 0.001) effects on the average daily gain and feed efficiency were detected, with the highest values in the 6FSM and 12FSM groups. For DM and NDF digestibility, quadratic effects were observed with the higher values in the 6FSM and 12FSM groups, but the digestibility of CP linearly decreased with the increase in FSM in the diet (P = 0.043). There was a quadratic (P < 0.001) effect of FSM inclusion rate on the estimated microbial CP yield. However, the values of intestinally absorbable dietary protein decreased linearly (P < 0.001). For the supply of metabolisable protein, both the linear (P = 0.001) and quadratic (P = 0.044) effects were observed with the lowest value in the 18FSM group. Overall, the results indicated that SBM can be effectively replaced by FSM in the diets of fattening sheep and the optimal proportion was 12.0% under the conditions of this experiment.     

Positive circuits and d-dimensional spatial differentiation: application to the formation of sense organs in Drosophila

We discuss a rule proposed by the biologist Thomas according to which the possibility for a genetic network (represented by a signed directed graph called a regulatory graph) to have several stable states implies the existence of a positive circuit. This result is already known for different models, differential or discrete formalism, but always with a network of genes contained in a single cell. Thus, we can ask about the validity of this rule for a system containing several cells and with intercellular genetic interactions. In this paper, we consider the genetic interactions between several cells located on a d-dimensional lattice, i.e., each point of lattice represents a cell to which we associate the expression level of n genes contained in this cell. With this configuration, we show that the existence of a positive circuit is a necessary condition for a specific form of multistationarity, which naturally corresponds to spatial differentiation. We then illustrate this theorem through the example of the formation of sense organs in Drosophila.     

Live observation of forespore membrane formation in fission yeast

Sporulation in the fission yeast Schizosaccharomyces pombe is a unique biological process in that the plasma membrane of daughter cells is assembled de novo within the mother cell cytoplasm. A double unit membrane called the forespore membrane (FSM) is constructed dynamically during meiosis. To obtain a dynamic view of FSM formation, we visualized FSM in living cells by using green fluorescent protein fused with Psy1, an FSM-resident protein, together with the nucleus or microtubules. The assembly of FSM initiates in prophase II, and four FSMs in a cell expand in a synchronous manner at the same rate throughout meiosis II. After the meiosis II completes, FSMs continue to expand until closure to form the prespore, a spore precursor. Prespores are initially ellipsoidal, and eventually become spheres. FSM formation was also observed in the sporulation-deficient mutants spo3, spo14, and spo15. In the spo15 mutant, the initiation of FSM formation was completely blocked. In the spo3 mutant, the FSM expanded normally during early meiosis II, but it was severely inhibited during late and postmeiosis, whereas in the spo14 mutant, membrane expansion was more severely inhibited throughout meiosis II. These observations suggest that FSM expansion is composed of two steps, early meiotic FSM expansion and late and post meiotic FSM expansion. Possible regulatory mechanisms of FSM formation in fission yeast are discussed.     

发酵豆粕对大黄鱼生长、肠道结构及肠道微生物菌群的研究

以鱼粉和小麦蛋白粉为蛋白源, 配制成6种等氮等脂(粗蛋白45%; 粗脂肪10%)的饲料, 研究其对大黄鱼(Larimichthys Crocea)幼鱼生长、肠道组织结构及肠道微生物菌群的影响。这6种饲料是以发酵豆粕分别替代基础饲料(含40%鱼粉)中0 (FSM0, 对照组)、15% (FSM15)、30% (FSM30)、45% (FSM45)、60% (FSM60)和75% (FSM75)的鱼粉制作而成。经过56d的生长实验, 结果表明, 饲料中随着发酵豆粕替代比例的升高, 各处理组大黄鱼幼鱼(10.49±0.03) g的存活率无显著性差异(P>0.05), 但FSM60和FSM75组有下降趋势; 相比FSM0组, FSM60和FSM75组的特定生长率(SGR)和增重率(WGR)显著降低(P<0.05), 饲料系数(FCR)显著升高(P<0.05); 摄食率(FI) FSM 60和FSM 75组显著高于FSM0、FSM15、FSM30和FSM45组(P<0.05)。肠道组织结构研究发现, 各处理组肠道组织结构后肠黏膜、皱襞高度、固有膜宽度和杯状细胞个数均无显著性差异(P>0.05)。Illumina-Mi Seq高通量测序技术分析发现, FSM0 (TC对照组)、FSM45 (TB最佳生长组)和FSM75 (TW最差生长组)组Chao1、香农指数(Shannon)、辛普森指数(Simpson)和覆盖率(Good coverage)均无显著性差异(P>0.05); 基于门水平, TC、TB和TW组大黄鱼幼鱼肠道优势菌群为厚壁菌门(Firmicutes); 而在属水平, 类芽孢杆菌(Paenibacillus)占绝对优势。从属水平差异菌属研究发现, 发酵豆粕对大黄鱼幼鱼肠道菌群有一定的影响: 与最差生长组(TW)相比, 最佳生长组(TB)和对照组(TC)均显著增加了类芽孢杆菌(Paenibacillus)和嗜碱菌属(Alkaliphilus)的物种丰度(P<0.05); 与TW组相比, TB组水栖菌属(Enhydrobacter)和TC组副球菌属(Paracoccus)的物种丰度均显著降低(P<0.05)。结果表明, 发酵豆粕替代鱼粉达45%时对大黄鱼幼鱼的生长、肠道组织结构及肠道优势菌群没有负面影响, 即发酵豆粕替代饲料(含40%鱼粉)中45%的鱼粉较为适宜。     

The fission yeast pleckstrin homology domain protein Spo7 is essential for initiation of forespore membrane assembly and spore morphogenesis

Sporulation in fission yeast represents a unique mode of cell division in which a new cell is formed within the cytoplasm of a mother cell. This event is accompanied by formation of the forespore membrane (FSM), which becomes the plasma membrane of spores. At prophase II, the spindle pole body (SPB) forms an outer plaque, from which formation of the FSM is initiated. Several components of the SPB play an indispensable role in SPB modification, and therefore in sporulation. In this paper, we report the identification of a novel SPB component, Spo7, which has a pleckstrin homology (PH) domain. We found that Spo7 was essential for initiation of FSM assembly, but not for SPB modification. Spo7 directly bound to Meu14, a component of the leading edge of the FSM, and was essential for proper localization of Meu14. The PH domain of Spo7 had affinity for phosphatidylinositol 3-phosphate (PI3P). spo7 mutants lacking the PH domain showed aberrant spore morphology, similar to that of meu14 and phosphatidylinositol 3-kinase (pik3) mutants. Our study suggests that Spo7 coordinates formation of the leading edge and initiation of FSM assembly, thereby accomplishing accurate formation of the FSM.     

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.     

Machine Learning Assisted Design of Highly Active Peptides for Drug Discovery

The discovery of peptides possessing high biological activity is very challenging due to the enormous diversity for which only a minority have the desired properties. To lower cost and reduce the time to obtain promising peptides, machine learning approaches can greatly assist in the process and even partly replace expensive laboratory experiments by learning a predictor with existing data or with a smaller amount of data generation. Unfortunately, once the model is learned, selecting peptides having the greatest predicted bioactivity often requires a prohibitive amount of computational time. For this combinatorial problem, heuristics and stochastic optimization methods are not guaranteed to find adequate solutions. We focused on recent advances in kernel methods and machine learning to learn a predictive model with proven success. For this type of model, we propose an efficient algorithm based on graph theory, that is guaranteed to find the peptides for which the model predicts maximal bioactivity. We also present a second algorithm capable of sorting the peptides of maximal bioactivity. Extensive analyses demonstrate how these algorithms can be part of an iterative combinatorial chemistry procedure to speed up the discovery and the validation of peptide leads. Moreover, the proposed approach does not require the use of known ligands for the target protein since it can leverage recent multi-target machine learning predictors where ligands for similar targets can serve as initial training data. Finally, we validated the proposed approach in vitro with the discovery of new cationic antimicrobial peptides. Source code freely available at http://graal.ift.ulaval.ca/peptide-design/.     

The fragment assembly string graph

We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes.     

Mapping multivalued onto Boolean dynamics

This paper deals with the generalized logical framework defined by René Thomas in the 70's to qualitatively represent the dynamics of regulatory networks. In this formalism, a regulatory network is represented as a graph, where nodes denote regulatory components (basically genes) and edges denote regulations between these components. Discrete variables are associated to regulatory components accounting for their levels of expression. In most cases, Boolean variables are enough, but some situations may require further values. Despite this fact, the majority of tools dedicated to the analysis of logical models are restricted to the Boolean case. A formal Boolean mapping of multivalued logical models is a natural way of extending the applicability of these tools.Three decades ago, a multivalued to Boolean variable mapping was proposed by P. Van Ham. Since then, all works related to multivalued logical models and using a Boolean representation rely on this particular mapping. We formally show in this paper that this mapping is actually the sole, up to cosmetic changes, that could preserve the regulatory structures of the underlying graphs as well as their dynamical behaviours.