Search

This chapter aims to introduce some of the basics of modeling with ODEs in biology. We focus on computational, numerical techniques, rather than on symbolic ones. We restrict our attention to reaction-based models, where the biological interactions are mechanistically described in terms of reactions, reactants and products. We discuss how to build the ODE model associated to a reaction-based model; how to fit it to experimental data and estimate the quality of its fit; how to calculate its steady state(s), mass conservation relations, and its sensitivity coefficients. We apply some of these techniques to a model for the heat shock response in eukaryotes.

Model refinement is an important aspect of the model-building process. It can be described as a procedure which, starting from an abstract model of a system, performs a number of refinement steps in result of which a more detailed model is obtained. At the same time, in order to be correct, the refinement mechanism has to be capable of preserving already proven systemic quantitative properties of the original model, e.g. model fit, stochastic semantics, etc. In this study we concentrate on the refinement in the case of self-assembly models. Self-assembly is a process in which a disordered ensemble of basic components forms an organized structure as a result of specific, local interactions among these components, without external guidance. We develop a generic formal model for this process and introduce a notion of model resolution capturing the maximum size up to which objects can be distinguished individually in the model. All bigger objects are treated homogenously in the model. We show how this self-assembly model can be systematically refined in such a way that its resolution can be increased and decreased while preserving the original model fit to experimental data, without the need for tedious, computationally expensive process of parameter refitting. We demonstrate how the introduced methodology can be applied to a previously published model: we consider the case-study of in vitro self-assembly of intermediate filaments.

Ciliates are a very diverse and ancient group of unicellular eukaryotic organisms. A feature that is essentially unique to ciliates is the nuclear dualism, meaning that they have two functionally different types of nuclei, the macronucleus and the micronucleus. During sexual reproduction a micronucleus is transformed into a macronucleus – this process is called gene assembly, and it is the most involved naturally occurring example of DNA processing that is known to us. Gene assembly is a fascinating research topic from both the biological and the computational points of view. In this chapter, several approaches to the computational study of gene assembly are considered. This chapter is self-contained in the sense that the basic biology of gene assembly as well as mathematical preliminaries are introduced. Two of the most studied molecular models for gene assembly, intermolecular and intramolecular, are presented and the main mathematical approaches used in studying these models are discussed. The topics discussed in more detail include the string and graph rewriting models, invariant properties, template-based DNA recombination, and topology-based models. This chapter concludes with a brief discussion of a number of research topics that, because of the space restrictions, could not be covered in this chapter.

We present in this paper a novel molecular model for the gene regulatory network responsible for the eukaryotic heat shock response. Our model includes the temperature-induced protein misfolding, the chaperone activity of the heat shock proteins, and the backregulation of their gene transcription. We then build a mathematical model for it, based on ordinary differential equations. Finally, we discuss the parameter fit and the implications of the sensitivity analysis for our model.

We concentrate in this chapter on the core aspects of algebraic series, pushdown automata, and their relation to formal languages. We choose to follow here a presentation of their theory based on the concept of properness. We introduce in Sect. 2 some auxiliary notions and results needed throughout the chapter, in particular the notions of discrete convergence in semirings and C-cycle free infinite matrices. In Sect. 3 we introduce the algebraic power series in terms of algebraic systems of equations. We focus on interconnections with context-free grammars and on normal forms. We then conclude the section with a presentation of the theorems of Shamir and Chomsky–Schutzenberger. We discuss in Sect. 4 the algebraic and the regulated rational transductions, as well as some representation results related to them. Section 5 is dedicated to pushdown automata and focuses on the interconnections with classical (non-weighted) pushdown automata and on the interconnections with algebraic systems. We then conclude the chapter with a brief discussion of some of the other topics related to algebraic systems and pushdown automata.

Computational Models for Cell Processes.- Process Algebra Modelling Styles for Biomolecular Processes.- Simple, Enhanced and Mutual Mobile Membranes.- Bio-PEPA with Events.- In Silico Modelling and Analysis of Ribosome Kinetics and aa-tRNA Competition.- Qualitative and Quantitative Analysis of a Bio-PEPA Model of the Gp130/JAK/STAT Signalling Pathway.- Rule-Based Modelling and Model Perturbation.- Extended Stochastic Petri Nets for Model-Based Design of Wetlab Experiments.- A Projective Brane Calculus with Activate, Bud and Mate as Primitive Actions.- Accepting Networks of Non-inserting Evolutionary Processors.- Discrete Modeling of Biochemical Signaling with Memory Enhancement.- Dynamical Systems and Stochastic Programming: To Ordinary Differential Equations and Back.- Computing Equilibrium Points of Genetic Regulatory Networks.- Code, Context, and Epigenetic Catalysis in Gene Expression.

