\chapter{Introduction}
Complex Adaptive Systems (CAS) are dynamical networks of interacting agents which as a whole determine the behaviour, adaptivity and cognitive ability of the system \citep{holland1992cas}. CAS are ubiquitous and occur in a variety of natural and artificial systems (e.g., biological cells, stock markets, the biosphere). Realising and evolving CAS \textit{in silico} may provide new critical tools for understanding, predicting and building CAS.

However modelling and evolving CAS remains problematic as the traditional analytical and statistical approaches (which may be coupled with Evolutionary Computation techniques) appear to limit the study of CAS \citep{holland2006}. Indeed no computational techniques have to date successfully supported open-ended evolution as occurring in \textit{natural} CAS. Achieving open-ended evolution is a critical problem which is related to many other grand challenges in the field of Artificial Life \citep{bedau2000opa,Gershenson2008}.

This thesis addresses one aspect of this issue on the evolutionary growth of complexity by examining the significance of autocatalytic closure for the evolution of CAS complexity. A specific subclass of CAS is addressed in this investigation: Cellular Information Processing Networks (CIPNs) which are chemical networks occurring in living cells capable of information processing. This thesis examines the evolution of organisationally closed CIPNs \textit{in-silico}.

The remainder of this chapter is organised as follows. A presentation of autocatalytic closure (a concept originating from Kaufffman's autocatalytic set theory) is first provided. A brief description of CIPNs is then given. Finally the potential applications, aims, objectives and layout of this thesis are enumerated.

\section{Autocatalytic set theory}
The autocatalytic set theory was proposed by \cite{kauffman1993oos} to explain the emergence and early evolution of life. An autocatalytic set is a collection of molecular species where each is capable of supporting the catalysis of another species in the set. It is argued that given a critical mass of molecular species, the spontaneous emergence and self-organisation of an autocatalytic set may occur.

Although individual species are not capable of self-replication, \textit{a contrario} to RNA world models \citep{gilbert1986rw,gesteland2005rw} or hypercycles \citep{eigen1971sma, eigen1977pns}, the set of species as a whole is able to catalyse its own production. Such a molecular set or reaction network is said to be \textit{collectively} autocatalytic/self-replicating, see Fig. \ref{fig:autocataSet}.

\begin{figure}[htbp]
	\centering
		\includegraphics{chapter1/autocataSet.eps}
	\caption{A: A simple collectively autocatalytic reaction network. The species $x_1$ catalyses the production of $x_2$. Similarly the production of $x_3$ and $x_1$ can be catalysed by $x_2$ and $x_3$ respectively, forming/closing the autocatalytic loop. B: A three element hypercycle, in contrast to collectively autocatalytic reaction networks, individual molecular species are capable of self-production in hypercycles.}
	\label{fig:autocataSet}
\end{figure}


An autocatalytic set is organisationally closed when the production of each species contained in the set may be catalysed by another member of the set. This \textit{virtuous} catalytic cycle enables a ``closed set'' to self-maintain/repair when subjected to internal and external perturbations and during cellular divisions (e.g., molecular mutations, removal/addition of molecular species through diffusion) given a continuous inflow of ``food molecules''.  

Kauffman argued that self-organisation and autocatalytic closure are key principles allowing the spontaneous emergence and maintenance of order given an original chaotic system. When subjected to a Darwinian evolutionary regime where natural selection and variation/heredity of phenotypic traits may occur, closed reaction networks may evolve and \textit{gradually} grow in structural and functional complexity leading to higher-order organisms. 

Although the autocatalytic set theory was initially proposed to address biological organisations, it has also been metaphorically extended to the study of social and economic systems \citep{gabora2008ces,kauffman1997hu}. 

\section{Cellular Information Processing Networks}
Cellular Information Processing Networks (CIPNs) are biochemical systems of interacting molecules occurring in living cells. CIPNs are responsible for coordinating the cellular activities in response to internal and external stimuli.

As signal processing systems, CIPNs can be regarded as special purpose computers \citep{bray1995pmc}. In contrast to conventional silicon-based computers, the information processing in CIPNs is not realised by electronic circuits, but by chemically reacting molecules in the cell. There is an almost infinite variety of potential molecular species, each of which would have distinct chemical functionality and could engage in interactions with other molecules with varying degrees of specificity.

An example of CIPN are Cell Signalling networks\footnote{The work presented in this thesis was funded by the ESIGNET project (Evolving Cell Signalling Networks \textit{in silico}, a European Integrated Project in the EU FP6 NEST initiative, contract no. 12789). The ESIGNET project aimed at realising and evolving artificial cell signalling networks to perform computational functions.} \citep{Helmreich,Krauss2003} such as the chemotaxis signalling pathway \citep{stock1992stb} which may occur in simple organisms (e.g., bacteria). This CIPN enables bacteria to move toward higher concentrations of specific chemicals or flee from toxic chemicals in their surroundings. this

In the simplest cases, CIPNs can be approximately modelled by systems of continuous differential equations, where the state variables are the concentrations of the distinct species of interacting molecules.  As an ``information processing'' device, this is most naturally compared to a traditional \emph{analog} computer. Analog computers are precisely designed to model the operation of a target dynamical system, by creating an ``analogous'' system
which shares (approximately) the same dynamics.  Electronic analog computers (based on the ``operational amplifier'' as the core computational device) have long been displaced by digital computers, programmed to numerically solve the relevant dynamical equations, due to their much greater ease of programming and
stability.  

While CIPNs are typically treated in this ``aggregate'' manner, where the information is carried by molecular concentration, one can also consider the finer grained behaviours of individual molecules which are computational in nature. Thus a single enzyme molecule can be regarded as carrying out pattern matching to identify and bind target substrates, and then executing a discrete computational operation in transforming these into the product molecule(s).  This has clear parallels with a wide variety of so-called ``rewriting systems'' in computational theory. However, it also clearly differs in important ways, such as:
\begin{itemize}
\item Operation is stochastic rather than deterministic.
\item Operation is intrinsically \emph{reflexive} in that all
  molecules can, in principle, function as both ``rules''
  (enzymes) and ``strings'' (substrates/products).
\end{itemize}
\cite{DBLP:conf/upp/Dittrich04} provides a more extended
discussion of the potential of such ``chemical computing''.

In this thesis, we hypothesise that CIPNs can be considered as subsets of organisationally closed reaction networks. A motivation for this hypothesis is that closure properties may be necessary to ensure the self-maintenance and robustness of CIPNs when subjected to internal and external perturbations and during cellular divisions. 

Moreover by exploiting the principles of Darwinian evolution, it is intended to evolve closed chemical networks of higher complexity which are capable of performing information processing tasks distinctive of CIPNs.
 
\section{Applications}
\label{sec:benefits}
The potential applications of realising and evolving CIPNs include:
\begin{itemize}
	\item \textit{Engineering crosstalk:} A natural phenomenon occurring in CIPNs called ``crosstalk" and its potential contributions to engineering are discussed. Crosstalk occurs when signals from different pathways become mixed together. This arises very naturally in CIPNs due to the fact that the molecules from all pathways may share the same physical reaction space (the cell). Depending on the relative specificities of the reactions there is then an automatic potential for any given molecular species to contribute to signal levels in multiple pathways. In traditional communications and signal processing engineering, crosstalk is regarded as a defect: an \emph{unintended} interaction between signals, that therefore has the potential to cause system malfunction.  This can also clearly be the case with crosstalk in real biochemical networks, for example cells may become cancerous due to undesired crosstalk connections \citep{pmid16230365,pmid10791773}. However, in the specific case of CIPN's, crosstalk also has additional potential functionalities, which may actually be constructive:

\begin{itemize}
\item Even where an interfering signal is, in effect, adding uncorrelated ``noise'' to a functional signal, this may sometimes improve the overall system behaviour. This is well known in conventional control systems engineering in the form of so-called ``dither'' \citep{korn1956eac}. Molecular biologists indicated that noise is an inevitable by-product of inherent molecular interactions, and that in fact noise is essential for development  \citep{citeulike:447368}. 

\item The crosstalk mechanism may also provide a very generic way of creating a large space of possible modifications or interactions between chemical pathways. Thus, although many cases of crosstalk may be immediately negative in their impact, crosstalk may still be a key mechanism in enabling incremental evolutionary search for more elaborate or complex CIPNs. For example, \cite{genoud1999} presented a number of crosstalk connections between real biochemical networks occurring in plants in which these ``interferences" provided a relatively \textit{rapid} and \textit{efficient} mechanism for optimizing non-cognitive behaviour in response to various combinations of stimuli. Crosstalk may also provide the necessary signal that enables desired outcome to occur, an example of this could be coordinating the cell cycle \citep{citeulike:488811}. 
\end{itemize}
Both above cases of crosstalk may give new insights on the use of crosstalk in control engineering.


	\item \textit{CIPNs as information processing devices}: Nature is a source of inspiration for information processing techniques which have been successfully applied to a wide variety of complex application domains. In keeping with this we examine the possibility of utilising CIPNs for information processing purposes. Realising and evolving artificial CIPNs may provide new computational paradigms for a variety of application areas. Early work conducted by \cite{bray1995pmc} showed that molecules could be regarded as information processing devices, these molecules would perform simple computational tasks. Examples of such information processing functions are: signal acceleration \citep{mangan2003saf}, signal amplification \citep{binder2004ibd} or decision making \citep{xiong2003pfb}. A review on the computational abilities of signalling networks can be found in \cite{sauro2004cvp}. Identified information processing processes occurring in CIPNs indicate that complex operational features have been designed in CIPNs through natural evolution. Moreover, there may be applications where a molecular level analog computer, in the form of a CIPN, may have distinct advantages.  Specifically, CIPNs may offer high speed and small size that cannot be realised with solid state electronic technology. More critically, where it is required to interface information processing with chemical interaction, a CIPN may bypass difficult stages of signal transduction that would otherwise be required.  This could have direct application in so-called ``smart drugs'' and other bio-medical interventions.

	\item \textit{Open-ended evolution:} Our project finally addresses the conditions allowing open-ended evolution to occur. Achieving an open-ended growth of complexity is a long-standing grand challenge related to the evolution of artificial systems \citep{bedau2000opa}. Although many computational evolutionary techniques have been proposed to evolve artificial systems, no systems have to date managed to support the open-ended evolutionary growth of complexity as occurring in the real world. Evolutionary systems would typically plateau and avert the perpetual emergence of complex behaviours \citep{860359}. 
	
	Understanding the key components\footnote{Example key components are the fitness functions devised in evolutionary systems. Two principal approaches to fitness functions are distinguished: 1) Explicit fitness functions which are \textit{explicitly} defined/engineered and govern the agents' genotype/phenotype mapping. These functions are usually fixed and do not evolve over time. Systems which rely on explicit fitness functions (and similar engineered elements) are declared as ``top-down'' evolutionary approaches. 2) Implicit fitness functions which, in contrast, are not engineered/explicitly devised in the system. Here, agents determine ``by themselves'' their fitness according to their intrinsic properties and interactions with the environment/other agents. Systems which rely on implicit fitness functions are declared as ``bottom-up'' evolutionary approaches.} enabling open-ended evolution may enable one to apply this knowledge to real-world domains such as solving optimisation problems. Traditional Evolutionary Computation techniques are ultimately limited by the capabilities of human engineers. A \textit{genuine} open-ended and artificial evolutionary system \citep{pattee1973htc} would abolish this barrier and allow for the perpetual creation of novel solutions in an ever-changing environment. 
\end{itemize}

\section{Aims and objectives}
We first enumerate the principal research questions of this thesis:
\begin{enumerate}
	\item What are the minimal conditions necessary to obtain the open-ended evolutionary growth of complexity?
	\item What is the significance of autocatalytic closure to the evolution of complexity?
	\item Can CIPNs be considered as subsets of closed chemical reaction networks?
	\item Can we evolve closed CIPNs, of higher complexity, to achieve pre-specified information processing tasks?
\end{enumerate}
To address more specifically the above singular research questions, we investigate the following research workpackages and objectives which are identified as follows:
\begin{itemize}
	\item \textit{Modelling Chemical Networks:} To identify the state of the art in the multidisciplinary field of scientific modelling applied to the study of biochemical networks. A review of the main existing families of modelling techniques according to a range of selected and relevant criteria will be provided.

	\item \textit{Evolving CIPNs:} To determine a satisfactory evolutionary framework to examine autocatalytic closure and the evolution of Cellular Information Processing Networks. A selection of techniques applied to evolving and examining closure dynamics of chemical networks will be evaluated. Two families of evolutionary methods are distinguished: top-down/Evolutionary Computation techniques and bottom-up/Artificial Chemistries methods. A comparison between top-down and bottom-up evolutionary approaches will be conducted.
	
	\item \textit{Evolutionary simulation platform:} To propose a novel evolutionary simulation platform capable of evolving closed reaction networks to carry-out pre-specified information processing tasks. This stochastic system will account for the reflexive nature of molecular species which are regarded as condition/action rules. A novel agent-based Artificial Chemistry will be constructed. This system is termed the \MCS~ and employs a term-rewriting formalism (the broadcast language which was devised by \citealp{holland1975ana,holland1992ana}) to specify the molecular species and reactions.

	\item \textit{Closure in reaction networks:} To provide complementary insights on the evolutionary dynamics (e.g., spontaneous emergence, self-maintenance) of closed reaction networks in Artificial Chemistries. A series of experiments focusing on the emergence, self-maintenance and evolution of closed reaction networks using the \MCS~will be carried out.

	\item \textit{Parallelism in Artificial Chemistries:} To address the concurrent nature of chemical processes in the \MCS. The effects of parallelism upon evolutionary dynamics in Artificial Chemistries will be explored. A parallel version of the \MCS~ using distributed computing facilities will be implemented.
	
	\item \textit{Evolutionary capability:} To contribute to the understanding of evolutionary capability in Artificial Chemistries. The effects of compartmentalisation, molecular diffusion and cellular division over the system's evolutionary capability will be examined. A series of evolutionary experiments will be performed using the parallel version of the \MCS~in which compartmentalisation, molecular diffusion and cellular division features are introduced.

	\item \textit{Evolution of closed reaction networks:} To demonstrate the evolution of closed reaction networks capable of performing pre-specified information processing tasks. An additional series of evolutionary experiments will be conducted using the cellular model of the \MCS. A novel cellular division criterion is devised to drive the evolution of the closed reaction networks.

	\item \textit{Crosstalk and the evolution of complexity:} To demonstrate the constructive role of crosstalk in enabling the evolutionary growth of complexity in closed reaction networks. A series of evolutionary experiments will be carried out in which crosstalking networks are evolved to carry-out pre-specified multitasking functions.

\end{itemize}

\section{Structure of the thesis}
The chapters of this thesis are summarised as follows:

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 2} & A review of the main computational techniques (i.e., deterministic, stochastic, probabilistic, algebraic and agent-based) to model chemical networks is given. Based on this evaluation, a suitable framework is identified to represent, simulate and analyse chemical networks in this project.
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 3} & An evaluation of several evolutionary techniques to evolve Cellular Information Processing Networks (CIPNs) is presented. Two families of evolutionary techniques are distinguished: top-down/Evolutionary Computation approaches and bottom-up/Artificial Chemistries. The outcome of this review is to identify an adequate framework to examine closure and the evolution of CIPNs.
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 4} & A novel Artificial Chemistry (AC) termed the Molecular Classifier System - broadcast language (\MCS) is described. The latter is an agent-based AC which employs the Holland broadcast language, a term-rewriting formalism, to specify the molecular species and reactions.
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 5} & A first series of experiments which focuses on the spontaneous emergence and self-maintenance of closed reaction networks in the \MCS~ is presented. Unexpected degenerative evolutionary dynamics caused by the emergence of parasitic and elongator molecular species are also examined. 
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 6} & To address the evolutionary degeneration issues of the \MCS, two multi-level selectional model variants which introduce compartmentalisation are presented. These novel \MCS~implementations exploit distributed computing facilities. A static reactor model with molecular diffusion and a cellular model are independently evaluated.
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 7} & The cellular model of the \MCS~ is employed to evolve closed reaction networks to carry-out a pre-specified information processing task. The potential role of crosstalk in enabling the evolutionary growth of complexity in chemical networks is investigated. This chapter demonstrates the evolution of crosstalking closed reaction networks of higher complexity.
\end{tabular}

\begin{tabular}{p{2cm} p{12.5cm}}
\textit{Chapter 8} & Finally, the contributions and the future work of this thesis are discussed. 
\end{tabular}