Automata Modeling of Quorum Sensing for Nanocommunication Networks

Automata Modeling of Quorum Sensing for Nanocommunication Networks Author: Sergi Abadal Cavall´e Advisor: Ian F. Akyildiz July 6, 2010 Broadband Wireless Networking Lab, Georgia Institute of Technology, Atlanta September, 2009 — May, 2010 NaNoNetworking Center in Catalunya, Universitat Polit`ecnica de Catalunya, Barcelona June, 2010 — July, 2010 Abstract Nanotechnology is enabling the development of devices in a scale ranging one to hundreds of nanometers. Communication between these devices underlying in the nanoscale greatly expands the possible applications, increasing the complexity and range of operation of the system. Several options for nanocommunications have been discovered and studied, and many of them take some natural mechanisms and processes as a model, or directly use different elements from nature to serve its purposes. For instance, in molecular communications, the information is encoded in tiny particles secreted by the emitter. In this work, a special case of molecular communications is studied and modeled. Quorum Sensing is a mechanism used by bacteria to sense their own population and coordinate or synchronize their actions, through the emission and sensing of molecules called autoinducers. The behavior of each bacterium involved featuring Quorum Sensing is modeled as an individual finite state automaton, capturing its course of action. Later, the design of a novel nanomachine that will include Quorum Sensing is presented, along with its applications. Mainly, Quorum Sensing will serve to synchronize the processes of a group of nanodevices, and this idea is developed to present “Collective Actuation Synchronization” and “Collective Actuation after Localized Sensing” nanomachines. Finally, these configurations are implemented and simulated, and the results are later discussed. Acknowledgements I would like to take the opportunity to thank all the people that helped me during this fascinating journey in which I can say that I learnt a lot about life and about nanocommunications. First of all, I would like to thank my family and friends, which understood my decision and supported me from the beginning. Without them, none of this would have been possible. I would also like to thank Professor Ian F. Akyildiz, for giving me the opportunity to work with him and the marvelous people at his charge, as well for his supervision and advising. Speaking of people at his charge, I am extremely happy to have worked with this fantastic group of people at the Broadband Wireless Networking Lab, especially with the guys at the nanocommunications group, to whom I deeply thank for their helpful remarks and advise. Josep Miquel Jornet, Massimiliano Pierobon, Luis Carlos Cobo, Joan Capdevila, part of this thesis has been possible thanks to you. For their financial support, I would like to thank “Fundaci´on Vodafone Espa˜na”, “Obra Social Bancaja” and “Generalitat de Catalunya”. Whereas I greatly appreciate the institutional support that ETSETB has offered so that I can enjoy this fantastic experience. I would specially like to thank Eduard Alarc´on and Josep Sol´e Pareta for their support. To all, thank you! Contents 1 Introduction 6 1.1 Nanotechnology.................................. 6 1.2 Nanomachines................................... 7 1.3 Interaction Between Nanomachines . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Assembling Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5 Applications.................................... 15 1.6 Motivation of This Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Quorum Sensing 18 2.1 Principles and Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.1 Autoinducers ............................... 20 2.1.2 Thresholds ................................ 20 2.2 Types of Quorum Sensing Systems . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Combination of Quorum Sensing Systems . . . . . . . . . . . . . . . . . . . 23 2.4 Bacterial Behaviors Controlled by Quorum Sensing . . . . . . . . . . . . . . 25 2.4.1 QuorumQuenching ........................... 29 2.5 Conclusion and Research Challenges . . . . . . . . . . . . . . . . . . . . . . 30 3 Automata Modeling of Quorum Sensing Bacteria 31 3.1 Introduction to Automata Theory . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Existing Models of Quorum Sensing . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Automaton Modeling of Quorum Sensing . . . . . . . . . . . . . . . . . . . 35 3.3.1 Pre-Quorum Section . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2 3.3.2 Post-Quorum Section . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Complete Model of Quorum Sensing Bacteria . . . . . . . . . . . . . . . . . 42 3.4.1 Simplified Model of Quorum Sensing Bacteria . . . . . . . . . . . . . 46 3.4.2 Extension to Combined Quorum Sensing Systems . . . . . . . . . . . 47 4 Interaction between Bacteria in Quorum Sensing 50 4.1 Environment Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Diffusion of Autoinducers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2.1 Fick’s Laws of Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2.2 Finite Differences Method Applied to Fick’s Laws . . . . . . . . . . 55 4.3 Transmission and Reception of Autoinducers . . . . . . . . . . . . . . . . . 55 4.4 Communication Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 Quorum Sensing Simulation and Performance Results 60 5.1 Algorithm..................................... 61 5.1.1 Assumptions ............................... 64 5.2 Results....................................... 66 5.3 Discussion..................................... 69 6 Nanomachine Design Based on Quorum Sensing Bacteria 72 6.1 Nanomachine Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.2 Applications.................................... 75 6.3 Collective Activity Synchronization . . . . . . . . . . . . . . . . . . . . . . . 77 6.4 Collective Actuation after Localized Sensing . . . . . . . . . . . . . . . . . . 82 7 Nanomachine Simulation and Performance Results 87 7.1 RelaxationTime ................................. 87 7.2 Collective Activity Synchronization . . . . . . . . . . . . . . . . . . . . . . . 89 7.2.1 Algorithm................................. 89 7.2.2 Results .................................. 91 7.3 Collective Actuation after Localized Sensing . . . . . . . . . . . . . . . . . . 97 7.3.1 Algorithm................................. 97 Automata Modeling of Quorum Sensing for Nanocommunication Networks 3 7.3.2 Results .................................. 98 8 Open Issues and Conclusions 102 8.1 OpenIssues.................................... 102 8.2 Conclusions.................................... 103 A Calculation of the Relaxation Time 107 Automata Modeling of Quorum Sensing for Nanocommunication Networks 4 Medium range solutions arise after observing that short range techniques are greatly inefficient as the distance grow. Molecular motors move slowly along the tracks (500 nm per second) and it has been observed that they detach after distances longer than 1 µm. In the case of molecular signaling, it is known that the diffusion time is a function of the square of the distance. Thus, at certain distances, the delay can be unacceptable. In [26], two mechanisms of medium range communication are proposed: Flagellated bacteria and catalytic nanomotors. Both of them encode the information in DNA sequences, and guide those to the receiver through a process based on a phenomenon called chemotaxis, by which the bacteria move following gradients of attractant particles. Both mechanisms show speeds tenths of times higher than short range techniques, as well as increased reliability at distances of several micrometers. Figure 1.3: Alternative classification of molecular options. Finally, long range techniques stem from the necessity to communicate nanomachines separated more than 1 mm. Both “wired” and “wireless” solutions have been proposed [50]. Wireless techniques, namely, pheromones, pollen, and spores do not need electrical conductors or other physical link but a fluid medium, to propagate: pheromones are diffusion based, while pollen and spores have to be transported by a flowing fluid. On the other hand, wired mechanisms rely on a physical infrastructure to propagate the message, like the emission and reception of hormones through a network of capillaries. The encoding Automata Modeling of Quorum Sensing for Nanocommunication Networks 11 of the message follows the same fashion as short-range techniques: information can be contained in the rate concentration of the agents we are using, as well as in DNA packets embedded in each of them. The receptors count on a high selectivity, thus binding only to specific agents, particularly in the pheromone and hormone cases [39]. Further information and analysis of these three approaches of molecular communication, and their multiple options can be found in [1, 26, 50] respectively. 1.4 Assembling Approaches In order to manufacture and assemble nanomachines, three different techniques have been stated, namely, top-down, bottom-up and bio-hybrid approaches. Figure 1.4: Approaches for the development of nanomachines. Top-down Approach The top-down approach was the first one to be stated, following the miniaturization tendency in electronics (i.e. Moore’s Law). It was first pointed out by Richard Feynman in the talk that was commented on beginning of this thesis, in which he stated that further miniaturization would be possible in order to write and read information in an atomic scale. Hence, in this approach, nanomachines are developed by means of downscaling current microelectronic and micro-electro-mechanical (MEMS) devices, conserving its architecture, Automata Modeling of Quorum Sensing for Nanocommunication Networks 12 further to the nanoscale [23, 44]. The evolution of classical lithography techniques enabled the manufacturing of components in dimensions below 100 nm. Furthermore, new nanofabrication techniques as microcontact printing [40], imprint lithography [7] and direct-write dip-pen nanolithography [57] have been developed and are currently used. It was in 2000, that Intel started the large-scale production of transistors with lengths below 100 nanometers, using these new techniques. In fact, CMOS transistors measuring 45 nm or even 32 nm long have been developed, and it has been envisaged that 22, 16 and 11 nanometer transistors will be manufactured in the near future. Bottom-up Approach In the bottom-up approach, nanomachines are constructed using individual molecules as building blocks, in a process called molecular manufacturing [17]. Or, generally speaking, smaller components are use to build up more complex assemblies [2]. An example of an existing type of manufacturing based in this approach is the assembly by DNA scaffolding. In this technique, structures of synthesized DNA known as “DNA origami” are arranged in a silicon surface, serving as a mold to assemble different nanoscale components particle by particle [53]. DNA sequences are composed by series of nucleotides, namely, adenine, guanine, thymine and cytosine, which are complementary two by two. The particles to assemble have DNA strands complementary to the strands present in the scaffold. This way, they can only be connected to the silicon surface in a single position with a defined orientation. The synthesizing of DNA strands is programmable, making this technique suitable for nanomachine manufacturing. Furthermore, it has been shown that the use of DNA origami makes the placement of atoms or molecules 100% accurate [3, 27]. Bio-hybrid Approach In this approach, also known as bio-inspired or biomimetic, biological components are proposed as models for new nanomachines, or even used as building blocks, integrating them into more complex systems [1]. Hence, it involves the understanding, conceptualization and/or mimicking nature’s ways of handling various problems or situations. Automata Modeling of Quorum Sensing for Nanocommunication Networks 13 Often, inside cells, we can find lots of biological structures that carry out functions such as sensing, actuation, storing, control [16], executed in a highly effective and energy efficient ways. Moreover, these natural nanomachines show some properties that would be desired for future nanomachines: •Self-continence: usually cells have their set of instructions completely specified in the DNA of its nucleus or nucleoid. •Self-replication: is the property through which nanomachines autonomously replicate themselves and its set of instructions. •Self-assembly: is defined as the process in which several disordered elements form an organized structure without external intervention, as a result of local interactions between them. An example of them is stated when the bottom-up approach was explained. DNA scaffolding creates new nanomachines helped by the self-assembly property, owing to the fact that the binding of complementary DNA strands is a non externally-driven process. In addition, other characteristics, desired in the creation of new nanomachines, exist in nature. Locomotion is one of them, and can be accomplished, by instance, through different organelles such as flagellum, present in several bacteria like E. Coli.Communication capabilities are also envisaged to be important, and different examples of natural components that enable this characteristic can be found in Section 1.3 (e.g. molecular motors or communication through flagellated bacteria). All in all, the bio-hybrid approach is considered the most promising of all assembling techniques, because the complexity of its components and the good properties that intrinsically are contained in them. Bottom-up also shows great promise, due to the fact that each atom can be arranged at will. On the other hand, the top-down approach offers great possibilities nowadays, but the potential of the other two options seems that will pave the best way for nanodevice manufacturing and assembly. Automata Modeling of Quorum Sensing for Nanocommunication Networks 14 1.5 Applications Like briefly stated in Section 1.3, nanonetworks expand the possible applications of nanomachines in an almost unlimited extent. Mainly, nanonetworks applications can be classified in five big areas: biomedical, environmental, industrial, military, and ICT applications [1, 34]. Nevertheless, nanotechnology plays a fundamental role in the manufacturing of lots of devices nowadays, thus affecting fields other than the five main areas (e.g. consumer electronics or sports-related fields). Biomedical Applications The most direct applications of nanonetworks are considered to be in the biomedical field. In fact, it is probably the first area in which intuitively scientists think when talking about nanomachines’ applications, because of nanomachines’ size and their envisioned biocompatibility. Concrete applications in this field are immune system support [6], bio-hybrid implants or tissue engineering [16], health monitoring mechanisms,drug delivery systems [20] and applications including genetic engineering. Environmental Applications Especially, bio-inspired nanodevices (such as nanofilters [29]) and nanonetworks can be applied in the environmental field to reach several goals unachievable with classical technologies. Biodegradation purposes,animals and biodiversity control, and air pollution control are good examples of environmental applications. Industrial and Consumer Goods Applications Nanonetworks can help with the development of new materials, manufacturing processes and quality control procedures. Automata Modeling of Quorum Sensing for Nanocommunication Networks 15 Examples of this kind of applications would be food and water quality control, or functionalized materials and fabrics (e.g. stain-repellent or antimicrobial [65] textiles, and easyto-clean surfaces or paints). Military Applications The range of operations of nanonetworks applied to military applications is really wide. Small scope applications could be used just to monitor soldiers’ performance through nanofunctionalized equipments. On the other hand, nanonetworks covering broader areas can be deployed in order to monitor the battlefield, to detect chemicals or toxics, for instance. It receives the name of nuclear, biological and chemical (NBC) defenses. ICT Applications Information and Communication Technologies (ICT) will obviously take advantage of all the potential and new features that nanonetworks offer, as networking is one of the pillars of ICTs. Examples of this kind of applications are: the integration of nano-sensor networks [59], distributed information access, and Future Internet. In S3ection 6.2, applications in which the work of this thesis can help improve performance, are explained in more detail. 1.6 Motivation of This Work Nanotechnology in general, and nanonetworks in particular, are fields that have attracted a lot of attention the last years and this interest will do nothing but increase in the future. As telecommunication engineers, the focus of this study is on discovering new tools for the communication between nanodevices. Synchronization between the nodes of a nanonetwork is not easy to accomplish, due to the inherent characteristics of the nanodevices, specially issues involving complexity and energy needs. Individual clocks maintain nodes working continuously, which is not energy Automata Modeling of Quorum Sensing for Nanocommunication Networks 16 efficient. Whereas, a global clock [41] is not suitable in nanonetworks based on molecular communications, owing to the fact that information travels at low speeds. Also, a solution based on cellular automata and the classical “firing squad problem” [68, 66] would be unfeasible because synchronization between neighboring nodes is need in the first place. In this work, Quorum Sensing is analyzed as a possible solution to the challenge of coordinating nodes in a nanonetwork using molecular communication. Quorum Sensing is a mechanism used by bacteria to sense their own population and coordinate or synchronize their behavior depending on the result of that sensing. This process is achieved by means of production, emission and reception of certain molecules, and lets the bacteria to actuate collectively. We believe that Quorum Sensing can be applied to nanomachines with communication capabilities, in order to enable synchronization or coordination with the nodes in its close environment. Even though biological and mathematical models of Quorum Sensing have appeared over the years, a computational model that captures the course of action of bacteria that perform Quorum Sensing is still needed. Automata theory is a powerful tool that allows us to depict the behavior of these bacteria, identifying their different states, and the reaction to different inputs. Moreover, the resulting automata model can be later used as the control unit of a nanomachine that features Quorum Sensing. ————————— The rest of the thesis is organized as follows: In Chapter 2, the concept, principles and mechanisms of Quorum Sensing are introduced and explained, as well as concrete applications that could benefit from it. An application-independent automaton model for the bacteria that participate in Quorum Sensing is presented in Chapter 3, whereas the interaction between those bacteria is discussed in Chapter 4. Chapters 3 and 4 serve as the theoretical basis to develop a simulator, which is introduced in Chapter 5 and includes the first results. An analogous path is followed in Chapters 6 and 7: two different nanomachines based in Quorum Sensing bacteria are developed in the former, while simulation and results are presented in the latter. Finally, conclusions and open issues are stated in Chapter 8. Automata Modeling of Quorum Sensing for Nanocommunication Networks 17 Chapter 2 Quorum Sensing Quorum Sensing is a biological process by which bacteria are able to communicate via signaling molecules called autoinducers. Major discoveries regarding the phenomena of bacterial communication were made in the 60s and the 70s, yet it was not until the 90s that Quorum Sensing was concisely defined. W. Claiborne Fuqua, one of the most cited scientists that pointed out the existence of this process, stated that “groups of bacteria exhibit cooperative behavioral patterns” [21]. Precisely, by means of Quorum Sensing, bacteria are somewhat aware of the cell population density, and use that information to regulate their gene expression in a collective manner. Considering that the gene expression determines the behavior and functions of a living organism, Fuqua’s initial observation was on the right track. The evolutionary reason behind the communication capabilities of bacteria is quite clear. Quorum Sensing enables the control of bacterial functions or processes that are unproductive when undertaken by an individual bacterium but become effective when undertaken by the group [31]. For instance, many bacteria species need to launch attacks in order to survive or spread. If a bacterium alone launches an attack, host’s defenses will eliminate the threat immediately. Whereas if a large group of bacteria launches an attack, the success rate rises enormously. Fuqua was the first one to introduce the term “Quorum Sensing”, which summarizes the concept, as the definition of Quorum is, “the number of members of a group or organization required to be present to transact business legally” [12]. Then, Quorum Sensing would be, 18 in plain words, to make sure that there are enough members of the group to carry out a certain function. The importance of Quorum Sensing is indisputable. Actually, it has been described as “the most consequential molecular microbiology story of the last decade” [36]. In fact, Wagner et al. [67] report that in P. aeruginosa up to 394 genes are activated by Quorum Sensing while 222 are repressed. In a recent review [38], it is estimated that between 6% to 10% of the whole genome is affected by this mechanism. These numbers can give us an idea of how relevant is Quorum Sensing in the cycle of life of bacteria, and the objective is to use this effective process to enable collectiveness between our nanomachines. 2.1 Principles and Mechanisms As Bonnie Bassler summarized in [5], Quorum Sensing is achieved through the production, release, and subsequent detection of and response to threshold concentrations of autoinducers. Bacteria produce and emit a special kind of particles which diffuse in the medium. These particles, called autoinducers, have the ability of triggering the release of more of the same kind, when sensed. Hence, as the population of bacteria grows, the extracellular concentration of autoinducers increases as well. If, at a certain point, the concentration of particles reaches a critical threshold, it means that a certain population has been attained. That situation is sensed by the group, which responds to it with a population-wide regulation of the gene expression. The fundamental part of the process can be regarded as a communication mechanism. The bacterium encodes the message through the synthesis of the autoinducers, and the proceeds to transmit it by means of secretion. The autoinducers propagate following the diffusion laws until arriving to a destination, which will receive it through ligand-binding mechanisms. The global message is encoded in the density of particles, which is later decoded and understood as a gene regulation expression. More insight on that can be found in Section 4.3. Automata Modeling of Quorum Sensing for Nanocommunication Networks 19 2.1.1 Autoinducers Quorum Sensing is a really common process between bacteria. Many different species use it for their purposes in a wide range of possibilities. The type of autoinducer involved in the communication determines if two distinct species of bacteria are in the same conversation or not. As stated before, an autoinducer is a tiny molecule which triggers the emission of more particles of its kind. Which species are going to be able to bind and sense them is determined in its chemical composition. Thus, there will be autoinducers that will enable intraspecies cell to cell communication, and others regarded as interspecies cell to cell communication. Interspecies communication allows the coexistence of different species in highly ordered communities, in which each of them carries out a specific subset of functions [5]. Some autoinducers, such as AI-2 and its synthase LuxS, even being extremely small (up to 4.5 ˚ A), are to be considered as a kind of universal signal. This is due to the fact that this type of autoinducer has been identified in many species, which even differ in the type of apparatus used in its detection (see Section 2.2). The use of LuxS has been identified in more than 20 different species; a list can be found in [4]. 2.1.2 Thresholds The behavior of Quorum Sensing bacteria is determined by the concentration of autoinducers that they sense in the environment. Changes in that behavior are consequence of variations in the concentration, and several thresholds determine when these changes occur. •Activation Threshold: as it has been explained in Section 2.1, when the concentration of autoinducers reaches a certain threshold, the colony performs a populationwide regulation of the gene expression. Therefore, all the bacteria of the colony change their behavior at once. From now on, we will refer to this critical value as “activation threshold”. However, when the behavior of Quorum Sensing is studied in depth, other threshold values appear. Automata Modeling of Quorum Sensing for Nanocommunication Networks 20 bacterium is too low to be seen or used in a beneficial way for the species, making Quorum Sensing a necessity. The example usually described to illustrate this case refers to the Euprymna scolopes. It is a small squid, 40 mm long in average, that is indigenous to the Hawaiian archipelago. It lives in shallow waters associated to coral reefs and sand flats, where it buries itself during the day to escape predators. At night, the squid comes out to hunt, therefore being more vulnerable at this time. Actually, the moonlight goes through the shallow waters and is able to cast shadows on the sand surface, situation that can be used by predators to detect the position of the squid and catch it. Here is when the symbiosis between E. scolopes and the bacteria V. fischeri comes into play. The squid hosts a small colony of those bacteria in an organ that lies in the mantle cavity of the animal (given in Figure 2.4). This colony remains deactivated during the day, but growing inside the organ. At night, the colony will have reached a certain population and Quorum Sensing will work, thus activating the bioluminescence. Light emitted by the bacterial symbionts is used by the squid to camouflage by means of counterillumination. This is, the animal controls the intensity of the projected light, matching the moonlight shining down and eliminating the shadows. By the time the squid has to bury again in the sand, it frees a 95% of the colony because the host is not able to sustain such a big number of bacteria. Therefore, the cycle repeats as during the day the remaining bacteria will reproduce again so at night the population is high enough to activate. Figure 2.4: Diagram of the ventral view of an E. scolopes sample. Automata Modeling of Quorum Sensing for Nanocommunication Networks 27 A more thorough depiction of the symbiosis between those two species can be found in [56], and a detailed analysis of the gram-negative process that occurs in the activation of V. fischeri in the same case, is offered in [21]. Virulence To survive, many species of bacteria have to launch an attack to their host to cause a certain reaction. For instance, when a certain environment starts to lack nutrients necessary for the bacteria to persist, they might attack to force host-to-host transportation. So, basically, the attack will make the host cough, sneeze, bleed or to have whichever reaction serves to get the bacteria out and in a position to infect new hosts, always in search for a favorable environment. However, as it has been explained in the introduction of this chapter, host defenses can get rid of the bacteria if they launch an attack too early. Therefore, Quorum Sensing is necessary for the colony to delay virulence factor production, until cell number is high enough that secretion of virulence factors will result in a productive infection. Biofilm Formation Both bioluminescence and virulence seem to be, in principle, processes that would only need the intraspecies cell-to-cell communication, if we suppose that virulent species do not use interspecies awareness of population density for its purposes. However, there are natural processes that take advantage of interspecies communication to coordinate the action with other kind of bacteria in a reciprocally beneficial way. The formation of biofilms is a process in which interspecies communication has been observed. In biofilms, bacteria anchor themselves to a surface, facilitating the adhesion of more of them, forming a layer over the surface. In some cases, species of bacteria without attachment capabilities adhere directly to the colonists that previously anchored on the surface. It is during this process than interspecies Quorum Sensing takes place. In fact, in biofilms bacteria are organized into elaborate framework. Different species are located in specialized regions, and a flow of nutrients is provided by aqueous channels through the entire structure. Moreover, biofilms are highly resistant to antibiotics and Automata Modeling of Quorum Sensing for Nanocommunication Networks 28 desiccation. Consequently, it is not strange that bacteria benefit from communal living, as it increases highly its chances of survival. Therefore, Quorum Sensing is essential as a way to communicate the different species. For instance, AI-2, explained in Section 2.1.1 as a sort of universal autoinducer, has been shown to be required for mixed species biofilm formation between Streptococcus gordonii and Porphyromonas gingivalis, members of biofilm communities in dental plaque [31]. 2.4.1 Quorum Quenching It is not surprising that different species have developed strategies to interfere with Quorum Sensing, since Quorum Sensing controls fundamental processes involved with both bacterial physiology and virulence. Autoinducer antagonists, autoinducer destroying enzymes, and other mechanisms for consuming autoinducers are now known to enable “Quorum Quenching” [15]. Therefore, basically, Quorum Quenching can be regarded as all the mechanisms that prevent the correct operation of Quorum Sensing. On one hand, autoinducer destroying enzymes or other consuming mechanisms would reduce the concentration of autoinducers to a level below the threshold, thus avoiding the collective gene regulation. On the other hand, a flood of fake autoinducers or any particle that can act as an autoinducer for a specific species, would trigger the gene regulation in an unfavorable situation. Nevertheless, Quorum Quenching studies have been started recently, and they suggest that many other different mechanisms exist and await identification. Examples of these mechanisms have been observed in both intraspecies (Staphylococcus aureus) and interspecies (some Bacillus) Quorum Sensing processes. The motivation for its use does not have to be necessarily competence, though. Bacteria can organize and sequence their actuation by the use of this process, and also Quorum Sensing. For instance, if a behavior (A) is not compatible with another one (B) in a community, the release of autoinducers to trigger the behavior A will come together with the release of Quorum Quenching agents for the behavior B. The medical community has put a lot of effort in this point, due to the fact that it might be interesting for a really concerning area: antibiotics. As it will be explained in Section 6.2, in view of antibiotics resistance gained by the bacteria, a new way of defeating bacterial Automata Modeling of Quorum Sensing for Nanocommunication Networks 29 illnesses would be to alter the normal course of Quorum Sensing, either with autoinducer destroyers, or causing a premature regulation of the gene expression. 2.5 Conclusion and Research Challenges Quorum Sensing is an apparently simple way of communicating bacteria with an apparently easy operation. Nevertheless, with decades of research on this topic, only the surface of a really complex mechanism has been scratched. Different autoinducers, receivers, and behaviors governed by Quorum Sensing have been discovered. However, lots of more types of autoinducers, bacteria, mechanisms of Quorum Quenching, and connections between species await to be discovered and explained. In the beginning of this thesis, it has been pointed out that nanotechnology is a highly multidisciplinary field. Obviously, biology is one of those disciplines, and in fact, plays a key role to understand natural processes. As engineers, our objective is to model these processes with tools that later will help us to apply the theoretic principles in nanomachines. In this case, the creation of nanomachines with communication and coordination capabilities is the challenge, and Quorum Sensing seems to be a good phenomenon to look upon as a model. Automata Modeling of Quorum Sensing for Nanocommunication Networks 30 Chapter 3 Automata Modeling of Quorum Sensing Bacteria So far, nanotechnology and more in depth Quorum Sensing, has been introduced. From now on, the objective is to formally model the process of Quorum Sensing, thus enabling the abstraction from the biologic phenomenon. This way, a study of the mechanism can be conducted more from a communication perspective. Quorum Sensing is a particular communication process in which, considering the intraspecies case, all the agents are identical. The strategy followed is to model the bacteria from the emitter and receiver perspective, which are also connected, in turn. Once this is done, big part of the global model is achieved. Automata theory gives the necessary tools to characterize the bacterium as a Finite State Machine (FSM), which in the future can be used to program nanodevices with communication capabilities. This approach has been chosen mainly because enables the ICT community to understand the biological processes that occur in nature, and its dynamics. After that, modeling of the environment and the interaction between bacteria has to be addressed, since communication is the basis of the Quorum Sensing phenomenon. The rest of the chapter is organized as follows. First, a brief introduction to automata theory is presented. After that, we discuss why automata theory is selected between other 31 model options, as a motivation. Finally, the model is developed, describing the steps followed to arrive to the actual model, which will be stated in Section 3.4. 3.1 Introduction to Automata Theory Let Σ be a finite and non-empty alphabet which elements are called symbols. Finite sequences of symbols are called words. Let Σ∗be the set of all the possible words in Σ, where the empty word is defined by . A language is a subset of Σ∗. Hence, an automaton is a device which is able to recognize and comprehend a certain language and behave accordingly with the reading of the input symbol and the internal state. Definition 3.1.1. Adeterministic finite state automaton is a system A={Q, Σ, δ, q0, F}, where Q is a finite set of the possible internal states of the automaton A, Σ is a finite alphabet, q0is the initial state, δis the transition function (δ:Q×Σ→Q) and F is a subset of Q, the set of final or acceptance states. The automaton reads the input, which will be a symbol of Σ, and computes the next state q0as a function of the input, say a, and the present state qusing the transition function, thus, q0=δ(a, q). Then, the automaton moves to state q0and reads the new input symbol of the system, b, and again computes the next state, q00, as a function of δ, q00 =δ(b, q0). This definition, together with other types of automata and further explanation for all of them, can be found in the reference book “Introduction to Automata Theory, Languages and Computation” [33]. It includes non-deterministic finite state automaton which is the result of giving the possibility for a transition not to be defined, or for that transition to have multiple options for the same input. The non-deterministic automaton allows this behavior by defining δas a relation instead of as a function. Also the probabilistic finite state automaton is defined, allowing the transitions to be defined by a probability that depends on the input. However, let now Λ be another alphabet, similar to Σ. Then: Definition 3.1.2. AMoore machine is a six-tuple A={Q, Σ,Λ, δ, τ, q0}, where Q is a finite set of the possible internal states of the automaton A, Σ and Λ are finite alphabets Automata Modeling of Quorum Sensing for Nanocommunication Networks 32 for the input and the output, respectively, q0is the initial state, δis the transition function (δ:Q×Σ→Q) and τthe output function (τ:Q→Λ). Basically, the Moore machine is a deterministic finite state automaton in which each state is bound to an output. The model for the Quorum Sensing bacteria will be based in aMoore machine, since all the transitions are fixed, and an output has to be defined. It will be developed and explained in detail in Section 3.3 and finally stated in Section 3.4. 3.2 Existing Models of Quorum Sensing The attention that Quorum Sensing has attracted in engineering areas is patently obvious from the quantity and variety of models and simulations that have been done. This section will serve to discuss the shortcomings of some examples, which in turn will be the reason why an automaton model is developed. •Mathematical Models [13, 24, 48], also referred as stochastic models, these are based on the use of differential equations that describe the chemical kinetics of the reactions found inside the bacteria. The authors introduce variables for each protein and enzyme concentration, and express the change of those in terms of protein production and degradation. This chain of reactions leads to the expression of autoinducer production in terms of the intracellular and extracellular concentration, which are the catalysts of the reaction, in the end. Results are extracted from the different solutions and the stability analysis. However, enzyme reaction chains that trigger gene regulation in Quorum Sensing vary from each species to another. Although all these different systems have been classified into three big groups (Gram-positive, Gram-negative, and hybrid; see Section 2.2), different species will end up having unique parts in their scheme apart from the common structure. For instance, in [48], a general mathematical model of Quorum Sensing in Gram-negative bacteria is shown, even though different species have distinct enzyme structures. Hence, specific models of Quorum Sensing for concrete species have been also developed, like in the cases of Pseudomonas aeruginosa [13] or the Agrobacterium family [24]. Automata Modeling of Quorum Sensing for Nanocommunication Networks 33 Another shortcoming of this approach is the lack of connection between bacteria, their enzyme reactions, and the environment. Parameters like the colony population, and factors like the interaction between bacteria or the bacterial reproduction, are the key to achieve Quorum Sensing. None of these necessary concepts is mentioned in the mathematical model of the enzyme reactions. •Computational Models [63] simplify the chemical reactions that occur inside the bacteria, and are more centered on creating a general and macroscopic framework in which bacteria are basic elements present in an environment. This approach overcomes one of the shortcomings present in the mathematical models, in which the environment was not taken into account. However, in [63], the bacteria are organized into clusters. Actions such as the emission of autoinducers are considered to be performed by the cluster, not by each one of the basic elements. This becomes the major shortcoming of this option, as bacteria sense the environment, emit autoinducers, and reproduce themselves as individuals. We cannot assume that all these actions are performed at the same time by all the bacteria in the colony, and in the same way. Advantages of Automata Modeling The principal motivation of trying to model Quorum Sensing bacteria as automata, is to eliminate all the shortcomings identified in the existing models of this natural process. 1. Understanding all the reactions that are triggered inside the bacteria when Quorum Sensing is being performed is really important. However, once the different behaviors of these bacteria have been identified, these enzyme reactions can be simplified and taken as a black box. This way, a general model of Quorum Sensing for all the species of bacteria can be developed. At the same time, the simplicity of the model is preserved. 2. Quorum Sensing is a process that involves communication between bacteria. Knowing how bacteria behave is as important as knowing how the environment affects the communication or interaction between bacteria. In our model, the behavior of bacteria Automata Modeling of Quorum Sensing for Nanocommunication Networks 34 is captured by the automata and, at the same time, the environment plays a key role in the interaction of these automata. This way, a balance between the insufficient level of detail of the computational model presented, and the excessive level of detail of the mathematical models, will be achieved. 3. Self-reproduction is a key element in the achievement of Quorum Sensing, since a colony of bacteria need to reach a certain population to activate a certain behavior. 3.3 Automaton Modeling of Quorum Sensing A general model of the behavior of a bacterium that participates in Quorum Sensing to regulate its gene expression can be accomplished with automata theory. In fact, the objective is to try to match the process as a deterministic finite state machine. Basically, a bacterium in a colony which has not reached quorum has the following simplified routine: First, the bacterium senses the autoinducers concentration in its close environment. This result is processed and compared with the activation threshold (see Section 2.1.2). So, a decision is to be made: •If the concentration is below the threshold, the bacterium will release a given amount of autoinducers, which will depend on the intracellular concentration as well. •On the other hand, if the concentration is above the threshold, the gene regulation is performed, thus changing the behavior of the bacterium. This cycle is continuous, meaning that the bacteria will sense the environment and release autoinducers in an infinite loop as long as the concentration sensed is below the threshold. Once the concentration exceeds the limit, the loop breaks and the gene regulation will follow. After the change of behavior, the bacterium will again control the concentration of autoinducers to sense the population of the colony. The purpose of this new loop is to ensure that the concentration is still over a certain different threshold. Thus, the bacterium Automata Modeling of Quorum Sensing for Nanocommunication Networks 35 keeps in this state until the density of the cluster falls below a certain level, moment in which will return to the initial state. Overall, the course of action described can be regarded as an ON-OFF switch. In fact, Quorum Sensing has been named “gene expression switch” in numerous occasions [13, 24, 63]. This is a good starting point to develop the model, due to the fact that the finite state machine representation of an ON-OFF switch is widely studied: Figure 3.1: States diagram for an ON-OFF switch. The starting state, SOFF , is the OFF or low density behavior. The transitions correspond to the options explained before: only the loop will be broken if the threshold is surpassed, thus causing the machine to jump to the ON state (SON ). Once there, the gene regulation is performed and the machine will stay in that state until the concentration sensed (R) falls below the second threshold. It is important to remark that the two thresholds introduced (TON and TOF F in the previous figure) do not have to be the same. In fact, it is believed that they inherently ensure a hysteretic behavior in the switch (TON > TOF F ), thus avoiding easy reversal of each change of state. From now on, this will serve as the most basic model. The initial or OFF state will be called Pre-Quorum section, as the critical population or quorum has not been reached. In the same fashion, the ON state will be called Post-Quorum section. Both of them will be fully developed in the next subchapters, to give shape to the complete model. 3.3.1 Pre-Quorum Section While being in this part of the automaton model, the cluster of bacteria has not reached the critical density of population to activate, meaning that the amount of autoinducers in Automata Modeling of Quorum Sensing for Nanocommunication Networks 36 States (Q) The states that form the automaton for the Quorum Sensing bacterium are: Q={S1, E1, S2, E2, S3, E3, B} where B={b1, b2, b3, . . . , bn}is the subset of states that represent the model of the behavior that the bacteria show after reaching Quorum. Each behavior, namely, motility, antibiotic release or bioluminescence, amongst others, determines the model that will lead to a certain subset Bof states, and the cardinality of it (n) is subject to that model. As for the rest of the automaton, the sensing states S1,S2and S3dictate the emission to be done (state E1,E2or E3), as well as the future state, indirectly. Input Alphabet (Σ) As it has been explained in Chapter 2, bacteria sense autoinducers coming from other cells of the same colony. The autoinducers themselves cause chemical reactions that mark the Quorum Sensing process. When it comes to modeling it, the symbols of the alphabet will be regarded as internal signals that are created in those chemical reactions, like stated in the beginning of the Section 3.4. Knowing this, the alphabet of possible inputs of the automaton will be: Σ = {d1, d2, d3, d4, X} where X={x1, x2, x3, . . . , xn}are the inputs that might be needed to model the transitions between the states that represent the post-Quorum behavior of the bacterium. The rest of the symbols of the input alphabet serve to model how the input of the cell R affects its behavior, taking into account the different thresholds that have been introduced: d1=R > T1 d2=R < T2 d3=R > T3 d4=R < T4 Automata Modeling of Quorum Sensing for Nanocommunication Networks 43 Symbols d1and d3activate when the received concentration surpasses the basal to autocatalytic threshold and the Quorum threshold, respectively. On the other hand, d2and d4 activate when the concentration is lower than the autocatalytic to basal thresholds. These internal inputs can also be regarded as biological events inside the cell. For instance, in gram-negative bacteria using the autoinducer LuxI, the activation of d3of the model coincides with the binding of the autoinducer with the LuxR transcriptional activator protein that triggers the process that ends up with the change of behavior. Output Alphabet (Λ) Also it has been explained before that the outputs suffer the reverse treatment. The output alphabet is formed by symbols that will trigger the production of external outputs, in this case, autoinducers. The alphabet of outputs in the Quorum Sensing bacteria model is: Λ = {l1, l2, Y } where Y={y1, y2, y3, . . . , ym}are the outputs that might be needed to complete the model of the post-Quorum behavior of the bacterium. The rest of the symbols of the output alphabet serve to model the quantity of autoinducers that the cell will emit. In fact, l1represents a basal level emission, and l2indicated that an emission in autocatalytic levels will be done. Although the quantity of autoinducers emitted by Quorum Sensing bacteria varies within those two levels, for the sake of simplicity, only the emission in these two extremes are considered. Transition Functions (δ) Basically, the transition functions between the states are the ones shown in Figure 3.5, and summarized in the Table 3.1. In the table, the rows represent the state in which the automaton is, and the columns are the future state in which the automaton will be after applying the transition function. When Σ appears as a transition, it means that no matter which input is entered in the automaton, the next state is fixed and unique. Automata Modeling of Quorum Sensing for Nanocommunication Networks 44 d1d2d3d4X →S1E2E1E1E1E1 E1S1S1S1S1S1 S2E2E1B E2E2 E2S2S2S2S2S2 S3E3E3E3E1E3 E3BBBB B B BBBB{B, S3} Table 3.1: Transition function (δ) of the bacterium automaton. Regarding the set of states which represent the post-Quorum behavior (B), the internal transitions between their states is determined solely by the inputs defined for it (X). The transitions that mark the entrance to that set of states Bare known, but those that mean the exit of Bare also determined by the set of inputs X. Remember that both Band X are subsets that depend on the post-Quorum behavior to model. Output Function (τ) The output function is a simple mapping of an output for each state. Two symbols appear in the output alphabet: l1indicates that an emission at a basal rate is to be performed, whereas l2indicates an autocatalytic emission. Then, these symbols will be assigned to each emission state: basal emission for E1in the pre-Quorum section, and autocatalytic for the other two states. Regarding the sensing states, when the environment is being perceived, there will be no output. This situation can be represented with the symbol , meaning the empty word, and can be interpreted as that, while in the sensing states, the autoinducers emission will not suffer any modification. STATE S1E1S2E2S3E3B OUTPUT  l1 l2 l2Y Table 3.2: Output function (τ) of the bacterium automaton. Automata Modeling of Quorum Sensing for Nanocommunication Networks 45 In the case of the post-Quorum behavior states, B, the output depends on the behavior that is being modeled. For instance, antibiotics emission is one of the functions that bacteria perform after Quorum Sensing, and would require of a special output defined in Yto trigger the release of the antibiotics. Initial State (q0) The starting state should be placed in the pre-Quorum part, owing to the fact that obviously no bacteria will start with the post-Quorum behavior activated. Even if the genetic replication of a certain bacterium takes place when the post-Quorum behavior is activated, the new born cell will not have enough intracellular concentration of autoinducers to stay in the post-Quorum section. Therefore, it will return shortly to the basal emission states. This is why S1is selected as the initial state. q0=S1 3.4.1 Simplified Model of Quorum Sensing Bacteria The automaton model presented in Section 3.4 is not minimal, meaning that an automaton with a lower number of states and the same behavior, can be found. However, the finite state machine presented serves to exemplify better the behavior of Quorum Sensing bacteria, and the causality of the sensing and emission states. Observing the states diagram and the transition table, it is clear that the transitions from the emission states does not depend on the input. Due to the multitasking nature of the living organisms, we will introduce the following modification: sensing and emission states are merged. The new states will be of the form SEi, the output of that state will be determined by the output of the substate Ei, whereas the transitions are determined by the substate Si. This modification will serve to maintain the simplicity of the automata presented in the next section. Combination of different Quorum Sensing systems are shown, and their representation in state diagrams would not be feasible if sensing and emission states were to be considered separately. Automata Modeling of Quorum Sensing for Nanocommunication Networks 46 Figure 3.6: Simplified states diagram for the Quorum Sensing bacteria. 3.4.2 Extension to Combined Quorum Sensing Systems The model presented and later simplified in this chapter is suitable for simple Quorum Sensing processes, meaning that only one type of autoinducers is involved. But, as stated in Section 2.3, there exist more complex systems that combine different types of the aforementioned simple Quorum Sensing mechanisms. Concretely, there are species that rely on two different types of autoinducers to regulate target genes, in a parallel fashion. To reach the change of behavior the activation of both Quorum Sensing systems at the same time is necessary. Using the simplified model for simple Quorum Sensing, and the SE states (see Section 3.4.1, a design for this option is presented. Now, two different inputs are taken into account: the concentration sensed for each type of autoinducer, represented by R1and R2. These are to be compared with both autocatalytic and activation thresholds, that can be different for each branch (for instance, TOF F,1,TON,1and TOF F,2,TON,2are the activation thresholds for each type of autoinducer). Thus, the transition between states will follow the same fashion as in the model for simple Quorum Sensing. The pre-Quorum part is the section that will suffer modifications. Let the first Quorum Sensing system be A, and the second one be B. New SE states are introduced, and each of Automata Modeling of Quorum Sensing for Nanocommunication Networks 47 Figure 3.7: States diagram for complex Quorum Sensing system (AND). them represents a duple {Ai, Bi}. Each element of the duple tells in which situation each system is into: basal emission, autocatalytic emission, or activation. All the possibilities will be contemplated, and a state for each possibility will be proposed. The transitions between states only contemplate contiguous changes in only one system at a time. The objective of this model is to reach the post-Quorum states, or activate, only when both systems reach activations at the same time, which would work as an AND gate between the systems A and B. The model is shown in Figure 3.7. The initial state is SE1, with both systems emitting at basal rate. If system A surpasses its first threshold, it will emit at autocatalytic rate, whereas the system B still at basal rate SE2. If then system B does the same, both will emit at autocatalytic rate SE4. After that, in the hypothetical case that A activates, a transition to state SE7will be made. The last step is to B to activate, in which case the post-Quorum behavior is activated. Once in the post-Quorum section, the sensing and emission are still done. If one of the systems goes below its deactivation level, the bacteria will turn to the pre-Quorum states. Automata Modeling of Quorum Sensing for Nanocommunication Networks 48 STATE A B SE1BASAL BASAL SE2AUTOCATALYTICAL BASAL SE3BASAL AUTOCATALYTICAL SE4AUTOCATALYTICAL AUTOCATALYTICAL SE5ACTIVE BASAL SE6BASAL ACTIVE SE7ACTIVE AUTOCATALYTICAL SE8AUTOCATALYTICAL ACTIVE {B, SEc}ACTIVE ACTIVE Table 3.3: Duples in each state for the AND system. As it can be seen, there is no way to be in the post-Quorum states if either A or B are not activated. In the same fashion, the case where a series of two simple systems converged in the control of a post-Quorum behavior could be modeled. Actually, this general model admits the introduction of new variables and combinations of all of them: combinations that exist in nature and can be really useful in the design of nanomachines, introduced in Chapter 6. Automata Modeling of Quorum Sensing for Nanocommunication Networks 49 Chapter 4 Interaction between Bacteria in Quorum Sensing Quorum Sensing is a process that can be considered collective. It needs a certain number of specimens interacting globally using the signaling molecules called autoinducers. These molecules have to travel from one transmitting bacterium to another unspecified cell that will be the receiver. This receiver can be the cell that is closer to the emitter, or simply the one that intercepts the autoinducer in its erratic path through the environment. Hence, to fully explain and model the Quorum Sensing phenomenon, a description of the environment and the laws that govern the movement of the particles involved, is needed. The chapter will be devoted to do it, complementing the bacterium model. First, a description of usual environment involved in Quorum Sensing is stated. After that, the process of diffusion of the autoinducers is explained, giving the mathematical expressions used to model it. Finally, a discussion about the emission and reception of autoinducers is performed. The contents of this chapter will serve to complete the global model for Quorum Sensing, which will lay the foundations for the simulation of such process and for the extraction of some results (Chapter 5). 50 4.1 Environment Description Quorum Sensing relies on the production, emission and sensing of autoinducers. These autoinducers propagate through the environment in which the bacteria are living, and we need to know that environment in order to be able to implement its properties in the simulation. The variety of species of bacteria that perform Quorum Sensing is astonishingly wide, with more to discover. That means that the environments in which one can find these species are also diverse. Nevertheless, some assumptions will be made regarding those sceneries, in order to simplify the simulations. Namely: •Finite space: reported species of bacteria range in size from barely 50 nm up to 750 µm the biggest. However, spherical or not, the most usual sizes are of the order of a few micrometers. Also, colonies of these bacteria can reach populations of approximately 105individuals, or more, like in the case of Vibrio fischeri [55]. Then, cultures of bacteria participating in Quorum Sensing do not occupy spaces larger than a few millimeters. Not in vain, cultures not exceeding a diameter of 2 mm are considered small, being large if they surpass the 5 mm of diameter [30]. The purpose of this discussion is to make clear that spaces in which bacteria act in Quorum Sensing are small and will be considered finite. Events taking place at several centimeters of distance will not affect the course of action of the culture of bacteria, at least in the short term. •Homogeneous environment: generally, real environments have a set of properties which by default vary spatially and temporally. Also, elements that configure those properties can also change in a constant fashion. However, considering a heterogeneous space, meaning that its properties vary as a function of space and time (randomly or not), would be adding a lot of parameters to the simulations. Thus, the grade of complexity achieved would be too much, and getting the attention off the aspects that really matter. Moreover, it has been already stated that spaces occupied by colonies of bacteria are small, thus changes of the environment properties are limited. Automata Modeling of Quorum Sensing for Nanocommunication Networks 51 Hence, the space will be considered homogeneous, meaning that its properties will be the same throughout all its extension. •Discrete space: in order to make the simulations feasible, we will consider a discrete space. This is, the space will be divided in a number (in our case, finite) of different points, which are considered separately. Different parameters will be assigned to each point in space. Due to this, the resolution of the discretization of the space must comply with some requirements. The most important of them ensures that the calculation of the diffusion of particles is done correctly. The concept of diffusion will be explained next, and the condition regarding the spatial resolution will be stated in Section 4.2.2. Nevertheless, the most important property of the environment is set based on its composition and the size of the agents involved. The viscosity of the medium, added to the fact that particles are nano in size, lead to the scenario in which the particles are subject to viscous forces rather than inertial forces. This can be summarized with the Reynolds Number, which expresses a ratio between inertial and viscous forces. In this case, the fluids in which the autoinducers are spread is considered to be a low Reynolds Number environment. As a conclusion, these characteristics define the environment that will be simulated in the end. The autoinducers emitted by the bacteria will move in a homogeneous low Reynolds number, finite and discrete space, following a process called molecular diffusion. 4.2 Diffusion of Autoinducers Molecular diffusion, or otherly called simply diffusion, is the thermal motion of all molecules at temperatures above the absolute zero. Following this principle, when in a certain environment exists a non-uniform distribution of particles, these tend to diffuse away in order to reach an uniform concentration through all the space [51]. Molecular diffusion can be also considered a specific case of random walk or Brownian motion, which models the random movement of particles suspended in a fluid, and also some other phenomena in diverse fields. Automata Modeling of Quorum Sensing for Nanocommunication Networks 52 4.4 Communication Aspects Despite the considerations made in the previous section, the communication process seen in Quorum Sensing is slightly different from the classical approach. The emitter does not really encode a message in a single autoinducer, thus there is nothing to decode from a single particle of the environment. Hence, a unicast or point-to-point scheme cannot be considered. The only message to be decoded and interpreted is the number of bacteria present in the colony, and this is why the classical approaches are not applicable in this case. The aforementioned message is inherently constructed by the group of bacteria, using the concentration of autoinducers in a sort of amplitude modulation. From the communication perspective, we could define it as a collective communication. Because, in broad terms, all the bacteria are, at the same time, emitters and receivers of the global message. The main feature of this new scheme is that, individually, every node realizes the same bidirectional multicast communication to reach a collective message understood by all: •The multicast property is given by the fact that there exist different types of molecules used as autoinducers, which bind to specific receptors. Therefore, the message is only intended to reach a certain group of receivers. From a information theory perspective, the address of the multicast group is inherently encoded in the chemical structure of the autoinducer. •It is bidirectional because all of the members of the group are capable to receive and transmit their part of the message to the others. Finally, Quorum Quenching strategies can be regarded as a source of noise, attenuation or interference for this communication. For instance, autoinducer destroying enzymes can be considered a source of attenuation, since they diminish the concentration of autoinducers that a node will sense. Also, residual autoinducers from other bacterial communications can be a source of noise in Quorum Sensing, since it can lead to erroneous decisions. Automata Modeling of Quorum Sensing for Nanocommunication Networks 59 Chapter 5 Quorum Sensing Simulation and Performance Results After having described and modeled the behavior of the Quorum Sensing bacteria and having defined the role that the environment and the diffusion of particles play in the process, it is time to implement them and validate those models through simulation. Some simulators have been created in the recent years, as nanotechnology seems to be the key for upcoming groundbreaking achievements regarding Quorum Sensing. •In [32], Hense et al show some results based on simulations using a mathematical model of Quorum Sensing. The details are not disclosed, so we cannot assume that the model of bacteria used in this case is similar or different to the one presented in this thesis. Regarding the parameters involved in Quorum Sensing, this simulator uses some approximations for biological data, instead of using values that might be found in the literature. The outcome of the simulations is a nice analysis of the spatial clustering and activation of bacteria, concluding that the more together they are, the more effective Quorum Sensing is. •On the other hand, in [58], some results based in a new simulator are presented. Although it seems that the objective is to give fancy graphic results, Quorum Sensing theory is applied. The model of bacteria used in this simulator has the characteristics of the “mathematical models” described in Section 3.2, in the sense that all the enzyme 60 reactions are taken into account. Thus, the computational complexity is high and the simulator does not seem to be capable of dealing with a realistic number of bacteria. In fact, results are shown for populations of only tens of bacteria. Apart from the aforementioned shortcomings, these and other simulators do not take into account the reproduction of the agents involved. In the case of bacteria, grow and divide is crucial to reach the population necessary to activate the colony. In order to obtain some results, we believe that modeling reproduction (even if it is in a simple way) is necessary. The simulator has been programmed in C, for its efficiency, modularity and portability. Since a lot of different entities will be present in the environment, the memory efficiency is required to manage all of them. Modularity allows us to program agents separately and to do modifications only in the ones that require them, whereas portability allows the simulator to be reused in the future if it is needed for further implementations. Eventually, the outputs and results of the simulations will be represented using Matlab, known for its ease of use. 5.1 Algorithm The general algorithm implemented is the one shown in the flowchart 5.1. Basically, one bacterium is deployed in a finite environment like the one defined in Section 4.1, in a form of a two-dimensional grid, the size of which depends on one of the input arguments of the simulator. The presence of bacteria in the environment is stored in the matrix map, which will show 1 if there is a bacterium in a certain point in space. In the first place, all the settings are initialized, including temporal and spatial resolutions, diverse bacterium parameters and settings regarding the result saving. After that, the main loop of the program covers all the simulation time. In each time step, the concentration map is refreshed with the new concentration values. This is done following the diffusion algorithm, the flowchart of which can be seen in Figure 5.2a. It is the computational application of the finite differences method for Fick’s law, in two Automata Modeling of Quorum Sensing for Nanocommunication Networks 61 Figure 5.1: Flowchart of the general algorithm. dimensions. Remember the general equation: φ(x, t + ∆t)−φ(x, t) ∆t=D n X i=0 φ(x−∆xi, t)−2φ(x, t) + φ(x+ ∆xi, t) (∆xi)2(5.1.1) The term of our interest, φ(x, t + ∆t) or the concentration in the two-dimensional point x= [x, y] in the next time step, can be isolated. Hence, φ(x, t + ∆t) = φ(x, t) + D 1 X i=0 φ(x−∆xi, t)−2φ(x, t) + φ(x+ ∆xi, t) (∆xi)2∆t(5.1.2) Or also expressed as: φ(x, y, t + ∆t) = φ(x, y, t) + D[∂2φ(x, y, t) ∂2x+∂2φ(x, y, t) ∂2y]∆t(5.1.3) as it appears in the flowchart 5.2a. In light of the equation used, it is clear that the parameter used in each point in space is the concentration of particles, not the count of them. This is stored in the matrix con. The use of Fick’s laws reduces enormously the complexity of the system, because otherwisely Automata Modeling of Quorum Sensing for Nanocommunication Networks 62 we would deal with every individual autoinducer, resulting in interactions between millions and millions of them. The simulation would be unfeasible in terms of processing time, as soon as the numbers grow. Figure 5.2: Flowcharts for the environment (a) and bacteria (b) algorithms. Once the concentration for all the points in space is updated, the program enters a secondary loop that covers each and every bacteria, the positions and states of which are stored in two lists named pos and state, respectively. The bacterial algorithm (see Figure 5.2b) is entered at each iteration. This subroutine checks if it is time for the cell to sense, to emit autoinducers, or simply to change state, always following the rules of the model presented in Section 3.4. It also checks if it is time for the cell to generate a copy of itself. Note that the times in which the bacterium has to emit and reproduce are randomized, Automata Modeling of Quorum Sensing for Nanocommunication Networks 63 and thus different for each member of the colony. However, the rates of emission and reproduction will be constant, whereas their value will the same for all the bacteria. 5.1.1 Assumptions In order to be able to simulate and extract some results, without having to resolve that are not of our concern, some assumptions have been made. •Null motility: flagellated bacteria are known to move in search for nutrients, but for the time being the species of bacteria considered in the simulations do not have flagella. For that reason, and in spite of the possible flow created by fluids in the environment, or the interaction or collisions of bacteria with particles in their close environment, we consider that bacteria do not move. •Sensing: in this simulation, an uniformly distributed amount of chemosensors is placed in the surface of the bacteria. Thus, autoinducers coming from any direction will be properly sensed. •Emission: there are no computational models of particle emission so far. In the simulations, a raise in the internal concentration of autoinducers and the posterior diffusion is considered as the emission process. Actually, this is similar to the dumping process described in [13]. •Reproductive rates: bacterial grow and divide has been widely studied. It is known that bacteria have three different reproductive phases: lag, logarithmic and stationary. The logarithmic phase occurs when bacteria are acclimated to the habitat, and while in it, they multiply themselves exponentially. This stage is the one introduced in the simulation, and therefore the population is doubled at a constant rate. The reproduction time or rate depends on the species, but one can find in the literature that reproduction can occur up to once each 10 minutes [18]. 15-20 minutes is widely published as a typical rate, and for Vibrio fischeri as an example of Quorum Sensing bacterium is approximately 40 minutes (calculation made from data of [55]). Due to computational restrains, the time between reproductions used will be much lower, but still effective as long as it is still much higher than the time between emissions. Automata Modeling of Quorum Sensing for Nanocommunication Networks 64 •Identicalness: all bacteria will be identical in terms of model and parameters. A mutation rate is present when bacteria replicate their DNA for reproduction, and this could change the behavior of some individuals within the colony. We will assume that the mutation rate is negligible. •Nutrients and living time: it is known that bacteria can be alive for long periods of time if they have enough nutrients to survive. We will assume that the environment presents enough nutrients to feed the colony during all the simulation time. •Clusters: bacteria are positioned in clustered way, and when they grow and divide, their descendants are also considered to be inside the cluster. Since motility is not contemplated, the cluster stays intact. Discussion about topology and position of the nodes in a random or different way is not the objective of these thesis. Simulations like in [32] deal with that. The values chosen for parameters involved in biological events of these simulations are taken from experiments or observations, if possible. Also, these values are adapted from the real three dimensional space to our space limited to two dimensions, when applicable. The threshold beyond which the bacteria activate (or activation threshold) is a varying factor depending on the species. Its value can also be considered of parameter of the simulation, but always within reasonable limits. For instance, in Vibrio fischeri or Escherichia coli, a concentration between 5 and 10 nM (nanomols per liter, 6.022 ·1014 molecules per dm3) autoinducers is enough to activate the target genes [14, 21]. The dumping or emission rate of autoinducers is not a clear parameter. Nevertheless, in [19] the emission rate of amino acids by two marine bacteria is analyzed. These particles are not much different than autoinducers, so we can consider these numbers as a good approximation: from 19 ·10−6to 25 ·10−6µmol per cell per hour. So, values in that range, or not far from those numbers can be assumed. The number of autoinducers released and the time between emissions will be selected accordingly. Regarding the size of the cells, bacteria span from as small as tenths of nanometers to almost one millimeter. But bacteria that apply Quorum Sensing are usually a few microns long. The value used in the simulations as the size of bacteria will be in that range. Automata Modeling of Quorum Sensing for Nanocommunication Networks 65 5.2 Results After running different simulations and adjusting different parameters, some results were obtained. Validation First and foremost, we must make sure that the model implemented shows the expected behavior. The simulation starts with a bacterium in the center of the simulated space. That bacterium and its descendants reproduce themselves again and again, so that the population doubles each time. Meanwhile, they keep sensing the environment and emitting autoinducers. There must be a certain point in which a great part of the colony will change of state. As explained earlier, the list of the states of the bacteria is constantly updated. In each iteration, a count of bacteria in post-Quorum states is performed. The results can be seen in Figure 5.3: the population grows in a steady basis until reaching a point in which almost all the bacteria activate simultaneously. The rest, activate shortly after, reaching a 100% of activation when the bacteria are clustered, not spread. Figure 5.3: Number of activated and total bacteria as a function of time. Nevertheless, for simulations in which a high population of bacteria is required to achieve Quorum Sensing, 100% of activation is not attainable. The bacteria located on the Automata Modeling of Quorum Sensing for Nanocommunication Networks 66 limits of the cluster do not sense enough concentration of autoinducers and consequently, do not activate. Those individuals keep reproducing until they are not on the limit anymore. Then, they sense a raise in the concentration of autoinducers and eventually they activate the post-Quorum behavior. But again, new bacteria are on the edge of the cluster and they will not activate. This way, the percentage of activation reaches a percentage of around the 95%. Once the model is validated, some more simulations can be done, changing the parameters. It seems clear that one of the key parameters in the overall process is the concentration threshold beyond which the bacteria activate, because that has influence upon the minimum population needed to change their status. These simulations are crucially important, because the first applications of Quorum Sensing require the deployment of a given number of nanomachines (see Chapter 7). The election of a reasonable value for this threshold is the key for the proper activation of nanomachines that perform Quorum Sensing. Number of Activating Bacteria The hypothesis is the following: The lower is the activation threshold, the fewer bacteria are needed to reach the critical level of concentration of autoinducers and to activate the colony. This should be true, knowing that the message is the aggregation of the autoinducers coming from all the bacteria, as seen in Section 4.4. Hence, the more bacteria are emitting, the higher will be the total concentration, reaching the activation threshold at some point. Figure 5.4 shows that the hypothesis is true. Moreover, the number of activating bacteria is quadratically dependant with the activation threshold used. The blue plot represents the number of quorated bacteria as a function of the activation threshold, and the green plot is the quadratic approximation, which fits the original plot almost without error. Hence, under all these assumptions, the function that expresses the number of bacteria that are required to achieve quorum by at least a 95% of the population, depending on the concentration threshold (T3, in the automaton presented in Section 3.4), can be approximated by a second order polynomial: Automata Modeling of Quorum Sensing for Nanocommunication Networks 67 Figure 5.4: Number of activating bacteria as a function of the threshold. N(T3)=1.81 ·1010 T2 3+ 2.61 ·106T3+ 22.43 (5.2.1) where T3is expressed in mol m2. Delay The fact that the activation threshold affects the number of bacteria activating in the end, has a direct consequence. The total time elapsed between the start of the process and the activation of the colony will obviously depend on the number of reproductions needed to reach the critical population. Nevertheless, we will define the delay as the time between the moment in which the first bacterium reaches the post-Quorum states, and the moment of global activation of the colony. As can be seen in Table 5.1, the total time elapsed in the process strongly depends on the number of generations of bacteria involved. Actually, it is shown that the time elapsed grows linearly with the population needed to reach quorum. In this specific case, the time between bacterial reproductions has a value of 50 time units. On the other hand, the value for the delay has a more random behavior, and does not depend on the number of reproductions needed to reach the population needed to activate the colony. Automata Modeling of Quorum Sensing for Nanocommunication Networks 68 the actuators should proceed (in case the nanomachine has to activate its post-Quorum behavior). It is important to note that using this architecture, the combination of Quorum Sensing systems can also be achieved. In this situation, the nanomachine would count on two different types of chemoreceptors and secretors, and the processing and control units would be adapted to each specific case. Another option would be to have two (or more) completely independent architectures in the same nanomachine, and integrate the decisions of their control units to govern the actuators. Nevertheless, this second option is not valid due to complexity and size constraints. 6.2 Applications Previously, in Section 1.5, several examples of fields that would benefit from communication between nanomachines were presented. Quorum Sensing, can be considered a form of molecular communication. The study of it and its antagonist, Quorum Quenching, open new possibilities in different fields for its application. Being a form of molecular communication, cases where the environment is favorable for the propagation of nanometric particles, are the best options (e.g. intra-body applications). In nature, bacteria use Quorum Sensing for different purposes, as stated in Section 2.4. Quorum Sensing enables bacteria to be aware of its own population, and to perform a postQuorum action simultaneously in all the colony. This fact make us think that this process can be used as a synchronization or coordination technique. For instance, Quorum Sensing could be used for the synchronization of bacterial clocks, or also called cellular oscillators, to generate a global rhythm [11, 22]. Other examples are numbered in Section 6.3. Quorum Sensing has been also observed in natural interspecies communications, in cases where bacteria needs to be aware of the population of other species. Also, it has been shown that combined systems have more than one Quorum Sensing process running in parallel, so the bacterium is able to be aware of its own and other species population. In this case, detection of cancer cells and proper actuation of a group of nanomachines could be Automata Modeling of Quorum Sensing for Nanocommunication Networks 75 implemented with this idea. Actually, cancer detection has always been a hot topic when talking about biomedical applications of nanomachines and nanonetworks. More insight about a way to implement this feature can be found in Section 6.4. The use of the combined systems just mentioned is an option that enables the implementation of Quorum Quenching, otherly called “Quorum Sensing inhibition”. As said before, Quorum Quenching or the deployment of anti-Quorum Sensing molecules is also a concept which aroused the interest of the scientific community, causing the apparition of many potential applications. Medical applications range from new ways to create antibiotics which prevent bacteria to activate aggressive behavior, to avoiding infections caused by bacterial biofilms formed in plastic catheters. The idea of preventing the formation of biofilms applies also to dental care or industrial applications: places in which certain biofilms are not welcome. Some of these can be found in Table 6.1: Representative Entities Effect on Quorum Sensing Evidence of Benefit Azithromycin Reduction in LasI, Rh1I, autoinducers, and virulence in P. aeruginosa Increased lung function in patients with panbronchiolitis and CF RIP, RAP vaccine Inhibition of the action of RNAIIIactivation protein in staphylococci Reduced virulence in various S. aureus animal models; decreased biofilm production on catheters by S. aureus and S. epidermis C30, C56 Inhibition of LuxR-dependent gene expression in Gram-negatives Increased clearance of P. aeruginosa in a mouse model of pneumonia; reduced adherence to catheters Several compounds isolated from plants Degradation of HSL signal molecules Various agricultural/horticultural benefits N-(2-oxocyclohexyl)- 3-oxododecanamide Antagonism of HSL activity Decreased biofilm production by P. aeruginosa in vitro 3-oxo-C12 -HSL-prot. conjugate vaccine Reduced pulmonary TNF-alpha aggregation in pneumonia Protection from lethal P. aeruginosa lung infection in mice Table 6.1: Potential therapeutic options associated to Quorum Quenching (from [43]). Automata Modeling of Quorum Sensing for Nanocommunication Networks 76 The trend about creating new antibiotics stems from the concern that arose around the fact that current antibiotics try to kill bacteria, resulting in the apparition of mutant varieties resistant to those antibiotics. A way to combat this situation is to deploy a regulated killing system [71] that controls and stabilizes actively the population of bacteria, preventing their activation. Alternatively, Quorum Quenching would jam the communication between members of the colony, in order to prevent the bacteria to attack, or to attack when they are not enough in number to be effective. All in all, affecting intraspecies systems, disease-specific antibiotics can be created; whereas affecting interspecies Quorum Sensing systems, broad spectrum antibiotics will be conceived [62]. In the next sections, two special cases that can serve for multiple applications will be stated and explained, namely, “collective activity synchronization” and “collective actuation after localized sensing”. Both are based in Quorum Sensing, using the model introduced in Section 3.4, along with the nanomachine architecture presented in Section 6.1. 6.3 Collective Activity Synchronization Nanomachines programmed for “collective activity synchronization” make use of Quorum Sensing as a feature to coordinate the action of all the units present in the medium. A fixed number of these nanomachines will be deployed in a target environment, and this group will not grow since these nanodevices do not have self-reproductive capabilities. In a similar fashion as a colony of bacteria, the model used for each individual nanomachine is the same. The general architecture introduced in Section 6.1 will serve as structure. Several simple modifications have been done in the automaton model that serves as control unit, in order to adapt it to the applications and limitations of the nanomachine. In general terms, the behavior of these nanomachines, determined by the control unit, consists of the release of autoinducers depending on the concentration sensed. When this concentration surpasses a certain threshold, the processing unit alerts the control unit, which will make the actuators perform the programmed “activity”. Automata Modeling of Quorum Sensing for Nanocommunication Networks 77 Processing Unit In this general case, the processing unit is the part responsible of turning the sensing information into simple signals that the control unit is capable of understanding. Basically, this unit counts the number of autoinducers that the nanomachine has received. Following a certain rate, the count (which represents the intracellular concentration) is compared with different thresholds, each with a different function. To mark the pace, tiny devices called nanoclocks, also known as genetic or biological clocks, can be used [9, 35]. These configurations fulfill most of the properties needed for the building of nanomachines using the bio-hybrid approach. On the other hand, we believe that the implementation of counters and simple comparators in an appropriate scale will be feasible due to the advances in nanoelectronics. If electrical power is to be needed, some solutions using zinc oxide nanowires have been proposed [69]. Figure 6.2: Processing Unit of a “Collective Activity Synchronization” nanomachine. The outputs of the processing unit are the wait signal (w) and the transition signals (d). The wait signal serves to control the rate with which the nanomachine changes of state and emits autoinducers. On the other hand, there are as many transition signals as thresholds, since these transitions are the result of the comparison of the count of particles with the thresholds. These transition signals follow the rules stated in Section 3.4, regarding the Automata Modeling of Quorum Sensing for Nanocommunication Networks 78 inputs of the automaton, whereas some auxiliary signals (X) will serve as transition signals for the post-Quorum behavior determined by the application. Threshold Function T1Transition from basal to autocatalytic phase T2Return from autocatalytic to basal phase T3Activation of the post-Quorum behavior T4Deactivation of the post-Quorum behavior XPost-Quorum behavior specific Table 6.2: Thresholds and functions of the Processing Unit. Hence, several features of the nanomachine are modeled with a proper adjustment of these values. For instance, if we want the nanomachine not to deactivate the post-Quorum behavior once acquired, T4must be set to zero. And setting the values of T1and T2, the behavior of the colony in terms of number of bacteria activating in the end is inherently modified, as seen in the results of Section 5.2 (Figure 5.4). Control Unit As stated before, the control unit is based on the automaton model designed earlier in this work. But since the original design was for the Quorum Sensing bacteria, some modifications have to be introduced in order to adapt the design to the inherent constraints to which the nanomachines are subject. For instance, bacteria have ways to somehow differentiate between their own autoinducers and autoinducers secreted by other individuals. Although using a bio-hybrid approach for the arrangement of the nanomachines, how to implement this feature is not a clear fact. The reason for wanting this differentiation is because the premature sensing of the environment may lead to erroneous receiving of autoinducers, and thus to a erroneous activation of the nanomachine. Eventually, a degradation of the performance can be observed. The proposed implementation of a wait signal in the processing unit, and the loop in the sensing states of the control unit (see Figure 6.3) serve to fight this degradation. If a Automata Modeling of Quorum Sensing for Nanocommunication Networks 79 Figure 6.3: Control Unit of a “Collective Activity Synchronization” nanomachine. nanomachine waits enough time for its own autoinducers to diffuse away, the consequent sensing will only contain a tiny percentage of its own secretion. This time will be called “relaxation time”, and an explanation of its theoretical calculation can be found in Section 7.1. Once the basis is set, the customization of the control unit must be performed in order to implement the concrete application of the nanomachine. It is known that the general application is to synchronize the action of a swarm of nanomachines. Now, it is time to define which action is to be synchronized, represented by the post-Quorum states of the automaton. •For instance, let the work of Maria Gregori in [25] serve as an example. In that work, an automata model of flagellated bacteria was designed, so that bacteria would transport information between two fixed points in space using chemotaxis (Figure 6.4). In case we need to split the message in several parts, we want to introduce redundancy by sending replica, or a synchronized broadcast of a message is to be performed, we can include this model for the post-Quorum behavior. To do it, we define the behavior states as B={Stop, Programming, Run, Tumble }, like in Figure 6.4. This way, a given number of nanomachines would part towards their destination at the same time. Automata Modeling of Quorum Sensing for Nanocommunication Networks 80 In this case, checking if quorum is maintained is not a required feature, so SE3state (see Figure 6.3) can be obviated. Extra inputs X={x1, x2, x3}have to be defined in the processing unit accordingly with the sensing of attractants (see [25]), and outputs Y={y1, y2, y3, y4}should serve to govern the actuator depending on the situation. Figure 6.4: Post-Quorum behavior for collective message transmission (from [25]). •Another example would be the collective release of a drug. In a hypothetical scenario, a highly concentrated and localized dose of a drug is needed, and the supply achieved by a single nanomachine is not enough, and useless. In this case, the deployment of several nanomachines that will work collectively is needed: they will perform Quorum Sensing to be aware of other nanomachines’ presence, and then they will release the drug. The post-Quorum behavior can be simply modeled with a state (DRUG, see Figure 6.5), the output of which (y1) opens the vesicle that secretes and releases the drug. Here, it is important to maintain the minimum number of nanomachines, so the state SE3cannot be obviated. If the deactivation threshold is surpassed, an output ordering the closing of the vesicle must be sent (y2). Actuators It has been stated that the actuators to include in the nanomachine depend strongly on the application desired. In the two cases just presented, the actuators proposed are: Automata Modeling of Quorum Sensing for Nanocommunication Networks 81 Figure 6.5: Complete control unit for collective drug release. •Flagella: one of the most promising techniques that will enable motility in nanomachines is the use of flagella. They are is a tail-like projection that protrude from the cell body. The movement of these appendages is governed by a chain of proteins [45], and allows the cell to propel itself when rotating counter-clockwise. Knowing better these chains of chemical reactions, turning the outputs of the control unit into chemicals signals that will rule the movement of the flagella may be possible. •Vesicles: in the case of collective drug release, specific secretory vesicles full of the drug to be delivered are the actuators. It is a research challenge to discover how to make them retain the drug or make them release it as a function of the signals coming from the control unit. For instance, a predetermined chemical signal coming from the control unit could break the primary membrane that covers the vesicle, releasing the drug contained in its interior. 6.4 Collective Actuation after Localized Sensing The function of this second group of nanomachines can be perfectly defined by only reading its name. The objective is to achieve a global reaction of a swarm of nanomachines in view of a certain action or sensing. Automata Modeling of Quorum Sensing for Nanocommunication Networks 82 For instance, some cancer cells release an specific chemical at some point. In [43], the fact that immune systems are inhibited around cancer cells emitting those chemicals, is pointed out as the key for proliferation and activation of bioluminescence bacteria. Then, detection of micro-tumors is achieved. An alternative to that idea can be implemented with the nanomachines here presented. A swarm of these devices senses periodically the environment, looking for the specific chemicals that cancer cells release. When one or several of them sense the chemical, they turn on the Quorum Sensing process, thus activating the whole colony of nanomachines and achieving collective actuation. The actuation can be luminescence, in order to detect the tumors. In a future not so far away, also killer automata could be implemented in order to effectively kill these cancer cells. This way, elimination of tumors in a localized, minimally invasive, and extremely low scale can be achieved. In a general point of view, the conception of this application could be observed as a combined Quorum Sensing system. The presence of two different chemicals is needed in order to activate the colony. Nevertheless, the chemical coming from the cancer cells does not play any role in Quorum Sensing, only serves as a starting signal. Processing Unit The processing unit is, in essence, the same as presented for “collective activity synchronization” nanomachines. But note that, in this case, two different types of molecules are received, namely, autoinducers and a target chemical. Both of them are received through chemosensors, and sensing information of the two types of particles is sent to the processing unit (Figure 6.6). As mentioned earlier, the sensing of a certain amount of a target chemical in the environment serves as the start signal for Quorum Sensing. A new threshold (TS2), marks the concentration of the target chemical beyond which the Quorum Sensing process is turned on. In order to report to the control unit that this threshold has been surpassed, a signal dS is sent. This signal is also sent when a nanomachine senses a certain minimum concentration of autoinducers (determined by TS1). This covers the case of nanomachines that are away Automata Modeling of Quorum Sensing for Nanocommunication Networks 83 Figure 6.6: Processing Unit for “Collective Actuation after Localized Sensing”. from the chemical, but know that nanomachines in its close environment started Quorum Sensing, and so they have to do. After surpassing one or other threshold, Quorum Sensing takes place, activating the colony of nanomachines in the end. The activation implies that bioluminescence, killing or whatever actuation that has been modeled, will happen. The control unit, as it will be explained next, keeps controlling the levels of both concentrations of autoinducers and target chemical. In case that the level of the chemical drops below the limit defined by TF, a new output (dF) will be sent to the control unit to terminate the post-Quorum behavior. For instance, this serves to stop the killing mode of the nanomachine once the tumor has been eliminated, to avoid further complications. Threshold Output Boolean Expression Function TS1,TS2dS(R1> TS1)||(R2> TS2) Start signal for Quorum Sensing TFdFR2< TFEnding of post-Quorum actuation Table 6.3: New thresholds and functions of the Processing Unit. The election of these new thresholds has to be done carefully. For instance, a hysteretic election of the thresholds for the target chemical is recommended (TFTS2) in order to Automata Modeling of Quorum Sensing for Nanocommunication Networks 84 Figure 7.2: Flowchart of “Collective Activity Synchronization” nanomachine algorithms. inspired by those bacteria. The main difference lies in the fact that, in this case, sensing is determined by the relaxation time, rather than the emission rate predetermined for bacteria. The processing unit (see Figure 6.2) sends a wait signal to the control unit (see Figure 6.3) during several time steps, in order to implement the relaxation time between sensings. This signal serves to inhibit the sensing, since it does not allow the control unit to change its state. Once the relaxation time has passed, the wait signal will be deactivated and the next sensing will be performed. 7.2.2 Results Once the algorithms are implemented, the simulation is ready to take place. Like in the case of bacteria, several results can be extracted. First, we can validate the model, checking that the nanomachines behave as expected, and that the objectives are accomplished. Later, the delay of the whole process will be analyzed. Both results will be shown for the two cases presented: for nanomachines which travel towards a receiver through chemotaxis, and for nanomachines prepared for drug release. Automata Modeling of Quorum Sensing for Nanocommunication Networks 91 Validation The validation of the model has two parts. The first part is the same for the two cases; both chemotaxis and drug release nanomachines will perform Quorum Sensing and the validation of this behavior consists of seeing how nanomachines activate. In the second part of the validation, the post-Quorum behavior is checked, analyzing how the joint effort of all nanomachines affects both chemotaxis and drug release performance. To realize the validation of the pre-Quorum part, several simulations have been performed, with a different number of nanomachines each time. The nanomachines are deployed in the environment, forming a cluster. Then, the evolution of the states of the nanomachines is observed. Parameters like the rates of autoinducers’ emission or the autocatalytic and activation thresholds are chosen in a way that the minimum number of nanomachines needed to reach quorum is around 100. The results can be seen in Figure 7.3, in which the percentage of activated nanomachines is represented as a function of time. The evolution observed is the expected in two different cases: Figure 7.3: Percentage of nanomachines activating for different colony sizes. Automata Modeling of Quorum Sensing for Nanocommunication Networks 92 •Quorum Sensing does not work when the number of nanomachines deployed (N) is below 100: for N = 1 and N = 10 none of the nanomachines activate. For N = 25 and N = 50, there is a residual activation of nanomachines, but not surpassing the 25% at any time. Here lies the importance of the study made in the subsection “Number of Activating Bacteria” in Section 5.2: the parameters have to be chosen carefully to avoid problems in the activation of the group of nanomachines. •On the other hand, when the number of deployed nanomachines is 100 or more, the algorithm of Quorum Sensing ensures the activation of all the nanomachines in a short time. In this situation, the bigger is the number of nanomachines deployed, the sooner they activate. The reason is that while the activation threshold remains fixed, the concentration of autoinducers will increase faster due to the bigger number of nanomachines in the environment. Regarding the validation of the post-Quorum part, the behavior programmed for after the activation in each case is observed. Two applications have been developed: •In the chemotaxis case, the post-Quorum behavior is the activation of the run-tumble algorithm, in which the nanomachine uses its flagella to move towards a receiver. Hence, a given number of nanomachines start their journey towards the receiver at the same time, as it is shown in Figure 7.4. Figure 7.4: Multiple nanomachines performing chemotaxis simultaneously. Automata Modeling of Quorum Sensing for Nanocommunication Networks 93 In the example shown, four different bacteria activate after performing Quorum Sensing and start their erratic journey towards the same receiver. The distance of these four bacteria to the receiver is represented, and it is considered that they have reached their destination when the distance is lower to 50 micrometers (marked with a square). The simulation tools needed to determine the path the flagellated bacteria are presented [8] and have been used with the permission of its author, L. Cobo. The total time to destination varies from one to another bacterium. If we send a given number of bacteria to the same receiver, the delay will be lower with a higher probability for at least one of them. Therefore, the performance of this communication can be improved. •In the second case, nanomachines are programmed to perform drug release after Quorum Sensing. To validate the post-Quorum behavior, the concentration of the drug is calculated in a certain localized area. This calculation is shown in Figure 7.5, where the concentration of the drug is represented as a function of time. Figure 7.5: Drug concentration for different colony sizes. For N = 1, N = 10 and N = 25, a negligible amount of the drug is released, since the number of activated nanomachines is zero or close to zero. As seen in Figure 7.3, a quarter part of the nanomachines activate when N = 50. Due to that partial activation, the level of the drug in the environment is still low. Finally, when 100 or more are deployed, the drug concentration reaches high levels due to the total Automata Modeling of Quorum Sensing for Nanocommunication Networks 94 activation. Then, we can conclude that the behavior is the expected in this case, since we succeeded in releasing a high dose of a drug in a localized area by the activation of several nanomachines by means of Quorum Sensing. Delay The purpose of this subsection is to study the delay of the activation of nanomachines when deployed in an environment, forming a cluster. Is not the same study as the one made in Section 5.2, since these nanomachines do not have reproduction capabilities. In this scenario, the total number of nanomachines is deployed at once, instead of releasing only one bacterium and letting it grow and divide until reaching the minimum population to activate. Here, we define “time elapsed” as the time that passes between the start of the simulation and the moment in which the percentage of activation arrives to 100%. Whereas, the “delay” is defined as the time elapsed between the moment the first nanomachine activates and the moment in which the swarm reaches complete activation. In Figure 7.6, some delay results as functions of the number of nanomachines deployed are depicted. The concepts of “time elapsed” and “delay” only make sense when the group of nanomachines reach the state of total activation, meaning that all the nanomachines activate in the end. For small nanomachine populations, total activation is never achieved, which is equivalent to saying that we will need an infinite time to reach quorum. That is why there is a vertical asymptote in a value lower to the minimum number of nanomachines needed to activate the colony. Another interesting result is that the delay of the process decreases if the number of nanomachines deployed is increased. The reason behind this behavior was pointed out in the “validation” section: while the activation threshold remains fixed, the concentration of autoinducers will increase faster due to the bigger number of nanomachines in the environment, thus surpassing the activation threshold in less time. Nevertheless, there is a point after which the delay does not decrease anymore. This is due to the relaxation time, presented and justified in Section 7.1, defined as the time needed between two consecutive sensings to ensure the correct performance of Quorum Automata Modeling of Quorum Sensing for Nanocommunication Networks 95 Figure 7.6: Delay of the activation process for “Collective Activity Synchronization” nanomachines. Sensing. Taking into account that the relaxation time in the simulations is 2 seconds (see Figure 7.6), it seems that: •The lower limit for the total time elapsed is the double of the relaxation time, and it is the optimum. •In the case of the delay, the lower limit is the relaxation time, and it is also the optimum. On one hand, shortening the activation delay would mean a better synchronization between all the nanomachines, and a faster actuation. On the other hand, there is the cost of manufacturing and deploying these nanomachines. Then, a compromise between these two factors must be reached, always taking into account the connection shown between them in Figure 7.6. Automata Modeling of Quorum Sensing for Nanocommunication Networks 96 7.3 Collective Actuation after Localized Sensing As explained in Section 6.4, nanomachines programmed for “collective activation after localized sensing” make use of Quorum Sensing to activate the group of nanomachines shortly after one or several of them sense a certain concentration of a chemical. The target chemical to sense does not have to be audoinducers, and marks the application of this configuration. For instance, if the target chemical is related to emissions of cancer cells, the group can be programmed to release a drug, thus resulting in a cancer killing system. In this section, the algorithm used in the simulations, and the result of those simulations will be presented. 7.3.1 Algorithm The general algorithm for simulations involving “collective activation after localized sensing” nanomachines is the same as in the case of “collective activity synchronization” nanomachines, and it is presented in Section 7.2.1. Concretely, the flowchart for this general algorithm is shown in Figure 7.1. Basically, the nanomachines are deployed in the target environment and, at each time step, both diffusion and nanomachine routines are executed. As expected, the algorithm or routine of the “collective activation after localized sensing” nanomachines is slightly different from the algorithm of the other type of nanomachine presented. In this case, the starting state is a dormant or inactive state in which the nanomachine does not emit autoinducers, but senses the environment looking for the target chemical, or autoinducers which indicate that the Quorum Sensing process has been started. Once the nanomachine exits this dormant state, the behavior will be the same as in the Quorum Sensing bacteria or as in the “collective activity synchronization” nanomachines. This is, they sense the environment, check the next state and emit autoinducers in order to reach quorum. Once Quorum Sensing is achieved, all the nanomachines activate their post-Quorum behavior, which can be, as explained in Section 6.4, drug release in order to kill a certain type cells. The flowchart for this nanomachine algorithm is shown in Figure 7.7. Automata Modeling of Quorum Sensing for Nanocommunication Networks 97 Figure 7.7: Flowchart of the “Collective Actuation after Localized Sensing” algorithm. 7.3.2 Results The simulations done served to validate the algorithm used and to verify that the control unit of the nanomachines works as expected. The objective of this type of nanomachines was to sense a certain chemical and react to that sensing. Concretely, the group of nanomachines has to stay dormant, without emitting autoinducers, until one or several nanomachines sense the target chemical. That will trigger, in the end, the activation of all the nanomachines by means of Quorum Sensing. To see the behavior of the group, a given number of nanomachines (N = 1000) is deployed in the environment. At a certain time (t = 5s) the chemical to be sensed is “spilled” in the same environment. The size, position and density of the “stain” will vary from simulation to simulation to extract the desired results. Validation Various simulations have been run to see the behavior of the “collective activation after localized sensing” nanomachines. Basically, the area where the chemical is located will be Automata Modeling of Quorum Sensing for Nanocommunication Networks 98 partially or completely covered by nanomachines, but the concentration of that chemical in the stained area will change. If the concentration of the chemical is above a certain predefined threshold, all the nanomachines should activate in the end, meaning that all of them will reach the post-Quorum state. On the other hand, if the concentration of the chemical is below the aforementioned threshold, the nanomachines should stay in the dormant state. The results shown in Figure 7.8 confirm that the nanomachines behave as expected. Taking into account that the chemical is spilt at t = 5s, two cases are represented: •Case A: the concentration of the target chemical does not surpass the minimum level needed to alert the nanomachines. Hence, all of them stay in the dormant state and obviously the percentage of active nanomachines remains at 0. Figure 7.8: Evolution of the state of “Collective Actuation after Localized Sensing” nanomachines. •Case B: the concentration of the target chemical is above the minimum level needed to alert the nanomachines. Starting at t = 5s, the nanomachines which sense that Automata Modeling of Quorum Sensing for Nanocommunication Networks 99 situation start emitting autoinducers. These autoinducers, in turn, diffuse in the medium, alerting the surrounding nanomachines and triggering the release of more autoinducers. At some point, all the nanomachines leave their dormant state, thus starting Quorum Sensing. Later, they start activating their post-Quorum behavior until reaching 100% of activation. All in all, the expected behavior of responding to a localized sensing, is confirmed. The expected behavior has been observed even in the most extreme case: when only one nanomachine situated at the edge of the cluster senses the target chemical. Delay The delay in this case will be defined as the lapse of time between the first time that any of the nanomachines senses the target chemical, and the global activation of the colony. Theoretically, this delay depends on how fast the nanomachines exit the dormant state. This is, if nanomachines cover all the area where the chemical is situated, many of them will start emitting autoinducers at the same time. Also, the bigger is the contaminated area, the more nanomachines will exit the dormant state, due to the sensing of the target chemical. Figure 7.9: Activation delay of “Collective Actuation after Localized Sensing” nanomachines. Automata Modeling of Quorum Sensing for Nanocommunication Networks 100 Appendix A Calculation of the Relaxation Time In Section 7.1, the need for defining a relaxation time is discussed. Here, the full development of the initial expression, and the explanation of the approximations used, can be found. It is been said that the starting point is the Roberts Equation: U(r, t) = 2Q (4πDt)3 2 e−r2 4Dt (A.0.1) This expression represents the density of particles at a distance r of a source of an instantaneous emission (of Q mols), at a given time t since the emission. Assuming that our bacteria/nanomachine is spherical, the same as its sensing area is, we can calculate the amount of particles present in its space (of radius R), integrating: QR(t) = ZrZφZϕ U(r, t)r2sinφ drdθdφ (A.0.2) The calculus of this integral is as follows: QR(t) = ZrZφZϕ U(r, t)r2sinφ drdθdφ =ZR 0Zπ −πZπ 0 2Q (4πDt)3 2 e−r2 4Dt r2sinφdrdφdϕ = =2Q (4πDt)3 2ZR 0 r2e−r2 4Dt dr Zπ −π dϕ Zπ 0 sinφdφ =8Qπ (4πDt)3 2ZR 0 r2e−r2 4Dt dr (A.0.3) After this, we apply a change of coordinates, x=r √4Dt, resulting in: QR=8Qπ (4πDt)3 2ZR √4Dt 0 (4Dtx2)e−x2(√4Dtdx) = 8Qπ(4Dt)3 2 (4πDt)3 2ZR √4Dt 0 x2e−x2dx = 107 =8Q √πZR √4Dt 0 x2e−x2dx (A.0.4) Analytically, we know that: Zx2e−x2=1 4[√πerf(x)−2xe−x2] So, we obtain, after applying to A.0.4: QR=8Qπ (4πDt)3 2 1 4[√πerf(x)−2xe−x2] (A.0.5) It can be seen in Section A.0.5 that trying to isolate the parameter x, and consequently tis almost impossible. To help with this step, Taylor series of erf(x) and e−x2will be used: erf(x) = 2 √π(x−x3 3+x5 10 −. . .) e−x2= 1 −x2+x4 2! −. . . In both cases, if x1 some terms can be neglected: erf(x)≈2 √π(x−x3 3) e−x2≈1−x2 So, applying both approximations in the solution of the integral, we obtain: 1 4[√πerf(x)−2xe−x2]≈1 4[√π2 √π(x−x3 3)−2x(1 −x2)] = =1 4 4 3x3=x3 3 Finally, adding the last result to the expression A.0.5, and applying the Barrow’s Law: QR=8Q √πZR √4Dt 0 x2e−x2dx =8Q √π 1 4[√πerf(R √4Dt)−2R √4Dte−R2 4Dt ]≈ ≈8Q 3√π R3 (4Dt)3/2(A.0.6) Now, we define the attenuation desired as: p=Q QR. Then, we can isolate “t” in the equation A.0.6 as the minimum relaxation time needed so a bacteria will sense only one small part of its own emitted particles. tMIN ≈(8πp 3)2 3R2 4πD Automata Modeling of Quorum Sensing for Nanocommunication Networks 108 Error Evaluation Remember that the assumption made is that x1. Using the “t” calculated: x0=R √4Dt0=R q4D(8πp 3)2 3R2 4πD =√π 3 q8πp 3 The higher we choose “p”, the better the condition will be met, and the better approximation of “t” will be taken. In case p is low, “t” should be taken one or two orders of magnitude higher. Anyway, it is known that this expression is an approximation, so it would be advisable to use a value slightly higher than tMIN . p x01 4[√πerf(x0)−2x0e−x02]x03 3Error 2 0.6927 0.0837 0.1108 32.37% 10 0.4051 0.0201 0.0222 10.44% 50 0.2369 4.2849e-3 4.4311e-3 3.42% 100 0.1880 2.1691e-3 2.2216e-3 2.42% 1000 0.0873 2.2055e-4 2.2156e-4 0.45% Table A.1: Errors of the approximation for the calculation of tMIN , as a function of p. Automata Modeling of Quorum Sensing for Nanocommunication Networks 109 Bibliography [1] I. Akyildiz, F. Brunetti, and C. Blazquez, “Nanonetworks: A new communication paradigm,” Computer Networks, vol. 52, no. 12, pp. 2260–2279, 2008. [2] I. Akyildiz and J. M. Jornet, “Electromagnetic Wireless Nanosensor Networks,” Nano Communication Networks, vol. 1, no. 1, 2010. [3] M. Anissimov, “Robot Arm Places Atoms and Molecules With 100% Accuracy,” p. 12, 2009. [4] B. Bassler, “How bacteria talk to each other: regulation of gene expression by quorum sensing,” Current opinion in microbiology, vol. 2, no. 6, pp. 582–587, 1999. [5] ——, “Small talk: Cell-to-cell communication in bacteria,” Cell, vol. 109, pp. 421–424, 2002. [6] C. Chen, “Development of Nanotechnology for Biomedical Applications,” in Emerging Information Technology Conference. IEEE, 2005. [7] S. Chou, P. Krauss, and P. Renstrom, “Imprint Lithography with 25-Nanometer Resolution,” Science, vol. 272, no. 5258, pp. 85–87, 1996. [8] L. C. Cobo, “Bacteria-based Communication in Nanonetworks,” submitted for journal publication, 2010. [9] N. A. Cookson, L. S. Tsimring, and J. Hasty, “The pedestrian watchmaker: genetic clocks from engineered oscillators.” FEBS letters, vol. 583, no. 24, pp. 3931–7, Dec. 2009. 111 [10] S. Crosson and K. Moffat, “Photoexcited Structure of a Plant Photoreceptor Domain Reveals a Light-Driven Molecular Switch,” The plant cell, vol. 14, pp. 1067–1075, 2002. [11] T. Danino, O. Mondrag´on-Palomino, L. Tsimring, and J. Hasty, “A synchronized quorum of genetic clocks.” Nature, vol. 463, no. 7279, pp. 326–30, Jan. 2010. [12] Dictionary.com, “Dictionary.com Unabridged,” 2010. [Online]. Available: http://dictionary.reference.com/browse/quorum [13] J. D. Dockery and J. P. Keener, “A mathematical model for quorum sensing in Pseudomonas aeruginosa,” Bulletin of Mathematical Biology, vol. 63, no. 1, pp. 95–116, 2001. [14] K. M. Dolan and E. P. Greenberg, “Evidence that GroEL, not sigma 32, is involved in transcriptional regulation of the Vibrio fischeri luminescence genes in Escherichia coli.” Journal of bacteriology, vol. 174, no. 15, p. 5132, 1992. [15] Y. H. Dong, L. H. Wang, J. L. Xu, H. B. Zhang, X. F. Zhang, and L. H. Zhang, “Quenching quorum-sensing-dependent bacterial infection by an N-acyl homoserine lactonase.” Nature, vol. 411, no. 6839, pp. 813–7, Jun. 2001. [16] E. Drexler, C. Peterson, and G. Pergamit, “Unbounding the Future: The Nanotechnology Revolution,” 1991. [17] K. E. Drexler, Nanosystems: molecular machinery, manufacturing, and computation. New York: John Wiley & Sons, 1992. [18] R. G. Eagon, “Pseudomonas natriegens, a marine bacterium with a generation time of less than 10 minutes,” Journal of Bacteriology, vol. 83, no. 4, p. 736, 1962. [19] C. Ferrier-Pages, M. Karner, and F. Rassoulzadegan, “Release of dissolved amino acids by flagellates and ciliates grazing on bacteria,” Oceanologica Acta, vol. 21, no. 3, pp. 485–494, 1998. [20] R. Freitas, “Pharmacytes: An Ideal Vehicle for Targeted Drug Delivery,” Journal of Nanoscience and Nanotechnology, vol. 6, no. 9, pp. 2769–2775, 2006. Automata Modeling of Quorum Sensing for Nanocommunication Networks 112 [21] C. Fuqua, S. Winans, and P. Greenberg, “Quorum Sensing in Bacteria: the LuxR-LuxI Family of Cell Density-Responsive Transcriptional Regulatorst,” Journal of Bacteriology, vol. 176, no. 2, pp. 269–275, 1994. [22] J. Garcia-ojalvo, M. B. Elowitz, and S. H. Strogatz, “Modeling a synthetic multicellular clock: Repressilators coupled by quorum sensing,” Sciences-New York, vol. 101, no. 30, 2004. [23] H. Goldstein, “Nanotechnology: The Race to the Bottom,” 2005. [24] A. B. Goryachev, D. J. Toh, K. B. Wee, T. Lee, H. B. Zhang, and L. H. Zhang, “Transition to quorum sensing in an agrobacterium population: A stochastic model,” PLoS Computational Biology, vol. 1, no. 4, pp. 265–275, 2005. [25] M. Gregori, “A new nanonetwork architecture using flagellated bacteria and catalytic nanomotors,” Master Thesis, Georgia Tech / UPC, 2009. [26] M. Gregori and I. Akyildiz, “A new NaNoNetwork architecture using flagellated bacteria and catalytic nanomotors,” to appear in Journal of Selected Topics in Communications (JSAC), 2010. [27] H. Gu, J. Chao, S. Xiao, and N. Seeman, “Dynamic patterning programmed by DNA tiles captured on a DNA origami substrate,” Nature Nanotechnology, vol. 4, no. April, pp. 245–248, 2009. [28] J. Hales, S. Zheng, S. Barlow, S. Marder, and J. Perry, “Bisdioxaborine polymethines with large third-order nonlinearities for all-optical signal processing,” Journal of the American Chemical Society, vol. 128, no. 35, pp. 11 362–3, Sep. 2006. [29] J. Han, J. Fu, and R. B. Schoch, “Molecular sieving using nanofilters: Past, present and future,” Lab on a Chip, vol. 8, pp. 23–33, 2008. [30] L. Harris, L. Owens, and S. Smith, “A selective and differential medium for Vibrio harveyi.” Applied and environmental microbiology, vol. 62, no. 9, pp. 3548–50, Sep. 1996. Automata Modeling of Quorum Sensing for Nanocommunication Networks 113 [31] J. Henke and B. Bassler, “Bacterial social engagements,” Trends in Cell Biology, vol. 14, no. 11, pp. 648–656, 2004. [32] B. A. Hense, C. Kuttler, M. Rothballer, A. Hartmann, and J.-u. Kreft, “Does efficiency sensing unify diffusion and quorum sensing?” Nature, vol. 5, no. March, pp. 230–239, 2007. [33] J. Hopcroft, R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages and Computation, 2nd ed. Addison-Wesley, 2001. [34] J. M. Jornet and I. Akyildiz, “Graphene-based nano-antennas for electromagnetic nanocommunications in the terahertz band,” in Proc. of 4th European Conference on Antennas and Propagation, EUCAP, Ed., Barcelona, 2010. [35] M. Kojima, M. Ohno, M. Nakajima, M. Homma, K. Takiguchi, T. Kondo, and T. Fukuda, “Nano Size Biological Clock Capsulated by Lipid Layer,” Science, vol. 8, no. c, pp. 526–529, 2009. [36] N. Krasnogor, M. Gheorghe, G. Terrazas, S. Diggle, P. Williams, and M. Camara, “An appealing computational mechanism drawn from bacterial quorum sensing,” Bulletin of the EATCS, vol. 85, pp. 135–148, 2005. [37] B. Lazazzera, “The intracellular function of extracellular signaling peptides.” Peptides, vol. 22, no. 10, pp. 1519–27, Oct. 2001. [38] A. Lazdunski, I. Ventre, and J. Sturgis, “Regulatory circuits and communication in Gram-negative bacteria.” Nature reviews (Microbiology), vol. 2, no. 7, pp. 581–92, 2004. [39] W. Leal, “Pheromone Reception,” Topics In Current Chemistry, vol. 240, pp. 1–36, 2005. [40] H. Lee, E. Menard, N. Tassi, J. Rogers, and G. Blanchet, “Large area microcontact printing presses for plastic electronics,” Materials Research Society Symposium Procedures, vol. 846, pp. 731–736, 2005. Automata Modeling of Quorum Sensing for Nanocommunication Networks 114 [41] Q. Li and D. Rus, “Global Clock Synchronization in Sensor Networks,” IEEE Transactions on Computers, vol. 55, no. 2, pp. 214–226, 2006. [42] S. Liu, “Software Simulation of DNA-Based Killer Automaton: The Innovative Nanomedicine,” UCI Undergraduate Research Journal, vol. VIII, pp. 79–88, 2005. [43] C. A. Martin, A. D. Hoven, and A. M. Cook, “Therapeutic frontiers: preventing and treating infectious diseases by inhibiting bacterial quorum sensing.” European journal of clinical microbiology & infectious diseases : official publication of the European Society of Clinical Microbiology, vol. 27, no. 8, pp. 635–42, Aug. 2008. [44] M. Meyyappan, J. Li, and A. Cassell, “Nanotechnology: an overview and integration with MEMS,” in MEMS, no. January. Istanbul, Turkey: IEEE, 2006, pp. 30–32. [45] T. Minamino, K. Imada, and K. Namba, “Molecular motors of the bacterial flagella,” Current opinion in structural biology, vol. 18, no. 6, pp. 693–701, 2008. [46] K. C. Mok, N. S. Wingreen, and B. Bassler, “Vibrio harveyi quorum sensing: a coincidence detector for two autoinducers controls gene expression.” The EMBO journal, vol. 22, no. 4, pp. 870–81, Feb. 2003. [47] M. Moore, A. Enomoto, and ..., “A Design of a Molecular Communication System for Nanomachines Using Molecular Motors,” in Pervasive Computing and Communications Workshops. IEEE, 2006. [48] J. M¨uller, C. Kuttler, B. A. Hense, M. Rothballer, and A. Hartmann, “Cell-cell communication by quorum sensing and dimension-reduction,” Journal of Mathematical Biology, vol. 53, pp. 672–702, 2006. [49] T. Nakano, T. Suda, M. Moore, R. Egashira, A. Enomoto, and K. Arima, “Molecular communication for nanomachines using intercellular calcium signaling,” in Proceedings of the Fifth IEEE Conference on Nanotechnology. Nagoya, Japan: Citeseer, 2005, pp. 478–481. [50] L. Parcerisa and I. Akyildiz, “Molecular Communication Options for Long Range Nanonetworks,” Computer Networks, 2009. Automata Modeling of Quorum Sensing for Nanocommunication Networks 115 [51] J. Philibert, “One and a Half Century of Diffusion: Fick, Einstein, Before and Beyond,” Diffusion Fundamentals, vol. 4, no. 6, pp. 1–19, 2006. [52] M. Pierobon and I. Akyildiz, “A Physical End-to-End Model for Molecular Communication in Nanonetworks,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 28, no. 4, pp. 602–611, 2010. [53] Y. Y. Pinto, J. D. Le, N. C. Seeman, K. Musier-Forsyth, T. A. Taton, and R. A. Kiehl, “Sequence-encoded self-assembly of multiple-nanocomponent arrays by 2D DNA scaffolding,” Nano letters, vol. 5, no. 12, pp. 2399–402, Dec. 2005. [54] J. Reif and S. Sahu, Autonomous programmable nanorobotic devices using DNAzymes. Springerlink, 2008, no. DNA Computing, pp. 66–78. [55] E. G. Ruby and L. M. Asato, “Growth and flagellation of Vibrio fischeri during initiation of the sepiolid squid light organ symbiosis,” Archives of Microbiology, vol. 159, pp. 160–167, 1993. [56] E. G. Ruby and M. J. McFall-Ngai, “A Squid That Glows in the Night: Development of an Animal-Bacterial Mutualism,” Journal of Bacteriology, vol. 174, no. 15, pp. 4865– 4870, 1992. [57] K. Salaita, Y. Wang, and C. A. Mirkin, “Applications of dip-pen nanolithography,” Nature Nanotechnology, vol. 2, no. 3, pp. 145–155, 2007. [58] M. Schwarz, D. Romano, and M. Gheorghe, “Visualizing Bacteria Quorum Sensing,” in AISB 2008 Convention Communication, Interaction and Social Intelligence, vol. 1, 2008, p. 1. [59] J. She and J. Yeow, “Nanotechnology-enabled wireless sensor networks: From a device perspective,” IEEE Sensors Journal, vol. 6, no. 5, pp. 1331–1339, 2006. [60] R. Smith and B. Iglewski, “P. aeruginosa quorum-sensing systems and virulence,” Current Opinion in Microbiology, vol. 6, no. 1, pp. 56–60, 2003. Automata Modeling of Quorum Sensing for Nanocommunication Networks 116