Elevated temperatures cause proteins in living cells to misfold. They start forming larger and larger aggregates that can eventually lead to the cell's death. The heat shock response is an evolutionary well conserved cellular response to massive protein misfolding and it is driven by the need to keep the level of misfolded proteins under control. We consider in this paper a recently proposed new molecular model for the heat shock response in eukaryotes, consisting of a temperature-induced activation mechanism, chaperoning of misfolded proteins and self-regulation of the chaperon synthesis. We take in this paper a control driven approach to studying this regulatory network. We modularize the network by identifying its main functional modules. We distinguish three main feedback loops. The main question we are addressing is why is this level of complexity needed for implementing what could in principle also be achieved with an open-loop design. We answer the question by comparing the numerical behavior of various knockdown mutants where one or more feedback loops are missing. We also discuss a new approach for a biologically-unbiased model comparison.

Natural Computing is a research area concerned with computing taking place in nature and with human-designed computing inspired by nature. It is a fast growing, genuinely interdisciplinary field involving, among others, biology, mathematics and computer science. Graphs and graph transformations are of great interest in this field in several respects. On the one hand, graphs are often used in the modeling of natural processes either as a representation of the hierarchical structures involved in the process or as a way to formalize the features of reality on several levels of abstraction. Several graph related formalisms such as Petri nets, abstract state machines, automata, membrane systems, mobile ambients, etc., are already used as modeling tools for natural processes. On the other hand, in human-designed computing inspired by nature, graph theoretical formulations and problems are often used as benchmarks for the investigation of the potential of the proposed computational paradigms.

Gene assembly in ciliates is an impressive computational process. Ciliates have a unique way of storing their genetic information in two fundamentally different forms within their two types of nuclei. Micronuclear genes are broken into blocks (called MDSs), with MDSs shuffled and separated by non-coding material; some of the MDSs may even be inverted. During gene assembly, all MDSs are sorted in the correct order to yield the transcription-able macronuclear gene. Based on the intramolecular model for gene assembly, we prove in this paper that gene assembly may be used in principle to solve computational problems. We prove that any given instance of the hamiltonian path problem may be encoded in a suitable way in the form of an 'artificial' gene so that gene assembly is successful on that gene-like pattern if and only if the given problem has an affirmative answer.

The simple intramolecular model for gene assembly in ciliates is particularly interesting because it can predict the correct assembly of all available experimental data, although it is not universal. The simple model also has a confluence property that is not shared by the general model. A previous formalization of the simple model through sorting of signed permutations is unsatisfactory because it effectively ignores one operation of the model and thus, it cannot be used to answer questions about parallelism in the model, or about measures of complexity. We propose in this paper a string-based model in which a gene is represented through its sequence of pointers and markers and its assembly is represented as a string rewriting process. We prove that this stringbased model is equivalent to the permutation-based model as far as gene assembly is concerned, while it tracks all operations of the model.

The intramolecular gene assembly model, [1], uses three molecular recombination operations ld, dlad, and hi. A computing model with two contextual recombination operations del and trl, which are based on ld and dlad, respectively, is considered in [6] and its computational power is investigated. In the present paper, we expand the computing model with a new molecular operation such as cpy - copy. Then we prove that the extended contextual intramolecular gene assembly model is both computationally universal and efficient.

The process of gene assembly in ciliates is a fascinating example of programmed DNA manipulations in living cells. Macronuclear genes are split into coding blocks (called MDSs), shuffled and separated by non-coding sequences to form micronuclear genes. Assembling the coding blocks from micronuclear genes to form functional macronuclear genes is facilitated by an impressive in-vivo implementation of the linked list data structure of computer science. Complexity measures for genes may be defined in many ways, including the number of MDSs, the number of loci, etc. We take a different approach in this paper and propose four complexity measures for genes in ciliates, based on the 'effort' required to assemble the gene. We consider: (a) the types of operations used in the assembly, (b) the number of operations used in the assembly, (c) the length of the molecular folds involved, and (d) the length of the shortest possible parallel assembly for that gene. "One of the oldest forms of life on Earth has been revealed as a natural born computer programmer."

