Victor Norris

Abdallah Zemirline

Patrick Amar

Eshel Pascal Ballet

Ben Jacob

Gilles Bernot

Guillaume Beslon

Eric Fanchon

Jean-Louis Giavitto

Nicolas Glade

Eshel Ben Jacob

Patrick Greussay

Yohann Grondin

James A Foster

Guillaume Hutzler

Francois Kepes

Olivier Michel

Gradimir Misevic

Franck Molina

Jacqueline Signorini

Pasquale Stano

Alain Thierry

From bioputing to bactoputing: computing with bacteria

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

If the two species, microbiologists and computer scientists, are to interact fruitfully, microbiologists need to have an idea of some of the problems that are of interest to computer scientists whilst computer scientists need to see solutions -perhaps to other problems -in the knowledge and intuitions of microbiologists.

What is computing? Defined narrowly, it is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all computing is 'What can be (efficiently) automated?' [START_REF] Denning | Computing as a discipline[END_REF]. In essence, a Turing machine is a very simple computer. The Turing machine is further specified by a set of instructions which we can think of as a program. What can a Turing machine do or not do? To answer this, consider a Universal Turing machine which is a Turing machine able to read the description of any other Turing machine and to do what that other Turing machine can do. A Universal Turing machine can therefore perform any definite method and, importantly, it could do this without being extraordinarily complex provided it has an immense storage capacity. (Note that a modern computer runs a microprogram that allows its processor chip to take instructions from the main store and compute local functions of them so as to make these instructions resemble those of a particular processor; hence by changing the microprogram, the computer becomes a PC, or a Mac, or a Unix workstation, or any other known computer. Most modern computers are therefore Universal Turing machines). No-one has yet found a plausible model of computation which is more powerful than the Turing machine. Whether living systems constitute -or could be turned into -more powerful calculating devices than Turing machines is highly controversial (see for example [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]). In an investigation of how the green sulphur bacterium, Chorobium tepidum, transfers and traps light energy, it has been suggested that it actually performs a quantum computation in using a wavelike characteristic of the energy transfer within the photosynthetic complex to allow the complexes to sample simultaneously different states and find the most efficient path [START_REF] Engel | Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems[END_REF]; this can be likened to an algorithm in quantum computing for searching an unsorted information database [START_REF] Grover | Quantum mechanics helps in searching for a needle in a haystack[END_REF]. That said, as coauthors with differing opinions, we choose in the following to skirt the issue of whether cells offer an alternative to the paradigm of the Turing machine.

What is a cell? It can be argued that the cell is an autocatalytic network, or a neural net, or a tensegrity structure, or a pattern of connectivity with characteristics of Small Worlds and Self-Organised Criticality, or a giant oscillating dipole, or a unit of subjective experience etc. It seems evident that the cell is the creator and the creation of an extraordinarily high density of different organizing processes that have autocatalytic relationships with one another [Norris et al., 2004]. It is a system that produces self-organization and assembly by recruiting and dismissing a multitude of processes and molecules. An exciting question for bioputer designers is therefore what else does this? What else, in other words, could be modelled using a cell and, in particular, a bacterial cell?