The intramolecular model for gene assembly in ciliates considers three operations, ld, hi, and dlad that can assemble any gene pattern through folding and recombination: the molecule is folded so that two occurrences of a pointer (short nucleotide sequence) get aligned and then the sequence is rearranged through recombination of pointers. In general, the sequence rearranged by one operation can be arbitrarily long and consist of many coding and non-coding blocks. We consider in this paper some simpler variants of the three operations, where only one coding block is rearranged at a time. We characterize in this paper the gene patterns that can be assembled through these variants. Our characterization is in terms of signed permutations and dependency graphs. Interestingly, we show that simple assemblies possess rather involved properties: a gene pattern may have both successful and unsuccessful assemblies and also more than one successful assembling strategy.

DNA computing, or more generally molecular computing, is an exciting research area at the intersection of mathematics, computer science and molecular biology. Research in DNA computing can be roughly divided in two streams: DNA computing in vitro and in vivo. The former is concerned with building (specialized) DNA-based computers in test tubes, while the latter is concerned with implementing some computational components in living cells, as well as with studying the computational processes taking place in the living cells.

All organisms are composed of cells. Some organisms, like an amoeba or a bacterium, consist of a single cell (unicellular organisms). Plants and animals consist of a few hundred to many trillions of cells (multicellular organisms). The structures common to cells and the molecular principles on which cells operate are described in this chapter. The structures and functions of cells are prescribed by genes contained in the DNA molecules of chromosomes. The genetic information in DNA is transcribed into RNA molecules, which in turn are translated into protein molecules. Protein molecules are the principal molecules that prescribe cell structures and functions. Cells duplicate by growing and replicating the DNA in their chromosomes. They distribute the duplicated copies of chromosomes (DNA) to daughter cells, which form by pinching of a cell into two cells.

In Chap. 9 we showed that all legal strings are reducible to the empty string by a finite number of applications of the string rules snr, spr, and sdr corresponding to the molecular operations ld, hi, and dlad. In particular, this is true for all realistic legal strings. A central question for understanding the role of this set of operations in the process of assembly is the following. What kind of realistic MDS arrangements (corresponding to realistic legal strings) can be successfully assembled by various subsets of this set?

In Chap. 6 we formalized the MDS structure of micronuclear and intermediate genes through NIDS arrangements and MDS descriptors. In this chapter we shall continue to consider the framework of MDS descriptors. In particular, we shall formalize in this framework the use of the three molecular operations ld, hi, and dlad for gene assembly introduced in Chap. 3. Thus, these operations will be formalized as operations on (rewriting rules for) MDS descriptors. We also prove that this formal model is universal, i.e., every (realistic) MDS descriptor can be reduced to the MDS descriptor (b, e) or its inverse \(\left( {\bar e,\bar b} \right)\) by these three operations.

In this chapter we shall introduce two formalizations of the MDS structure of genes, viz., MDS arrangements and MDS descriptors. MDS arrangements result from representing each elementary or composite MDS by its own symbol, and then by representing the MDS structure of a micronuclear or an intermediate gene by the string of symbols corresponding to the sequence of MDSs. On the other hand. MDS descriptors follow the key observation concerning gene assembly (stated in Chap. 2) that it is not the whole structure of MDSs but only their repeat sequences (pointers) that guide gene assembly. Therefore, in the framework of MDS descriptors each MDS is represented by the pair of its pointers, with each pointer represented by its own symbol. Correspondingly, the IUS descriptor of a micronuclear or an intermediate gene is the string of pairs of pointers corresponding to the sequence of MDSs.

We can only speculate about the significance of the extraordinary modifications in the structure of micronuclear genes in stichotrichous ciliates that have occurred during evolution. However, it is clear the presence of IESs and MDSs, and particularly the scrambling of MDSs in micronuclear genes, requires spectacular manipulations of DNA sequences whenever cells mate and then develop new macronuclei. These DNA manipulations are massive, consisting of the excision of more than 100,000 IESs and reordering of many thousands of MDSs. Major progress in understanding this intricate DNA processing has been made by studying the nucleotide sequences in micronuclear genes. The excision of IESs and the unscrambling and joining of MDSs are referred to as gene assembly. In this chapter we postulate three molecular operations based on the pairs of repeats in the ends of MDSs to accomplish the assembling of genes after cell mating. In the description of these three operations the pairs of repeats are called pointers because they point the way for MDS joining.