What is bioputing? The relevance of certain biological materials and processes to computing has been understood for decades. These materials include DNA, where its value to different sorts of computing, such as the solution of combinatorial problems, is well-known [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. Such materials in combination with biological processes can constitute effective computers [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. Hence, bacteria and other cells can be used as a source of new materials with new properties for computing along traditional lines. They may also be used in an intact form for simple forms of such computing [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. Attempts to construct the minimal cell, inspired in part by origins of life studies and by biotechnological applications, may also produce cells that are amenable for sophisticated, albeit traditional, computing. All these approaches form part of the general approach of what we term bioputing.

What is bactoputing? Bactoputing is the use of the natural behaviour of bacteria for computing. As such, it is a subset of bioputing. Here we try to focus on a version of bactoputing in which bacteria are considered as computers. One common approach to computing with bacteria entails adapting them so that they become identical sets of logic gates. Each essentially identical bacterium is then a constituent of a computer; in other words, a homogeneous population of bacteria constitutes the computer. In this approach, one possibility is to use the logic systems that are native to the bacterium, to use, in other words, its original set of networks of gene expression and protein synthesis [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. One of the obvious attractions here would be the capacity of bacteria to multiply cheaply. One of the drawbacks is that bacteria have a tendency to follow their own agenda and frustrate attempts to engineer them to follow human designs (but see below [START_REF] Posfai | Emergent properties of reduced-genome escherichia coli[END_REF]). An alternative approach is to consider each bacterium as different [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. In this case, a heterogeneous population of bacteria constitutes the bactoputer. This is the tack we follow here. (We choose to ignore a different version of bactoputing in which bacteria are considered as agents that both compute and act; for example, bacteria may be modified to recognise, invade and treat cancer cells or parasites within us [START_REF] Baker | Better living through microbes[END_REF]. This would involve adapting what certain species of bacteria do anyway, and is therefore in the spirit of bactoputing. More speculatively still, bacteria might be converted into new organelles in a remake of the origins of eukaryotic cells. Such organelles might function to repair the host cell and reverse ageing (Norris, in preparation). This would entail making full use of the capacity of bacteria to sense their environment and to modify it.)

In section 2, we mention a number of problems that may, one day, be amenable to bactoputing. These problems include: many combinatorial problems that are unsolvable by traditional computing since they entail polynomial increases in the number of steps needed; hardware problems due to lack of memory or the difficulty of construction in 3D; problems faced by many social groups in which a compromise must be found so as to survive in difficult conditions but to proliferate in favourable conditions; 'undecidable' problems that may require construction of a bactoputer or other novel brain; the problem of finding a new high level language appropriate for a bactoputer. In section 3, we review, for computer scientists interested in bactoputing, certain aspects of microbial physiology along with efforts to construct simplified bacteria by deleting 'superfluous' DNA from genomes, by use of wallless variants (L-forms), by selecting bacteria via mutation and selection, and by origin-of-life experiments to make liposome-based systems. In section 4, we try to address the problems raised in section 2.

A few questions in computer science and the social sciences

NP problems

If the number of steps in the calculation is given by a function of N and each step takes a microsecond, for N = 100, functions such as log 10 N and N 5 are tractable since they take 2 microseconds and 3 hours, respectively, whilst N N is not tractable (it would take 3x10 186 years). This leads to the idea that an algorithm can be tractable if its behaviour depends polynomially (N 2 , N 3 etc.) on the size, N, of input. This idea can be extended to the problem treated which is considered tractable if its worst case can be solved by a tractable algorithm. The class P is the class of tractable decision problems. The class P is about polynomial time but there is a wider class of problems, PSPACE, that are solvable with a polynomial amount of memory. This has a direct relevance to a bacterial population which, in the right conditions, can undergo an exponential increase in mass.

The Hamiltonian circuit problem is whether there is a route which visits every village exactly once and which ends at the village where it started. The related Travelling Salesman problem (see below) is whether there is a route shorter than a given distance which visits every village at least once and which ends at the start. These are examples of the NP class of problems, which may be tractable but for which no polynomial-time algorithm is known. A decision problem (one that needs a 'yes' or a 'no' as an answer) is said to be in NP if there exists the equivalent of a lucky guess algorithm (a pseudo-algorithm) for instances of the problem needing a 'yes' that takes less than polynomial time to correctly answer 'yes'. The problem of whether or not P and NP are the same class of problems is a major question in mathematics and has economic repercussions. If they are the same class and a problem in NP is tractable without, as well as with, a lucky guess, then much larger instances of them can be tackled. If they are different classes and problems in NP can be shown to be intractable, the search for certain types of algorithm for them can cease.

Problems can sometimes be transformed into one another (this is the case for the Travelling Salesman and the Hamiltonian Circuit) and, since any polynomial function of a polynomial is itself also a polynomial, as long as the time taken to do the transformation is polynomial in N, the size of the input, the time taken by a polynomial-time algorithm for the transformed problem must also be polynomial. This notion of transformation is important because many NP problems can transformed into a problem that is itself in NP. (see Appendix for problems that are termed NP-complete). This is a general term for a wide variety of many problems, indeed every branch of mathematics has its NP problems involving networking, timetabling, packing, matrices, geometry, and combinatorial mathematics (note that DNA sequence comparisons are in NP if mismatches and gaps are allowed).

The problem of density

A recurrent problem is that computers have insufficient memory or run too slowly. One limitation to the speed at which computers can run is the distance between components. This limitation is due to what is essentially a 2D construction of the integrated circuit. The possibility of constructing a nanoscale 3D calculating device would therefore be very attractive.

Optimisation and constraint problems in organisations

Many social and economic problems require an organisation to steer between survival and growth. Companies and universities must survive hard (financial) times and expand in good ones. These appear to be contradictory constraints. No single optimal solution exists. For example, there may be no individual solution to the management problem of what proportion of the staff of a multinational group or of a research organisation should be permanent. One possibility is to consider the organisation as a collection of relatively independent units, such as research laboratories, that could offer a simultaneous diversity of independent solutions. A range of different solutions may be needed -but what is this range? Other questions where we might look to bacteria for answers include the optimum number of decision-making levels and identification of the subsystem that actually makes the decision. Finally, many social organisations are constrained by the need to reconcile coherence with their present environment and coherence with their past environments. Research laboratories have to respond to new discoveries and to new funding initiatives but must reconcile these with their research history and, in particular with their skills, experience and interests. Perhaps bacteria have something to teach us here too.

Recognition and other problems

Electronic circuitries or even neuronal brains may be used to address complex problems that include many undecidable problems such as the recognition of shapes (e.g. is this a picture of a horse?) and optimisation problems with non-separable objective functions (e.g. the problem of attributing local rules to components so as to obtain a given global behaviour). A potential ability to address such problems is one motivation for research into the design of synthetic 'brains'. Some of these brains assemble readily into structures, are easy to understand and straightforward to control, which facilitates interfacing with users. They include selforganised networks of real neurones connected to electronic chips [START_REF] Demarse | The neurally controlled animat : Biological brains acting with simulated bodies[END_REF]. There are also 'soft' networks where the circuits are not fixed and easy to reconfigure. These include bioelectronic hybrid architectures such as those based on dynamic circuits made of the slime mould Physarum polycephalum [START_REF] Tsuda | Robot control: From silicon circuitry to cells[END_REF] or 'chemical brains' based on collisions between chemical waves in the Belousov-Zhabotinsky reaction [START_REF] Adamatzky | Collision-free path planning in the belousov-zhabotinsky medium assisted by a cellular automaton[END_REF]. What are the possibilities for a bacterial brain?

Beyond high level instructions

High level programming languages are written in terms of instructions that include loops (For ... Next), tests (If ... then .... else), and operate on variables and modules (Gosub). In general, each instruction is specific and instructions are acted on sequentially (even in parallelprocessing??). How might very different languages be developed? Biological systems have inspired imitation in conventional computing in the case, for example, of genetic algorithms. Might bacteria inspire an effectively different style of computing. Would it be possible, for example, to devise a new type of programming language based on bacterial actions?

Bactoputing tools

In the following section, we review some well-known facts about bacteria and mention some recent speculations with the idea that these may be useful for bactoputing. We then propose population-based approaches in which the bacterial population is a single computer but in which each bacterium is a different computing device.

Phenotypic diversity

Population diversity can pose a problem to those types of bactoputing that require bacteria to behave in standard, constant ways. One solution to this lies in constructing negative feedback circuits to limit the range over which the concentrations of network components fluctuate, as shown for simple genetic circuits in E. coli [START_REF] Becskei | Engineering stability in gene networks by autoregulation[END_REF]. However, population diversity can be seen as a solution in search of a problem. One of these problems is species extinction where a possible solution would lie in preserving the small sub-groups in which a disproportionate fraction of the diversity is concentrated [START_REF] Rauch | Theory predicts the uneven distribution of genetic diversity within species[END_REF].

Rather than think of bacteria as identical individuals, it is often useful to think of them in terms of populations of heterogeneous individuals that compete, collaborate and communicate. Bacteria already use peptides and other chemicals that they export into the media and that they then sense to determine population density in the phenomenon of quorum sensing which is implicated in processes that include symbiosis, virulence, competence, conjugation, antibiotic production, motility, sporulation, and biofilm formation [START_REF] Miller | Quorum sensing in bacteria[END_REF].

Many bacteria are confronted with the problem of a changing environment in which different and sometimes incompatible strategies are required for survival and for growth. This is resolved at the population level by the generation of both phenotypic diversity [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF] and genetic diversity. In generating phenotypic diversity, transcription factors are clearly important and, since they are often present in small numbers, there is a role to be played by stochastic noise [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]; however, the key role, we and others have argued, is played by the cell cycle [START_REF] Norris | Autocatalytic gene expression occurs via transertion and membrane domain formation and underlies differentiation in bacteria: A model[END_REF] which leads to the presence of two or more chemically identical chromosomes within the same cytoplasm that spontaneously adopt complementary patterns of expression to equip the future daughter cells for life in different environments [START_REF] Minsky | Stress, order and survival[END_REF]. In generating genetic diversity, there is an interesting phenomenon whereby certain individuals in a stressed population undergo mutations in proof-reading genes that lead to a high level of mutations; when these unhealthy individuals lyse, fragments of their DNA can be taken up and used by other individuals which may thus acquire a beneficial mutation [START_REF] Matic | Survival versus maintenance of genetic stability: A conflict of priorities during stress[END_REF]. It turns out that for environmental stresses to induce programmed cell death in cultures of E. coli, the bacteria must secrete a specific pentapeptide that is derived from the degradation of glucose-6-phosphate dehydrogenase, a metabolic enzyme [START_REF] Kolodkin-Gal | A linear pentapeptide is a quorum-sensing factor required for mazef-mediated cell death in escherichia coli[END_REF]. This may mean that there is yet another connection to be understood between individual metabolism and population signalling.

Plasmids, bacteriophage and transposons

Bacteria possess small 'chromosomes' or plasmids that are replicated independently of their principal chromosome and that can be transferred readily between bacteria. Genetic information can also be transferred between bacteria by bacteriophages; these bacterial viruses are stable and resistant and, protected by a shell of proteins, often transport DNA from one bacterium to another. Genetic information can be transferred within a chromosome or between a chromosome and a plasmid by transposons. This allows them to adapt to exposure to new dangers and to avail themselves of new opportunities. Hence bacteria possess a powerful armoury for altering and rearranging their genetic material. They possess, in other words, a system for both solving problems and for anticipating problems.

Hyperstructures

In the pursuit of the nature of the bacterial cell, we and others have explored the possibility of the existence of a level of organisation intermediate between macromolecules and whole cells -the level of hyperstructures [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. A hyperstructure is a collection of diverse molecules (genes, mRNAs, proteins, ions, lipids) that is associated with at least one function. A non-equilibrium hyperstructure is assembled into a large, spatially distinct structure to perform a function and is disassembled, wholly or partially, when no longer required [START_REF] Norris | Questions for cell cyclists[END_REF]. Examples in E. coli of non-equilibrium hyperstructures include a nucleolar hyperstructure (analogous to the microcompartment within which ribosomes are assembled inside the eukaryotic nucleus) for synthesizing ribosomal RNA [START_REF] Cabrera | The distribution of rna polymerase in escherichia coli is dynamic and sensitive to environmental cues[END_REF]] and the division hyperstructure responsible for the invagination of the membrane and peptidoglycan layer [START_REF] Aarsman | Maturation of the escherichia coli divisome occurs in two steps[END_REF]]. An equilibrium hyperstructure is also a large spatially distinct structure with a function but its life is not dependent on spending energy. Examples, again in E. coli, include the highly-ordered RecA-DNA co-crystal, which forms when there is insufficient ATP to repair DNA damage, and in which the tight crystalline packaging is believed to protect the DNA by physically sequestering it [START_REF] Levin-Zaidman | Ordered intracellular reca-DNA assemblies: A potential site of in vivo reca-mediated activities[END_REF]. Certain hyperstructures straddle the non-equilibrium/equilibrium divide such as the flagellar hyperstructure which has both an equilibrium part (the flagellum itself) and, during the formation of the flagellum, a non-equilibrium part comprising the transcribed genes and their products that acts as a sensor of hydration [START_REF] Wang | Sensing wetness: A new role for the bacterial flagellum[END_REF].

In the hyperstructure approach, hyperstructures structure membranes, cytoplasm and nucleoid and progress through the cell cycle becomes a state cycle of hyperstructures. Such hyperstructures may interact via a variety of mechanisms including the familiar processes of DNA supercoiling, coupled transcription/translation, molecular and macromolecular signalling, tensegrity and local concentrations, as well as the speculative ones of ion condensation, oscillating water structures, and intracellular streaming.

Minimal genomes

Bacteria have existed for billions of years. As the growing problem of antibiotic resistance shows, they readily adapt to and escape from human control. Computers based on bacteria are therefore likely to have a short lifespan unless the adaptability of bacteria is taken into account or indeed unless it becomes part of the computing. One approach to make bacteria more malleable is to take bacteria such as E. coli and Bacillus subtilis and to cut down the genome so as to eliminate 'unnecessary' functions [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. How far might this be taken? Until recently, it was believed that 250 or so genes would be needed for a minimal version of a modern cell in the most favourable conditions [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF] similar to minimal genome sizes inferred by site-directed gene disruptions and transposon-mediated mutagenesis knockouts in several bacteria (for references see [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]). However, the symbiont Carsonella ruddii, which lives inside insects, has a 160 kb chromosome that encodes only 182 proteins although admittedly it does lack many genes that are thought essential for independent life outside a host [START_REF] Nakabachi | The 160kilobase genome of the bacterial endosymbiont carsonella[END_REF]. Hence the number of 250 genes might be reduced considerably, for example, if repair and other functions are dispensed with and if protein synthesis is imagined to be performed with a reduced set of ribosomal proteins. Attempts to generate bacteria with minimal genomes have led to engineered E. coli strains with nearly 30% of the genome missing, certain of which grow more slowly than the wild type strain [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. More recently, elimination of recombinogenic sequences and mobile DNA (such as transposons and IS elements), as well as elimination of 'non-essential' and cryptic functions, have generated strains of E. coli that have increased genomic stability, maintain otherwise unstable plasmids and can be electroporated readily with DNA [START_REF] Posfai | Emergent properties of reduced-genome escherichia coli[END_REF]; moreover, these strains grow well. Whilst such strains may be less prone to discarding or perverting the constructs that scientists have inserted into them, they may be less able to follow the natural strategies of bacteria based on the generation of genetic and phenotypic diversity (see above), strategies that may be either welcome or unwelcome depending on the type of computing to be performed.

In developing bacteria for computing purposes, little use has yet been made of L-forms. These are bacteria that have been selected for the loss of their peptidoglycan wall. Despite this major change, these simplified bacteria manage to grow and divide [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. Although fragile, they seem to have cytoplasmic membranes that are naked and they may be easier to manipulate and may be more amenable for computing than their parent bacteria. In a sense, they represent a step back towards earlier forms of life that could usefully undergo genome shrinking.

Directed evolution

Another approach of possible value to bactoputing is that of directed evolution. Mutators have defective DNA proof-reading and generate mutations at a high frequency. Such mutators can be grown for thousands of generations in chemostats under a constant selective pressure to drive genotype and phenotype towards those desired by the experimenter. These selective conditions can result in the bacteria adapting in ways that are not desired, for example, by increasing their capacity to stick the walls of the chemostat and so avoid being flushed out; this type of problem, which may arise in both the construction of the strain and in the operation of the bacteria-based computer, can be partly resolved with two chemostats one being used whilst the other is being sterilised [de [START_REF] De Crecy-Lagard | Long term adaptation of a microbial population to a permanent metabolic constraint: Overcoming thymineless death by experimental evolution of escherichia coli[END_REF]. The mutations in such conditions occur independently of one another in individual bacteria. However, if a proportion of bacteria lyse, the possibility exists that other bacteria can take up their DNA and benefit (see above). Hence, the rapidity of directed evolution can be increased by the use of bacterial species that take up foreign DNA at a high frequency such as Acinetobacter sp ADP1 [START_REF] Palmen | Physiological characterization of natural transformation in acinetobacter calcoaceticus[END_REF].

Liposomes and origins of life

There are two ways in which study of the origins of life may be useful for a bacteria-based computing. One is in the investigation of what the first cell really was (assuming it really was a specific cell rather than a population or ecosystem [START_REF] Hunding | Compositional complementarity and prebiotic ecology in the origin of life[END_REF]); clearer ideas about the nature of the first cells might help us in exploiting their descendants. The second is in the experiments performed. A prime example of combining such hypotheses with experiments is in the construction of the minimal cell de novo. This is a bottom-up approach (as opposed to the top-down approach of deleting chunks from an existing genome described above) where the objective is to generate the simplest cell that can be considered alive [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]. The definition of 'alive' here need not trouble those whose objective is to obtain devices for computing. One concept is that of a minimal RNA cell comprising a vesicle with two ribozymes inside, the first of which catalyses the synthesis of the components that selfassemble into membrane whilst the second replicates both itself and the first ribozyme [START_REF] Szostak | Synthesizing life[END_REF]. The properties of vesicles (liposomes when their constituents are lipids) continue to be intensively explored. Vesicles can grow using surfactant precursors and even divide to maintain the original size distribution (for references see [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]). Heterogeneous composition and the presence of channels may help circumvent the problem of the difficult entry of materials in modern membranes based on phospholipids or similar molecules. For example, an α-hemolysin pore incorporated into liposomes permits the uptake of small metabolites from the medium [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. A very different way of bringing ions and indeed macromolecules into liposomes might be based on the channels formed by the simple compounds polyphosphate and poly-β-hydroxybutyrate [START_REF] Das | Proof for a nonproteinaceous calciumselective channel in escherichia coli by total synthesis from (r)-3-hydroxybutanoic acid and inorganic phosphate[END_REF][START_REF] Norris | Poly-(r)-3-hydroxybutyrate and the pioneering work of rosetta natoli reusch[END_REF]#2258]. An alternative, population-based, approach would be to develop the fusion and fission of heterogeneous liposomes [START_REF] Norris | A fission-fusion origin for life[END_REF]]. There have been numerous experiments on fusion of compartments using water-in-oil emulsions which have the advantage of allowing high local concentrations of reactants (for references, see [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]). Often, these reconstruction approaches entail the production of proteins detectable by fluorescence, such as the Green Fluorescent Protein (GFP). A mutant form of GFP has, for example, been produced in lecithin liposomes [START_REF] Yu | Synthesis of functional protein in liposome[END_REF]. Continued development in this area towards real minimal cells coupled to detection systems may prove useful for computing. The work in the PACE project is relevant here (http://complex.upf.es/~ricard/PACEsite).

The vision in the bottom-up construction of minimal cells is that they should contain a small set of macromolecules with highly specific functions: the original cells started out simple and became complex [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]. This vision is being fleshed out experimentally [START_REF] Luisi | Approaches to semi-synthetic minimal cells: A review[END_REF]. A very different vision is that life appeared in the form of a pre-biotic ecology in which a rich, diverse and complex world of protocells or composomes exchanged their contents [START_REF] Hunding | Compositional complementarity and prebiotic ecology in the origin of life[END_REF]. In this vision, the first cells only have meaning within the context of a population and to investigate and exploit this, the minimal cell must give way to the minimal population.

Colonies and swarming

Populations of the bacterium, Paenibacillus dendritiformis, make surfactants to extract fluid from the semi-solid nutrient substrate so as to create a layer within which they can swim. The problem is that the production of the surfactant requires the collective action of a dense bacterial population which the food-depleted substrate can not sustain. The solution they have adopted is to form a colony with a branching structure -within each branch the bacterial density is sufficiently high, yet the average population density of the colony is sufficiently low for the nutrients to suffice. Very different patterns form at different nutrient levels. Part of the solution resides in the precise adjustment of the viscosity of the lubricant layer and the production rate of the surfactant in order to generate specific branch structures with specific widths according to the substrate hardness and nutrient levels [START_REF] Kozlovsky | Lubricating bacteria model for branching growth of bacterial colonies[END_REF][START_REF] Jacob | Self-engineering capabilities of bacteria[END_REF]. P. dendritiformis growing on poor substrates can have either a branching (B) or chiral (C) morphology. On hard substrates where high densities are required to produce enough lubricating fluid, the B morphotype is selected, leading to the formation of colonies with branching, bush-like morphologies whilst on softer substrates, the C morphotype is selected, leading to curly branches that allow faster expansion while also using patches of food left behind as the branches are twisted inward. How exactly are the branches made? Cells go into a non-motile state further back from the colony front, where the nutrient levels is extremely low. They also emit quorum-sensing molecules or pheromones that represent the state of the population and its environment and that occasion changes in gene expression. One of these changes is the inhibition of cell division which leads to them elongating. Upon elongation, the cells alter their collective movement from the typical runand-tumble of the short B cells to a coordinated forward-backward movement that leads to the branches twisting with a specified handedness (this handedness depends on cell-cell interactions together with the inherent flagella handedness). The two possible morphotypes are inheritable and can coexist for some range of growth conditions. There are also spontaneous transitions to give new patterns that maximize the rate of colony expansion.

Learning from experience has also been described in bacteria. Paenibacillus vortex, forms vortices that vary in size from tens to millions of bacteria, according to their location in the colony. The cells in the vortex replicate, and the vortex expands in size and moves outward as a unit, leaving behind a trail of motile but usually non-replicating cells -the vortex branch. Maintaining the integrity of the vortex while it serves as a higher-order building block of the colony requires communication: each cell in the vortex needs to be informed that its role is now more complex, being a member of both the specific vortex and the whole colony, so it can adjust its activities accordingly. This ongoing communication is particularly apparent when it comes to the birth of new vortices. New vortices emerge in the trail behind a vortex following initiation signals that cause the bacteria there to produce more lubricating fluid and to move quite rapidly as a turbulent "biofluid", until an eddy forms and becomes a new vortex. The entire process appears to proceed as a continuous dialogue: a vortex grows and moves, producing a trail of bacteria and being pushed forward by the very same bacteria left behind. At some point the process stalls, and this is the signal for the generation of a new vortex behind the original one, that leaves home (the trail) as a new entity toward the colonization of new territory. Recent findings based on P. vortex and other bacteria indicate that bacteria modify their colonies in the presence of antibiotics so as to optimise bacterial survival. It also appears that these bacteria have a short-term memory which enables them to recall the structural solution they found to the antibiotic to which they were exposed most recently [Ben Jacob et al., 2004].

Signalling

Within bacterial and other cells there are numerous types of signalling pathways of relevance to computing [START_REF] Bray | Intracellular signalling as a parallel distributed process[END_REF]. These include the well-studied two component pathways [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF] and other systems [START_REF] Grangeasse | Tyrosine phosphorylation: An emerging regulatory device of bacterial physiology[END_REF] that depend on phosphorylation, those that depend on alarmones such as ppGpp [START_REF] Wang | Nutritional control of elongation of DNA replication by (p)ppgpp[END_REF], systems that depend on poly-β-hydroxybutyrate [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF] and those that depend on ions (perhaps even on ion condensation [START_REF] Ripoll | Ion condensation and signal transduction[END_REF]). Another conceptually very different class of signals exists, at least potentially, in cells. This is the class gemerated by those enzymes that only associate with one another when they are actively engaged in catalysing their cognate reactions (so giving rise to functioning-dependent structures); a wide variety of types of signals in the form of enzymes or metabolites can be generated [START_REF] Thellier | Steady-state kinetic behaviour of functioning-dependent structures[END_REF].

Within bacterial communities, chemical signalling occurs via molecules such as N-acylhomoserine lactones for Gram-negative bacteria, post-translationally modified peptides for Gram-positive bacteria and furanosyl-borate diester for all species [START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF] as well as fragments of intracellular enzymes [START_REF] Kolodkin-Gal | A linear pentapeptide is a quorum-sensing factor required for mazef-mediated cell death in escherichia coli[END_REF]. There has also been intriguing evidence for physical signalling in bacterial communication [START_REF] Matsuhashi | Bacillus carboniphilus cells respond to growth-promoting physical signals from cells of homologous and heterologous bacteria[END_REF][START_REF] Norris | Do bacteria "Sing"?[END_REF]).

Applying bactoputing to problems

Solving the travelling salesman problem?

Quorum-sensing can be used as the basis of a population-based computing [START_REF] Bulter | Design of artificial cell-cell communication using gene and metabolic networks[END_REF][START_REF] You | Programmed population control by cell-cell communication and regulated killing[END_REF]. Suppose that short peptides A and B exported from two different bacteria into the medium bind to receptors in a third bacterium to initiate signal transduction (via for example well-known sensor kinases/response regulators) in this bacterium that then activates or represses synthesis of another peptide C that is exported. In principle, one could have a limitless supply of logic gates of every conceivable type. Each bacterium becomes a swimming logic gate communicating via diffusible peptides. Bacteria that have not taken part in signalling could be eliminated (for example, the sensor kinase could also induce synthesis of a factor that protects the bacterium from an externally added or an internally produced poison). This would be the equivalent of apoptosis in the brain. The numbers of an individual species of bacterium in the population become the equivalent of weights in a neural net. Proteases added to the media could be used to remove signalling peptides and so synchronise the system. In this approach, chemotaxis, which E. coli uses to swim up gradients of attractants (or down those of repellents), could be used to produce a structuring of the volume in the flask such that those bacteria that are attracted to others aggregate; such structuring could result in a rapid transfer of peptides between different bacteria and could be detected if different species of bacteria were to emit light of different frequencies. Refinements that might be possible include the use of a particular peptide to activate transport systems so that whole families of gates could be switched on or off so as to construct hierarchies of gating systems. A connection with the environment could be ensured by restricting one class of peptides to be environmental signals and a second class to be the responses at the end of the line (and which could bind to biochips to trigger electrical changes). In the ideal world, learning would occur if the correct combination of response peptides were rewarded by an influx of glucose into the system.

To illustrate how peptide signalling plus differential growth might work, consider the problem of the travelling salesman who has to find the shortest route between the cities A, B, C, D, and E which he must only visit once (see above and Appendix). Suppose each city is represented by a peptide. To set the problem up, we construct a bacterium that has input A and output B (denoted by A→B), another that has A→C ... D→A, E→A etc. Suppose each bacterium can only grow if it receives A, B, C, D and E (each of which induces the expression of a different gene encoding a labile protein essential for growth) and the culture is fed in a chemostat a limiting concentration of A, B, C, D and E (plus everything else in excess needed for growth). This selects for an autocatalytic network based on signalling of the style A→C, C→E, E→B, B→D and D→A. In addition, each bacterium is engineered at the start so as to produce its output in inverse proportion to the distance between the cities; hence, the greater the distance between the cities, the less the bacterium produces of the output peptide for a constant input peptide (there is the equivalent time delay possibility). The initial population must contain representatives of every pair of cities in both directions (e.g. A→B and B→A). The object is to obtain the most efficient autocatalytic network since this should correspond to the shortest route between the cities. Prolonged cycles of growth occur in a soft gel in which the peptides can diffuse some distance from the bacteria that produce them (so that when the members of an autocatalytic network are near one another, they benefit rather than the entire population); the temperature is then raised so that the gel becomes a sol, the bacteria can be mixed, (perhaps a proportion removed to sample), and the temperature lowered to create a gel again. In the ideal world of tractable, docile, well-behaved bacteria, this should result in the selection of efficient networks corresponding to solutions to good routes to the cities (Amar and Norris, unpublished).

Tackling the density problem?

Bacterial colonies are complex 3D structures in which the bacteria are densely packed (see above). A cubic millimetre of bacteria would contain at least 10 9 individual cells. In such a cube, each bacterium could act as both an element of a population-based processor and memory. Bacteria such as E. coli can double every 17 minutes so increases in computing capacity are not difficult to envisage. Moreover, in the case of a bacterial colony, the colony constructs itself as it grows (see above). The capacity of bacteria to diversify their phenotypes might also be exploited by creating conditions that allow the growth of those bacteria that take part in the calculation at the expense of those that do not take part.

Optimisation and constraint problems in organisations

Many bacterial species are extremely good at steering between survival and growth and in generating a huge diversity of behaviours in the individual bacteria that constitute a population. In trying to interpret the phenotypic diversity characteristic of these populations, it would extremely useful to obtain information on the activity of transcription factors at the level of the individual cell. Given that the process of chromosome replication itself is a possible source of diversity [START_REF] Rocha | A strand-specific model for chromosome segregation in bacteria[END_REF][START_REF] Norris | Hypothesis: Variations in the rate of DNA replication determine the phenotype of daughter cells[END_REF], it would also be useful to manipulate rates of replication [START_REF] Janniere | Genetic evidence for a link between glycolysis and DNA replication[END_REF]. Bacterial populations also generate genetic diversity and there should be a way to make use of the mutation strategy adopted by bacteria in conditions of stress or high population densities (see above [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]).

It can be argued that the phenotypes of bacteria are determined at the level of hyperstructures (see above) rather than at the level of individual macromolecules (such as genes or proteins or small signalling molecules). In this hypothesis, the bacterial population generates a range of phenotypes by varying the proportion of equilibrium and non-equilibrium hyperstructures present in each bacterium. The function that describes this variation in the population changes with different conditions and different species. How might information about this function be obtained? Ongoing developments in optical and analytic microscopy are making easier to determine which molecules and macromolecules constitute hyperstructures as well as the number and distribution of a given type of hyperstructure within a bacterial population. Hence the eventual problem for students of bactoputing will be to somehow code this information into a useable form.

For billions of years, bacteria have been solving the problem of reconciling coherence with the present environment and coherence with their preceding phenotype. We have proposed that this generation of a meaningful phenotype occurs via competitive coherence [START_REF] Norris | Modelling e. Coli: The concept of competitive coherence[END_REF]. This concept is based on the way a bacterium must maintain both the continuity of its composition and the coherence of this composition (with respect to the inside and outside world) so as to have phenotypes that are consistent both over time with one another and at the present time with the environment. Failure to achieve such consistency is disadvantageous and, in a competitive world, punishable by extinction.

Recognition and other problems

It is well-known that bacteria communicate within colonies (see above). This communication is usually assumed to be chemical in nature but other possibilities should be considered, including sound [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF]]. Chemical communication occurs by diffusion through the medium and the information may be destined for distant bacteria or for the whole population (in which case, modulation of intensity -and perhaps frequency -is important). Communication may also be strictly local and depend for example on exchange between neighbours via conjugation pili through which DNA can be sent.

Populations of bacteria in the form of colonies behave like huge and massively interconnected networks with seemingly intelligent behaviours. As living processors they adapt, evolve and organise themselves to process efficiently their environment and, for example, extract nutrients to transform into biomass or decide that an enemy is present. The colony can also spatially reorganise under the action of orienting perturbations such as sources of chemoattractive molecules. Adaptable, reconfigurable bacterial populations that can switch between different organisational modes (i.e. from single motile cells to colonies with well structured morphologies [Ben Jacob and Shapira, 2004].) do indeed possess the properties and capabilities needed for being chemical-biological brains. This switch corresponds to the dynamic transition of the processing system from being very efficient and globally interconnected, but poorly programmable, to being structurally programmable with a better interfacing capacity [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. As in a self-adaptative loop inducing the structuring and the processing ability of a network of fibrillar agents (e.g. microtubules in [START_REF] Pfaffmann | Adaptive information processing in microtubule networks[END_REF], the spatially distributed population of bacteria can reorganise according to the environment (e.g. it can respond to the addition at a specific time and place of chemoattractants or nutrients by reorganising spatially and functionally).

How might the problem-solving prowess of colony-forming bacteria such as P. dendritiformis be used in bactoputing? The use of such populations for bactoputing can be envisaged through (i) a strong interface by using a restricted list of instructions (e.g. chemical instructions, temperature or electrical stimuli,...) in order to induce specific behaviour in the bactoputer, or (ii) soft and poorly defined interfaces by the direct contact of the bactoputer with the problem it has to solve. The latter case might correspond to a diagnostic chip dedicated to detection of diseases with the bacterial chip acting simultaneously as a sensor, a processor analysing complex data, and an output device that it translates this information into a form intelligible to humans. Moreover its controllability could be reinforced by driving the structuring of the colony into specific, static geometries that have been engineered (e.g. network of microscopic channels, interconnected containers ...). The result would be the accomplishment of a task or macroscopically observed manifestations of the behaviour of the colonies such as the appearance of fluorescent signals or of a colony with a particular morphology.

Beyond high level instructions

If one were to devise a new programming language based on bacteria, which instructions would it contain? Some of these instructions are easy to suggest: transport (a hundred different ions and molecules); move (up and down gradients in 3D); recombine instructions (between regions of the chromosome or by making use of plasmids and transposons); exchange instructions (by conjugating or by taking up those phage that contain some chromosomal DNA); mutate (or mutate at high frequency in the case of mutator bacteria); send messages (in the form of quorum-sensing molecules and other molecules); replicate the chromosome (and pause during replication), differentiate (perhaps as a function of a role in a colony) and sporulate (or at least form a bacterium that has increased resistance); grow (at different rates); divide (to make progeny that are smaller and that may differ from one another); lyse to release phage. Other actions are harder to exploit due to the limited state of current knowledge; these include creating a hyperstructure, maintaining or altering the ratio of equilibrium to non-equilibrium hyperstructures, and increasing the diversity of hyperstructures.

How might such instructions be given? The hundreds of factors that control transcription and translation and that mediate the above actions might be manipulated chemically by fusing the genes that control them to inducible promoters (such as the one that controls the lactose operon and that can be induced by the chemical IPTG). They might also be manipulated physically by changing the temperature or exposing the bacteria to radiation or other stresses. Rather than discrete instructions being given, the instruction to the bacterial population would be in the form of a chemical or physical gradient. Hence the instruction would be different at different places.

How would instructions be ordered? Rather than instructions simply being given in a sequence, many instructions would be given simultaneously. A metaphor for the instructions would be that of a landscape with a varied topology, different vegetation, watercourses, soil types etc. Of course, instructions could also be given sequentially (e.g. heat shock followed by cold shock) or the possibilities inherent in pausing DNA replication might be exploited by inserting sequences into the chromosome to allow proteins to bind to them and hence slow down or block replication in chosen regions [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF].

How would results be read out? When the population is a colony, results could be in the form of spatiotemporal patterns (see above) or in the distribution of extracellular signalling molecules. When the population is a suspension of cells, results could be in the form of the molecules and structures that constitute the individual cells.

Discussion

Computer scientists are interested in solving combinatorial problems of the NP-complete and related classes. We have suggested above that the autocatalytic growth properties of bacterial populations might be exploited to solve the travelling salesman problem. This is an illustration of a weak form of bactoputing that, arguably, is just bioputing since it is not really in the nature of bacteria to perform the task required here. Another weak form of bactoputing would entail constructing bacteria with their metabolic enzymes on the outside (an 'inside-out' metabolism) to create a heterogeneous population in which each individual bacterium needs the activity of other bacteria to grow. A related but stronger form of bactoputing would be to make use of those bacteria like Clostridium cellulovorans that use cellulsomes to degrade the walls of plants and that naturally have metabolic activities on the outside [START_REF] Doi | Cellulosomes: Plant-cell-wall-degrading enzyme complexes[END_REF].

Computer scientists are also interested in solving problems with hardware, and here bacterial populations offer huge densities (a human intestinal tract contains up to 10 14 bacteria) with numerous chemical and physical connections in three dimensions [START_REF] Matsuhashi | Production of sound waves by bacterial cells and the response of bacterial cells to sound[END_REF][START_REF] Palkova | Multicellular microorganisms: Laboratory versus nature[END_REF]. They are also cheap and grow fast as well as being robust and self-repairing. Some species can operate at high temperatures and, of course, the presence of water is not a problem.

In the world of human affairs, an organisation often has to steer between survival and growth where conflicting constraints make it hard to find good solutions. A possible approach to finding these solutions is to use one complex system to model another. Bacteria have been selected for billions of years for their capacity to explore phenotype space; this entails exploiting opportunities to grow and to survive stresses. Both opportunities and challenges come in a huge number of combinations in an evolutionary landscape that is modified by the behaviour of the bacteria themselves. Here, we have suggested that it is in bacterial solutions to the challenge of navigating phenotype space that bactoputer scientists may discover new paradigms and applications. For example, bacterial populations anticipate nutritional crashes and, in doing this, they communicate with one another and lyse [START_REF] Kolodkin-Gal | A linear pentapeptide is a quorum-sensing factor required for mazef-mediated cell death in escherichia coli[END_REF], they also increase phenotypic diversity in the rundown to stationary phase [START_REF] Vohradsky | Genome resource utilization during prokaryotic development[END_REF]. The prediction here is that as oil supplies run out and global warming increases our societies will go through a period of experimentation, which if unsuccessful, will be followed by convergence on some spartan model. Maybe a bactoputer could help us do this intelligently.

The use of bacterial colonies in their native state as 'brains' to solve recognition and other problems would be a strong form of bactoputing. It would be possible to construct a transparent chip into which grooves were cut (with for example a focussed ion beam) that would have diameters similar to those of a bacterium; bacteria containing fluorescent labels could then explore a network of grooves as guided by a variety of chemoattractants and chemorepellents; a stack of such chips, with channels connecting them, might then be made into a bacterial brain that could be described as a bactoputer insofar as it would be based on a natural property of bacteria, namely, chemotaxis. Another strong form of bactoputing could directly involve the metabolism (the network of reactions, catalysed by enzymes, that creates the cell) and, given that metabolic enzymes are encoded by genes, it should be possible to design circuits based on coupling metabolism and gene expression [START_REF] Thellier | Steady-state kinetic behaviour of functioning-dependent structures[END_REF]. Such bactoputing could be useful in studying social systems where money is both a 'nutrient' and a signal. Significantly, it has been shown that a regulatory circuit in metabolism, namely the lycopene biosynthesis pathway in E. coli, can be engineered to control gene expression in response to the intracellular metabolite, acetyl phosphate [START_REF] Farmer | Improving lycopene production in escherichia coli by engineering metabolic control[END_REF].

Perhaps the most exciting aspect of bactoputing would lie in the development of a totally new high language for computing based on the language that bacteria themselves speak (divide, replicate DNA, mutate, lyse, produce phage, conjugate etc.). As our understanding of regulation in bacteria increases, our capacity to manipulate bacteria -to give them instructions -also increases. But if we can speak to them, can we also listen? For that, we need better access to the phenotypes of individual bacteria. Technological advances in 'omics' will one day -perhaps soon -give rapid access to information on the proteomes, phosphorylomes, lipidomes, interactomes, metabolomes etc. of large numbers of individual cells. Bactoputer scientists should be preparing for this day now.

Acknowledgements

We thank the Epigenomics Project for support. VN thanks Philippe Marliere for several ideas as well as A. N. Walker for the course available on www.maths.nott.ac.uk/personal/anw/G12FCO/