In Chap. 10 we represented MDS structure of micronuclear and intermediate genes as graphs. In this chapter we continue this line of formalization by representing the gene assembly process in the framework of graphs. Thus, we shall formalize now the three molecular operations Id, hi,and dlad as operations (rewriting rules) on overlap graphs, obtaining in this way graph pointer reduction systems. Although the transition from legal strings to overlap graphs represents a considerable increase in abstraction (indeed, the linear structure of legal strings is lost!), we prove that the graph pointer reduction system is equivalent to the string pointer reduction system as far as strategies for gene assembly are concerned.

The gene assembly process that transforms the micronuclear genome to the macronuclear genome in stichotrichs ciliates is a complex DNA processing which is very interesting from the computational point of view. We shall give a survey of the notions and results concerning three molecular operations, known as ld, hi, and dlad, that have been postulated to accomplish the gene assembly process. These operations are modelled on three abstraction levels: MDS descriptors, legal strings, and overlap graphs. It turns out that these three abstractions are equivalent as far as the operational modelling of gene assembly is concerned.

In Chap. 8 we formalized the MDS structure of micronuclear and intermediate genes through legal strings. In this chapter we shall formalize the gene assembly process in the framework of legal strings. Thus, we shall now formalize the three molecular operations ld, hi, and dlad as operations on (rewriting rules for) legal strings, obtaining string pointer reduction systems. Although the transition from MDS descriptors to legal strings represents an increase in abstraction (we only preserve in legal strings the sequence of pointers), we prove that string pointer reduction systems are equivalent to MDS descriptor pointer reduction systems as far as the strategies for gene assembly are concerned.

Two models for gene assembly in ciliates have been proposed and investigated in the last few years. The DNA manipulations postulated in the two models are very different: one model is intramolecular – a single DNA molecule is involved here, folding on itself according to various patterns, while the other is intermolecular – two DNA molecules may be involved here, hybridizing with each other. Consequently, the assembly strategies predicted by the two models are completely different. Interestingly however, the final result of the assembly (including the assembled gene) is always the same. We compare in this paper the two models for gene assembly, formalizing both in terms of pointer reductions. We also discuss invariants and universality results for both models.

Gene assembly in ciliates is a life process fascinating from both the biological and the computational points of view. Several formal models of this process have been formulated and investigated, among them a model based on (legal) strings and a model based on (overlap) graphs. The latter is more abstract because the translation of legal strings into overlap graphs is not injective. In this paper we consider and solve the overlap equivalence problem for realistic strings: when do two different realistic legal strings translate into the same overlap graph? Realistic legal strings are legal strings that “really” correspond to genes generated during the gene assembly process.

The process of gene assembly in ciliates is one of the most complex examples of DNA processing known in any organism, and it is fascinating from the computational point-of-view -- it is a prime example of DNA computing in vivo. In this paper we continue to investigate the three molecular operations (ld, hi, and dlad) that were postulated to carry out the gene assembly process in the intramolecular fashion. In particular, we focus on the understanding of the IES/MDS patterns of micronuclear genes, which is one of the important goals of research on gene assembly in ciliates. We succeed in characterizing for each subset S of the three molecular operations those patterns that can be assembled using operations in S. These results enhance our understanding of the structure of micronuclear genes (and of the nature of molecular operations). They allow one to establish both similarity and complexity measures for micronuclear genes.

DNA computing, or more generally molecular computing, is a novel exciting area of research at the intersection of mathematics, computer science and molecular biology. The area of DNA computing studies the use of biomolecules for the purpose of computing (in vitro or in vivo). Molecular biologists assists here computer scientists in their attempt to replace or to complement the silicon-based computers by DNA-based computers. The hardware for such computations consists of biomolecules ( bioware).

We prove two results on commutation of languages. First, we show that the maximal language commuting with a three element language, i.e. its centralizer, is rational, thus giving an affirmative answer to a special case of a problem proposed by Conway in 1971. Second, we characterize all languages commuting with a three element code. The characterization is similar to the one proved by Bergman for polynomials over noncommuting variables, cf. Bergman, 1969 and Lothaire, 2000: A language commutes with a three element code X if and only if it is a union of powers of X.

International audience; This tutorial surveys computational aspects of cellular automata, a discrete dynamical model introduced by S. Ulam and J. von Neumann in the late 40s: a regular grid of finite state cells evolving synchronously according to a common local rule described by a finite automaton.