Natural computing
Encyclopedia
Natural computing, also called Natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of novel problem-solving techniques; 2) those that are based on the use of computers to synthesize natural phenomena; and 3) those that employ natural materials (e.g., molecules) to compute. The main fields of research that compose these three branches are artificial neural networks, evolutionary algorithms, swarm intelligence
, artificial immune systems, fractal geometry, artificial life
, DNA computing
, and quantum computing, among others.
Computational paradigms studied by natural computing are abstracted from natural phenomena as diverse as self-replication
, the functioning of the brain
, Darwinian evolution, group behavior, the immune system
, the defining properties of life forms, cell membranes, and morphogenesis
.
Besides traditional electronic hardware
, these computational paradigms can be implemented on alternative physical media such as biomolecules (DNA, RNA), or trapped-ion quantum computing devices.
Dually, one can view processes occurring in nature as information processing. Such processes include self-assembly
,
developmental processes, gene regulation networks, protein-protein interaction
networks, biological transport (active transport
, passive transport
) networks, and gene assembly in unicellular organism
s. Efforts to
understand biological systems also include engineering of semi-synthetic organisms, and understanding the universe itself from the point of view of information processing. Indeed, the idea was even advanced that information is more fundamental than matter or energy.
The Zuse-Fredkin thesis, dating back to the 1960s, states that the entire universe is a huge cellular automaton
which continuously updates its rules.
Recently it has been suggested that the whole universe is a quantum computer
that computes its own behaviour.
membrane computing, and amorphous computing.
In fact, all major methods and algorithms are nature-inspired metaheuristic
algorithms including cellular automata, evolutionary
computation, swarm intelligence and others. The detailed review can be found in many books
A cellular automaton is a dynamical system
consisting of a two-dimensional grid of cells. Space and time are discrete and each of the cells can be in a finite number of states
. The cellular automaton updates the states of its cells
synchronously according to the transition rules given a priori
. The next state of a cell is computed by a transition rule and it depends only on its current state and the states of its neighbors.
Conway's game of life
is one of the best-known examples of cellular automata, shown to be computationally universal
. Cellular automata have been applied to modelling a variety of phenomena such as communication, growth, reproduction, competition, evolution and other physical and biological processes.
Neural computation is the field of research that emerged from the comparison between computing machines
and the human nervous system
.
This field aims both to understand how the brain
of living organisms works
(brain theory or computational neuroscience
), and to design efficient algorithms based on the principles of how the human brain processes information (Artificial Neural Networks, ANN ).
An artificial neural network
is a network of artificial neurons.
An artificial neuron A is equipped with a function
, receives n real-valued
inputs
with respective weights
, and it outputs 
. Some neurons are selected to be the output neurons, and the network function is the vectorial function that associates to the n input values, the outputs of the m selected output neurons.
Note that different choices of weights produce different network functions for the same inputs. Back-propagation is a supervised learning method
by which the weights of the connections in the network are repeatedly adjusted so as to minimize the difference between the vector of actual outputs and that of desired outputs. Learning algorithm
s based on backwards propagation of errors
can be used to find optimal weights for given topology of the network
and input-output pairs.
Evolutionary computation is a computational paradigm inspired by Darwinian evolution.
An artificial evolutionary system is a computational system based on the notion of simulated evolution. It comprises a constant- or variable-size population of individuals, a fitness criterion
, and genetically inspired operators that produce the next generation
from the current one.
The initial population is typically generated randomly or heuristically, and typical operators
are mutation
and recombination
. At each step, the individuals are evaluated according to the given fitness function (survival of the fittest
). The next generation is obtained from selected individuals (parents) by using genetically inspired operators. The choice of parents can be guided by a selection operator which reflects the biological principle of mate selection. This process of simulated evolution
eventually converges towards a nearly optimal population of individuals, from the point of view of the fitness function.
The study of evolutionary systems has historically evolved along three main branches:
Evolution strategies provide a solution to parameter optimization problems
for real-valued as well as discrete and mixed types of parameters.
Evolutionary programming
originally aimed at creating optimal "intelligent agents" modelled, e.g., as finite state machines.
Genetic algorithms applied the idea of evolutionary computation to the problem of finding a (nearly-)optimal solution to a given problem. Genetic algorithms initially consisted of an input population of individuals encoded as fixed-length bit strings, the genetic operators mutation (bit flips) and recombination (combination of a prefix of a parent with the suffix of the other), and a problem-dependent fitness function.
Genetic algorithms have been used to optimize computer programs, called genetic programming
, and today they are also applied to real-valued parameter optimization problems as well as to many types of combinatorial tasks.
, sometimes referred to as collective intelligence
, is defined as the problem solving behavior that emerges from the interaction of individual agents (e.g., bacteria
, ants, termites, bees, spiders, fish
, birds) which communicate with other agents by acting on their local environments.
Particle swarm optimization
applies this idea to the problem of finding an optimal solution to a given problem
by a search through a (multi-dimensional) solution space. The initial set-up is a swarm of particles, each representing a possible solution to the problem. Each particle has its own velocity
which depends on its previous velocity (the inertia component), the tendency towards the past personal best position (the nostalgia component), and its tendency towards a global neighborhood optimum or local neighborhood optimum (the social component). Particles thus move through a multidimensional space and eventually converge towards a point between the global best
and their personal best.
Particle swarm optimization algorithms have been applied to various optimization problems, and to unsupervised learning
, game learning, and scheduling
applications.
In the same vein, ant algorithms
model the foraging behaviour of ant colonies.
To find the best path between the nest and a source of food, ants rely on indirect communication by laying a pheromone
trail on the way back to the nest if they found food, respectively
following the concentration of pheromones if they are looking for food. Ant algorithms have been successfully applied to a variety of combinatorial optimization problems over discrete search spaces.
) are computational systems inspired by the natural immune systems of biological organisms.
Viewed as an information processing system, the natural immune system
of organisms performs many complex tasks in parallel and distributed computing
fashion.
These include distinguishing between self and nonself, neutralization
of nonself pathogens (viruses, bacteria, fungi, and parasites
), learning
, memory
, associative retrieval, self-regulation
, and fault-tolerance.
Artificial immune systems are abstractions of the natural immune system, emphasizing these computational aspects.
Their applications include computer virus detection
, anomaly detection
in a time series of data, fault diagnosis, pattern recognition
, machine learning, bioinformatics
, optimization, robotics
and control
.
investigates computing models abstracted from the compartmentalized structure of living cells effected by membranes
.
A generic membrane system (P-system) consists of cell-like compartments (regions) delimited by membranes, that are placed in a nested hierarchical structure. Each membrane-enveloped region contains objects, transformation rules which modify these objects, as well as transfer rules, which specify whether the objects will be transferred outside or stay inside the region.
Regions communicate with each other via the transfer of objects.
The computation by a membrane system starts with an initial configuration, where the number (multiplicity) of each object is set to some value for each region (multiset of objects
).
It proceeds by choosing, nondeterministically
and in a maximally parallel manner,
which rules are applied to which objects. The output of the computation is collected from an a priori determined output region.
Applications of membrane systems include modelling of biological processes (photosynthesis
, certain signaling pathways, quorum sensing
in bacteria, cell-mediated immunity
), as well as computer science applications such as computer graphics
, public-key cryptography
, approximation
and sorting algorithms, as well as analysis of various computationally hard problems.
(the development of well-defined shapes and functional structures) is achieved by the interactions between cells guided by the genetic program encoded in the organism's DNA.
Inspired by this idea, amorphous computing
aims at engineering well-defined shapes and patterns, or coherent computational behaviours, from the local interactions of a multitude of simple unreliable, irregularly placed, asynchronous, identically programmed computing elements (particles).
As a programming paradigm, the aim is to find new programming techniques
that would work well for amorphous computing environments. Amorphous computing also plays an important role as the basis for "cellular computing" (see the topics synthetic biology
and cellular computing, below).
(ALife) is a research field whose ultimate goal is to understand the essential properties of life organisms by building, within electronic computers or other artificial media, ab initio
systems that exhibit properties normally associated only with living organisms.
Early examples include Lindenmayer systems (L-systems), that have been used to model plant growth and development. An L-system is a parallel rewriting system that starts with an initial word, and applies its rewriting rules in parallel to all letters of the word.
Pioneering experiments in artificial life included the design of evolving "virtual block creatures" acting in simulated environments with realistic features such as kinetics
, dynamics
, gravity, collision
, and friction
.
These artificial creatures were selected for their abilities endowed to swim, or walk, or jump, and they competed for a common limited resource (controlling a cube). The simulation resulted in the evolution of creatures exhibiting surprising behaviour: some developed hands to grab the cube, others developed legs to move towards the cube. This computational approach was further combined with rapid manufacturing technology to actually build the physical robots that virtually evolved. This marked the emergence of the field of mechanical artificial life.
The field of synthetic biology explores a biological implementation of similar ideas.
Other research directions within the field of artificial life include artificial chemistry
as well as traditionally biological phenomena explored in artificial systems, ranging from computational processes such as co-evolutionary adaptation and development, to physical processes such as growth, self-replication
, and self-repair.
. In contrast, the two paradigms introduced here, molecular computing and quantum computing, employ radically different types of hardware.
) is a computational paradigm in which data is encoded as biomolecules such as DNA strands
, and molecular biology tools act on the data to perform various operations (e.g., arithmetic or logical operations).
The first experimental realization of special-purpose molecular computer was the 1994 breakthrough experiment by Leonard Adleman
who solved a
7-node instance of the Hamiltonian Path Problem
solely by manipulating DNA strands in test tubes.
DNA computations start from an initial input encoded as a DNA sequence (essentially a sequence over the four-letter alphabet {A, C, G, T}),
and proceed by a succession of bio-operations such as cut-and-paste (by restriction enzymes and ligases),
extraction of strands containing a certain subsequence (by using Watson-Crick complementarity), copy (by using polymerase chain reaction
that employs the polymerase enzyme), and read-out.
Recent experimental research succeeded in solving more complex instances of NP-complete
problems such as a 20-variable instance of 3SAT
, and wet DNA implementations of finite state machines with potential applications to the design of smart drugs.
One of the most notable contributions of research in this field is to the understanding of self-assembly
.
Self-assembly is the bottom-up
process by which objects autonomously come together to form complex structures. Instances in nature abound, and include atoms binding by chemical bonds to form molecules, and molecules forming crystals or macromolecules. Examples of self-assembly research topics include self-assembled DNA nanostructures such as Sierpinski triangle
s or arbitrary nanoshapes obtained using the DNA origami
technique, and DNA nanomachines such as DNA-based circuits (binary counter, bit-wise cumulative XOR), ribozymes for logic operations, molecular switches (DNA tweezers), and autonomous molecular motors (DNA walkers).
Theoretical research in molecular computing has yielded several novel models of DNA computing (e.g. splicing systems introduced by Tom Head already in 1987) and their computational power has been investigated. Various subsets of bio-operations are now known to be able to achieve the computational power of Turing machines.
A quantum computer processes data stored as quantum bits (qubits), and uses quantum mechanical phenomena such as superposition
and entanglement
to perform computations.
A qubit can hold a "0", a "1", or a quantum superposition of these.
A quantum computer operates on qubits with quantum logic gates
.
Through Shor's polynomial algorithm for factoring integers, and Grover's algorithm
for quantum database search that has a quadratic time advantage, quantum computers were shown to potentially possess a significant benefit relative to electronic computers.
Quantum cryptography
is not based on the complexity of the computation, but on the special properties of quantum information
, such as the fact that quantum information cannot be measured reliably and any attempt at measuring it results in an unavoidable and irreversible disturbance.
A successful open air experiment in quantum cryptography was reported in 2007, where data was transmitted securely over a distance of 144 km.
Quantum teleportation
is another promising application, in which a quantum state (not matter or energy!) is transferred to an arbitrary distant location. Implementations of practical quantum computers are based on various substrates such as ion-traps
,
superconductors, nuclear magnetic resonance
, etc.
As of 2006, the largest quantum computing experiment used liquid state nuclear magnetic resonance quantum information processors, and could operate on up to 12 qubits.
The two main directions of research in this area are systems biology and synthetic biology.
Computational systems biology (or simply systems biology) is an integrative and qualitative approach that investigates the complex communications and interactions taking place in biological systems.
Thus, in systems biology, the focus of the study is the interaction network
s themselves and the properties of biological systems that arise due to these networks, rather than the individual components of functional processes in an organism.
This type of research on organic components has focused strongly on four different interdependent interaction networks: gene-regulatory networks, biochemical networks, transport networks, and carbohydrate networks.
Gene regulatory networks comprise gene-gene interactions, as well as interactions between genes and other substances in the cell.
Gene
s are transcribed into messenger RNA
(mRNA), and then translated into protein
s according to the genetic code
.
Each gene is associated with other DNA segments (promoters, enhancer
s, or silencer
s) that act as binding site
s for activator
s or repressor
s for gene transcription.
Genes interact with each other either through their gene products (mRNA, proteins) which can regulate gene transcription, or through small RNA species that can directly regulate genes.
These gene-gene interactions, together with genes' interactions with other substances in the cell, form the most basic interaction
network: the gene regulatory network
s. They perform information processing tasks within the cell, including the assembly and maintenance of other networks. Models of gene regulatory networks include random and probabilistic Boolean network
s, asynchronous automata, and network motif
s.
Another viewpoint is that the entire genomic regulatory system is a computational system, a genomic computer. This interpretation allows one to compare human-made electronic computation with computation as it occurs in nature.
In addition, unlike a conventional computer, robustness in a genomic computer is achieved by various feedback mechanisms by which poorly functional processes are rapidly degraded, poorly functional cells are killed by apoptosis
, and poorly functional organisms are out-competed by more fit species.
Biochemical networks refer to the interactions between proteins, and they perform various mechanical and metabolic tasks inside a cell. Two or more proteins may bind to each other via binding of their interactions sites, and form a dynamic protein complex (complexation). These protein complexes may act as catalysts for other chemical reactions, or may chemically modify each other.
Such modifications cause changes to available binding sites of proteins. There are tens of thousands of proteins in a cell, and they interact with each other. To describe such a massive scale interactions, Kohn maps were introduced
as a graphical notation to depict molecular interactions in succinct pictures. Other approaches to describing accurately and succinctly protein-protein interactions include the use of textual bio-calculus or pi-calculus
enriched with stochastic features.
Transport networks refer to the separation and transport of substances mediated by lipid membranes.
Some lipids can self-assemble into biological membranes. A lipid membrane consists of a lipid bilayer
in which proteins and other molecules are embedded, being able to travel along this layer. Through lipid bilayers, substances are transported between the inside and outside of membranes to interact with other molecules.
Formalisms depicting transport networks include membrane systems and brane calculi.
Synthetic biology aims at engineering synthetic biological components, with the ultimate goal of assembling whole biological systems from their constituent components. The history of synthetic biology can be traced back to the 1960s
, when Francois Jacob
and Jacques Monod
discovered the mathematical logic in gene regulation. Genetic engineering techniques, based on recombinant DNA
technology, are a precursor of today's synthetic biology which extends these techniques to entire systems of genes and gene products.
Along with the possibility of synthesizing longer and longer DNA strands, the prospect of creating synthetic genomes with the purpose of building entirely artificial synthetic organisms became a reality.
Indeed, rapid assembly of chemically synthesized short DNA strands made it possible to generate a 5386bp synthetic genome of a virus.
Alternatively, Smith et al. found about 100 genes that can be removed invidually from the genome of Mycoplasma Genitalium
.
This discovery paves the way to the assembly of a minimal but still viable artificial genome consisting of the essential genes only.
A third approach to engineering semi-synthetic cells is the construction of a single type of RNA-like molecule with the ability of self-replication. Such a molecule could be obtained by guiding the rapid evolution of an initial population of RNA-like molecules, by selection for the desired traits.
Another effort in this field is towards engineering multi-cellular systems by designing, e.g., cell-to-cell communication modules
used to coordinate living bacterial cell populations.
One particular study in this area is that of the computational nature of gene assembly in unicellular organisms called ciliate
s.
Ciliates store a copy of their DNA containing functional genes in the macronucleus
, and another "encrypted" copy in the micronucleus
. Conjugation of two ciliates consists of the exchange of their micronuclear genetic information, leading to the formation of two new micronuclei, followed by each ciliate re-assembling the information from its new micronucleus to construct a new functional macronucleus.
The latter process is called gene assembly, or gene re-arrangement. It involves re-ordering some fragments of DNA (permutation
s and possibly inversion) and deleting other fragments from the micronuclear copy.
From the computational point of view, the study of this gene assembly process led to many challenging research themes and results, such as the Turing universality of various models of this process.
From the biological point of view, a plausible hypothesis about the "bioware" that implements the gene-assembly process was proposed, based on template guided recombination.
Other approaches to cellular computing include developing an in vivo programmable and autonomous finite-state automaton with E. coli
, and designing and constructing in vivo cellular logic gates and genetic circuits that harness the cell's existing biochemical processes.
Many of the constituent research areas of natural computing have their own specialized journals and books series.
Journals and book series dedicated to the broad field of Natural Computing include the journals International Journal of Natural Computing Research (IGI Global),Natural Computing (Springer Verlag), Theoretical Computer Science, Series C: Theory of Natural Computing (Elsevier), the Natural Computing book series (Springer Verlag), and the upcoming Handbook of Natural Computing (G.Rozenberg, T.Back, J.Kok, Editors, Springer Verlag).
Swarm intelligence
Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
, artificial immune systems, fractal geometry, artificial life
Artificial life
Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
, DNA computing
DNA computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
, and quantum computing, among others.
Computational paradigms studied by natural computing are abstracted from natural phenomena as diverse as self-replication
Self-replication
Self-replication is any behavior of a dynamical system that yields construction of an identical copy of that dynamical system. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction...
, the functioning of the brain
Brain
The brain is the center of the nervous system in all vertebrate and most invertebrate animals—only a few primitive invertebrates such as sponges, jellyfish, sea squirts and starfishes do not have one. It is located in the head, usually close to primary sensory apparatus such as vision, hearing,...
, Darwinian evolution, group behavior, the immune system
Immune system
An immune system is a system of biological structures and processes within an organism that protects against disease by identifying and killing pathogens and tumor cells. It detects a wide variety of agents, from viruses to parasitic worms, and needs to distinguish them from the organism's own...
, the defining properties of life forms, cell membranes, and morphogenesis
Morphogenesis
Morphogenesis , is the biological process that causes an organism to develop its shape...
.
Besides traditional electronic hardware
Electronic hardware
Electronic hardware refers to interconnected electronic components which perform analog and/or logic operations on received and locally stored information to produce as output and/or store resulting new information and/or to provide control for output actuator mechanisms.Electronic hardware can...
, these computational paradigms can be implemented on alternative physical media such as biomolecules (DNA, RNA), or trapped-ion quantum computing devices.
Dually, one can view processes occurring in nature as information processing. Such processes include self-assembly
Self-assembly
Self-assembly is a term used to describe processes in which a disordered system of pre-existing components forms an organized structure or pattern as a consequence of specific, local interactions among the components themselves, without external direction...
,
developmental processes, gene regulation networks, protein-protein interaction
Protein-protein interaction
Protein–protein interactions occur when two or more proteins bind together, often to carry out their biological function. Many of the most important molecular processes in the cell such as DNA replication are carried out by large molecular machines that are built from a large number of protein...
networks, biological transport (active transport
Active transport
Active transport is the movement of a substance against its concentration gradient . In all cells, this is usually concerned with accumulating high concentrations of molecules that the cell needs, such as ions, glucose, and amino acids. If the process uses chemical energy, such as from adenosine...
, passive transport
Passive transport
Passive transport means moving biochemicals and other atomic or molecular substances across membranes. Unlike active transport, this process does not involve chemical energy, because, unlike in an active transport, the transport across membrane is always coupled with the growth of entropy of the...
) networks, and gene assembly in unicellular organism
Unicellular organism
A unicellular organism, also known as a single-celled organism is an organism that consists of only one cell, in contrast to a multicellular organism that consists of multiple cells. Historically simple single celled organisms have sometimes been referred to as monads Prokaryotes, most protists,...
s. Efforts to
understand biological systems also include engineering of semi-synthetic organisms, and understanding the universe itself from the point of view of information processing. Indeed, the idea was even advanced that information is more fundamental than matter or energy.
The Zuse-Fredkin thesis, dating back to the 1960s, states that the entire universe is a huge cellular automaton
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
which continuously updates its rules.
Recently it has been suggested that the whole universe is a quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
that computes its own behaviour.
Nature-inspired models of computation
The most established "classical" nature-inspired models of computation are cellular automata, neural computation, and evolutionary computation. More recent computational systems abstracted from natural processes include swarm intelligence, artificial immune systems,membrane computing, and amorphous computing.
In fact, all major methods and algorithms are nature-inspired metaheuristic
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
algorithms including cellular automata, evolutionary
computation, swarm intelligence and others. The detailed review can be found in many books
Cellular automata
- Further information: Cellular automatonCellular automatonA cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
A cellular automaton is a dynamical system
Dynamical system
A dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
consisting of a two-dimensional grid of cells. Space and time are discrete and each of the cells can be in a finite number of states
State (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
. The cellular automaton updates the states of its cells
synchronously according to the transition rules given a priori
A priori
A priori is Latin for "from the former" or "from before", and may refer to:* A priori knowledge, justification or arguments. See a priori and a posteriori.* A priori , a type of constructed language...
. The next state of a cell is computed by a transition rule and it depends only on its current state and the states of its neighbors.
Conway's game of life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
is one of the best-known examples of cellular automata, shown to be computationally universal
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
. Cellular automata have been applied to modelling a variety of phenomena such as communication, growth, reproduction, competition, evolution and other physical and biological processes.
Neural computation
- Further information: Neural computationNeural ComputationNeural Computation is a peer-reviewed academic journal covering aspects of neural computation. Articles highlight problems and techniques in modeling the brain, and in the design and construction of neurally-inspired information processing systems. Neural Computation was founded in 1989 and is...
Neural computation is the field of research that emerged from the comparison between computing machines
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
and the human nervous system
Nervous system
The nervous system is an organ system containing a network of specialized cells called neurons that coordinate the actions of an animal and transmit signals between different parts of its body. In most animals the nervous system consists of two parts, central and peripheral. The central nervous...
.
This field aims both to understand how the brain
Brain
The brain is the center of the nervous system in all vertebrate and most invertebrate animals—only a few primitive invertebrates such as sponges, jellyfish, sea squirts and starfishes do not have one. It is located in the head, usually close to primary sensory apparatus such as vision, hearing,...
of living organisms works
(brain theory or computational neuroscience
Computational neuroscience
Computational neuroscience is the study of brain function in terms of the information processing properties of the structures that make up the nervous system...
), and to design efficient algorithms based on the principles of how the human brain processes information (Artificial Neural Networks, ANN ).
An artificial neural network
Artificial neural network
An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
is a network of artificial neurons.
An artificial neuron A is equipped with a function
, receives n real-valuedReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
inputs
with respective weightsWeight function
A weight function is a mathematical device used when performing a sum, integral, or average in order to give some elements more "weight" or influence on the result than other elements in the same set. They occur frequently in statistics and analysis, and are closely related to the concept of a...
, and it outputs . Some neurons are selected to be the output neurons, and the network function is the vectorial function that associates to the n input values, the outputs of the m selected output neurons.Note that different choices of weights produce different network functions for the same inputs. Back-propagation is a supervised learning method
Supervised learning
Supervised learning is the machine learning task of inferring a function from supervised training data. The training data consist of a set of training examples. In supervised learning, each example is a pair consisting of an input object and a desired output value...
by which the weights of the connections in the network are repeatedly adjusted so as to minimize the difference between the vector of actual outputs and that of desired outputs. Learning algorithm
Machine learning
Machine learning, a branch of artificial intelligence, is a scientific discipline concerned with the design and development of algorithms that allow computers to evolve behaviors based on empirical data, such as from sensor data or databases...
s based on backwards propagation of errors
Backpropagation
Backpropagation is a common method of teaching artificial neural networks how to perform a given task. Arthur E. Bryson and Yu-Chi Ho described it as a multi-stage dynamic system optimization method in 1969 . It wasn't until 1974 and later, when applied in the context of neural networks and...
can be used to find optimal weights for given topology of the network
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
and input-output pairs.
Evolutionary computation
- Further information: Evolutionary computationEvolutionary computationIn computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
Evolutionary computation is a computational paradigm inspired by Darwinian evolution.
An artificial evolutionary system is a computational system based on the notion of simulated evolution. It comprises a constant- or variable-size population of individuals, a fitness criterion
Fitness (biology)
Fitness is a central idea in evolutionary theory. It can be defined either with respect to a genotype or to a phenotype in a given environment...
, and genetically inspired operators that produce the next generation
Generation
Generation , also known as procreation in biological sciences, is the act of producing offspring....
from the current one.
The initial population is typically generated randomly or heuristically, and typical operators
are mutation
Mutation
In molecular biology and genetics, mutations are changes in a genomic sequence: the DNA sequence of a cell's genome or the DNA or RNA sequence of a virus. They can be defined as sudden and spontaneous changes in the cell. Mutations are caused by radiation, viruses, transposons and mutagenic...
and recombination
Genetic recombination
Genetic recombination is a process by which a molecule of nucleic acid is broken and then joined to a different one. Recombination can occur between similar molecules of DNA, as in homologous recombination, or dissimilar molecules, as in non-homologous end joining. Recombination is a common method...
. At each step, the individuals are evaluated according to the given fitness function (survival of the fittest
Survival of the fittest
"Survival of the fittest" is a phrase originating in evolutionary theory, as an alternative description of Natural selection. The phrase is today commonly used in contexts that are incompatible with the original meaning as intended by its first two proponents: British polymath philosopher Herbert...
). The next generation is obtained from selected individuals (parents) by using genetically inspired operators. The choice of parents can be guided by a selection operator which reflects the biological principle of mate selection. This process of simulated evolution
Evolution
Evolution is any change across successive generations in the heritable characteristics of biological populations. Evolutionary processes give rise to diversity at every level of biological organisation, including species, individual organisms and molecules such as DNA and proteins.Life on Earth...
eventually converges towards a nearly optimal population of individuals, from the point of view of the fitness function.
The study of evolutionary systems has historically evolved along three main branches:
Evolution strategies provide a solution to parameter optimization problems
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
for real-valued as well as discrete and mixed types of parameters.
Evolutionary programming
Evolutionary programming
Evolutionary programming is one of the four major evolutionary algorithm paradigms. It is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve....
originally aimed at creating optimal "intelligent agents" modelled, e.g., as finite state machines.
Genetic algorithms applied the idea of evolutionary computation to the problem of finding a (nearly-)optimal solution to a given problem. Genetic algorithms initially consisted of an input population of individuals encoded as fixed-length bit strings, the genetic operators mutation (bit flips) and recombination (combination of a prefix of a parent with the suffix of the other), and a problem-dependent fitness function.
Genetic algorithms have been used to optimize computer programs, called genetic programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
, and today they are also applied to real-valued parameter optimization problems as well as to many types of combinatorial tasks.
Swarm intelligence
Swarm intelligenceSwarm intelligence
Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
, sometimes referred to as collective intelligence
Collective intelligence
Collective intelligence is a shared or group intelligence that emerges from the collaboration and competition of many individuals and appears in consensus decision making in bacteria, animals, humans and computer networks....
, is defined as the problem solving behavior that emerges from the interaction of individual agents (e.g., bacteria
Bacteria
Bacteria are a large domain of prokaryotic microorganisms. Typically a few micrometres in length, bacteria have a wide range of shapes, ranging from spheres to rods and spirals...
, ants, termites, bees, spiders, fish
Fish
Fish are a paraphyletic group of organisms that consist of all gill-bearing aquatic vertebrate animals that lack limbs with digits. Included in this definition are the living hagfish, lampreys, and cartilaginous and bony fish, as well as various extinct related groups...
, birds) which communicate with other agents by acting on their local environments.
Particle swarm optimization
Particle swarm optimization
In computer science, particle swarm optimization is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality...
applies this idea to the problem of finding an optimal solution to a given problem
by a search through a (multi-dimensional) solution space. The initial set-up is a swarm of particles, each representing a possible solution to the problem. Each particle has its own velocity
Velocity
In physics, velocity is speed in a given direction. Speed describes only how fast an object is moving, whereas velocity gives both the speed and direction of the object's motion. To have a constant velocity, an object must have a constant speed and motion in a constant direction. Constant ...
which depends on its previous velocity (the inertia component), the tendency towards the past personal best position (the nostalgia component), and its tendency towards a global neighborhood optimum or local neighborhood optimum (the social component). Particles thus move through a multidimensional space and eventually converge towards a point between the global best
Maxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
and their personal best.
Particle swarm optimization algorithms have been applied to various optimization problems, and to unsupervised learning
Unsupervised learning
In machine learning, unsupervised learning refers to the problem of trying to find hidden structure in unlabeled data. Since the examples given to the learner are unlabeled, there is no error or reward signal to evaluate a potential solution...
, game learning, and scheduling
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
applications.
In the same vein, ant algorithms
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
model the foraging behaviour of ant colonies.
To find the best path between the nest and a source of food, ants rely on indirect communication by laying a pheromone
Pheromone
A pheromone is a secreted or excreted chemical factor that triggers a social response in members of the same species. Pheromones are chemicals capable of acting outside the body of the secreting individual to impact the behavior of the receiving individual...
trail on the way back to the nest if they found food, respectively
following the concentration of pheromones if they are looking for food. Ant algorithms have been successfully applied to a variety of combinatorial optimization problems over discrete search spaces.
Artificial immune systems
Artificial immune systems (a.k.a. immunological computation or immunocomputingImmunocomputing
Immunocomputing explores the principles of information processing that proteins and immune networks utilize in order to solve specific complex problems while protected from viruses, noise, errors and intrusions.It intends to establish:...
) are computational systems inspired by the natural immune systems of biological organisms.
Viewed as an information processing system, the natural immune system
Immune system
An immune system is a system of biological structures and processes within an organism that protects against disease by identifying and killing pathogens and tumor cells. It detects a wide variety of agents, from viruses to parasitic worms, and needs to distinguish them from the organism's own...
of organisms performs many complex tasks in parallel and distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
fashion.
These include distinguishing between self and nonself, neutralization
Neutralization
In chemistry, neutralization, or neutralisation is a chemical reaction in which an acid and a base react to form a salt. Water is frequently, but not necessarily, produced as well. Neutralizations with Arrhenius acids and bases always produce water:Y and X represent a monovalent cation and anion...
of nonself pathogens (viruses, bacteria, fungi, and parasites
Parasitism
Parasitism is a type of symbiotic relationship between organisms of different species where one organism, the parasite, benefits at the expense of the other, the host. Traditionally parasite referred to organisms with lifestages that needed more than one host . These are now called macroparasites...
), learning
Learning
Learning is acquiring new or modifying existing knowledge, behaviors, skills, values, or preferences and may involve synthesizing different types of information. The ability to learn is possessed by humans, animals and some machines. Progress over time tends to follow learning curves.Human learning...
, memory
Memory
In psychology, memory is an organism's ability to store, retain, and recall information and experiences. Traditional studies of memory began in the fields of philosophy, including techniques of artificially enhancing memory....
, associative retrieval, self-regulation
Homeostasis
Homeostasis is the property of a system that regulates its internal environment and tends to maintain a stable, constant condition of properties like temperature or pH...
, and fault-tolerance.
Artificial immune systems are abstractions of the natural immune system, emphasizing these computational aspects.
Their applications include computer virus detection
Antivirus software
Antivirus or anti-virus software is used to prevent, detect, and remove malware, including but not limited to computer viruses, computer worm, trojan horses, spyware and adware...
, anomaly detection
Anomaly detection
Anomaly detection, also referred to as outlier detection refers to detecting patterns in a given data set that do not conform to an established normal behavior....
in a time series of data, fault diagnosis, pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
, machine learning, bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
, optimization, robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
and control
Control theory
Control theory is an interdisciplinary branch of engineering and mathematics that deals with the behavior of dynamical systems. The desired output of a system is called the reference...
.
Membrane computing
Membrane computingMembrane computing
Membrane computing is an area within computer science that seeks to discover new computational models from the study of biological cells, particular of the cellular membranes. It is a sub-task of creating a cellular model....
investigates computing models abstracted from the compartmentalized structure of living cells effected by membranes
Cell membrane
The cell membrane or plasma membrane is a biological membrane that separates the interior of all cells from the outside environment. The cell membrane is selectively permeable to ions and organic molecules and controls the movement of substances in and out of cells. It basically protects the cell...
.
A generic membrane system (P-system) consists of cell-like compartments (regions) delimited by membranes, that are placed in a nested hierarchical structure. Each membrane-enveloped region contains objects, transformation rules which modify these objects, as well as transfer rules, which specify whether the objects will be transferred outside or stay inside the region.
Regions communicate with each other via the transfer of objects.
The computation by a membrane system starts with an initial configuration, where the number (multiplicity) of each object is set to some value for each region (multiset of objects
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
).
It proceeds by choosing, nondeterministically
Nondeterminism
Nondeterminism may refer to:* Nondeterministic programming * Nondeterministic algorithm * Non-deterministic Turing machine * Indeterminacy in computation * Indeterminism...
and in a maximally parallel manner,
which rules are applied to which objects. The output of the computation is collected from an a priori determined output region.
Applications of membrane systems include modelling of biological processes (photosynthesis
Photosynthesis
Photosynthesis is a chemical process that converts carbon dioxide into organic compounds, especially sugars, using the energy from sunlight. Photosynthesis occurs in plants, algae, and many species of bacteria, but not in archaea. Photosynthetic organisms are called photoautotrophs, since they can...
, certain signaling pathways, quorum sensing
Quorum sensing
Quorum sensing is a system of stimulus and response correlated to population density. Many species of bacteria use quorum sensing to coordinate gene expression according to the density of their local population. In similar fashion, some social insects use quorum sensing to determine where to nest...
in bacteria, cell-mediated immunity
Immunity (medical)
Immunity is a biological term that describes a state of having sufficient biological defenses to avoid infection, disease, or other unwanted biological invasion. Immunity involves both specific and non-specific components. The non-specific components act either as barriers or as eliminators of wide...
), as well as computer science applications such as computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, public-key cryptography
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
, approximation
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
and sorting algorithms, as well as analysis of various computationally hard problems.
Amorphous computing
In biological organisms, morphogenesisMorphogenesis
Morphogenesis , is the biological process that causes an organism to develop its shape...
(the development of well-defined shapes and functional structures) is achieved by the interactions between cells guided by the genetic program encoded in the organism's DNA.
Inspired by this idea, amorphous computing
Amorphous computing
Amorphous computing refers to computational systems that use very large numbers of identical, parallel processors each having limited computational ability and local interactions...
aims at engineering well-defined shapes and patterns, or coherent computational behaviours, from the local interactions of a multitude of simple unreliable, irregularly placed, asynchronous, identically programmed computing elements (particles).
As a programming paradigm, the aim is to find new programming techniques
Abstraction (computer science)
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
that would work well for amorphous computing environments. Amorphous computing also plays an important role as the basis for "cellular computing" (see the topics synthetic biology
Synthetic biology
Synthetic biology is a new area of biological research that combines science and engineering. It encompasses a variety of different approaches, methodologies, and disciplines with a variety of definitions...
and cellular computing, below).
Artificial life
Artificial lifeArtificial life
Artificial life is a field of study and an associated art form which examine systems related to life, its processes, and its evolution through simulations using computer models, robotics, and biochemistry. The discipline was named by Christopher Langton, an American computer scientist, in 1986...
(ALife) is a research field whose ultimate goal is to understand the essential properties of life organisms by building, within electronic computers or other artificial media, ab initio
Ab initio
ab initio is a Latin term used in English, meaning from the beginning.ab initio may also refer to:* Ab Initio , a leading ETL Tool Software Company in the field of Data Warehousing.* ab initio quantum chemistry methods...
systems that exhibit properties normally associated only with living organisms.
Early examples include Lindenmayer systems (L-systems), that have been used to model plant growth and development. An L-system is a parallel rewriting system that starts with an initial word, and applies its rewriting rules in parallel to all letters of the word.
Pioneering experiments in artificial life included the design of evolving "virtual block creatures" acting in simulated environments with realistic features such as kinetics
Kinetics (physics)
In physics and engineering, kinetics is a term for the branch of classical mechanics that is concerned with the relationship between the motion of bodies and its causes, namely forces and torques...
, dynamics
Dynamics
Dynamics may refer to:-Physics and engineering:* Dynamics , the time evolution of physical processes** Aerodynamics, the study of gases in motion...
, gravity, collision
Collision
A collision is an isolated event which two or more moving bodies exert forces on each other for a relatively short time.Although the most common colloquial use of the word "collision" refers to accidents in which two or more objects collide, the scientific use of the word "collision" implies...
, and friction
Friction
Friction is the force resisting the relative motion of solid surfaces, fluid layers, and/or material elements sliding against each other. There are several types of friction:...
.
These artificial creatures were selected for their abilities endowed to swim, or walk, or jump, and they competed for a common limited resource (controlling a cube). The simulation resulted in the evolution of creatures exhibiting surprising behaviour: some developed hands to grab the cube, others developed legs to move towards the cube. This computational approach was further combined with rapid manufacturing technology to actually build the physical robots that virtually evolved. This marked the emergence of the field of mechanical artificial life.
The field of synthetic biology explores a biological implementation of similar ideas.
Other research directions within the field of artificial life include artificial chemistry
Artificial chemistry
An artificial chemistry is a computer model used to simulate various types of systems. Artificial chemistry is in some ways similar to a chemical reaction, hence the name...
as well as traditionally biological phenomena explored in artificial systems, ranging from computational processes such as co-evolutionary adaptation and development, to physical processes such as growth, self-replication
Self-replication
Self-replication is any behavior of a dynamical system that yields construction of an identical copy of that dynamical system. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction...
, and self-repair.
Nature-inspired novel hardware
All of the computational techniques mentioned above, while inspired by nature, have been implemented until now mostly on traditional electronic hardwareElectronic hardware
Electronic hardware refers to interconnected electronic components which perform analog and/or logic operations on received and locally stored information to produce as output and/or store resulting new information and/or to provide control for output actuator mechanisms.Electronic hardware can...
. In contrast, the two paradigms introduced here, molecular computing and quantum computing, employ radically different types of hardware.
Molecular computing
Molecular computing (a.k.a. biomolecular computing, biocomputing, biochemical computing, DNA computingDNA computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
) is a computational paradigm in which data is encoded as biomolecules such as DNA strands
DNA sequence
The sequence or primary structure of a nucleic acid is the composition of atoms that make up the nucleic acid and the chemical bonds that bond those atoms. Because nucleic acids, such as DNA and RNA, are unbranched polymers, this specification is equivalent to specifying the sequence of...
, and molecular biology tools act on the data to perform various operations (e.g., arithmetic or logical operations).
The first experimental realization of special-purpose molecular computer was the 1994 breakthrough experiment by Leonard Adleman
Leonard Adleman
Leonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...
who solved a
7-node instance of the Hamiltonian Path Problem
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
solely by manipulating DNA strands in test tubes.
DNA computations start from an initial input encoded as a DNA sequence (essentially a sequence over the four-letter alphabet {A, C, G, T}),
and proceed by a succession of bio-operations such as cut-and-paste (by restriction enzymes and ligases),
extraction of strands containing a certain subsequence (by using Watson-Crick complementarity), copy (by using polymerase chain reaction
Polymerase chain reaction
The polymerase chain reaction is a scientific technique in molecular biology to amplify a single or a few copies of a piece of DNA across several orders of magnitude, generating thousands to millions of copies of a particular DNA sequence....
that employs the polymerase enzyme), and read-out.
Recent experimental research succeeded in solving more complex instances of NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems such as a 20-variable instance of 3SAT
3sat
3sat is the name of a public, advertising-free, television network in Central Europe. The programming is in German and is broadcast primarily within Germany, Austria and Switzerland .3sat was established for cultural...
, and wet DNA implementations of finite state machines with potential applications to the design of smart drugs.
One of the most notable contributions of research in this field is to the understanding of self-assembly
Self-assembly
Self-assembly is a term used to describe processes in which a disordered system of pre-existing components forms an organized structure or pattern as a consequence of specific, local interactions among the components themselves, without external direction...
.
Self-assembly is the bottom-up
Bottom-up
Bottom-up may refer to:* In business development, a bottom-up approach means that the adviser takes the needs and wishes of the would-be entrepreneur as the starting point, rather than a market opportunity ....
process by which objects autonomously come together to form complex structures. Instances in nature abound, and include atoms binding by chemical bonds to form molecules, and molecules forming crystals or macromolecules. Examples of self-assembly research topics include self-assembled DNA nanostructures such as Sierpinski triangle
Sierpinski triangle
The Sierpinski triangle , also called the Sierpinski gasket or the Sierpinski Sieve, is a fractal and attractive fixed set named after the Polish mathematician Wacław Sierpiński who described it in 1915. However, similar patterns appear already in the 13th-century Cosmati mosaics in the cathedral...
s or arbitrary nanoshapes obtained using the DNA origami
DNA origami
DNA origami is the nanoscale folding of DNA to create arbitrary two and three dimensional shapes at the nanoscale. The specificity of the interactions between complementary base pairs make DNA a useful construction material through design of its base sequences...
technique, and DNA nanomachines such as DNA-based circuits (binary counter, bit-wise cumulative XOR), ribozymes for logic operations, molecular switches (DNA tweezers), and autonomous molecular motors (DNA walkers).
Theoretical research in molecular computing has yielded several novel models of DNA computing (e.g. splicing systems introduced by Tom Head already in 1987) and their computational power has been investigated. Various subsets of bio-operations are now known to be able to achieve the computational power of Turing machines.
Quantum computing
- Further information: Quantum computing
A quantum computer processes data stored as quantum bits (qubits), and uses quantum mechanical phenomena such as superposition
Quantum superposition
Quantum superposition is a fundamental principle of quantum mechanics. It holds that a physical system exists in all its particular, theoretically possible states simultaneously; but, when measured, it gives a result corresponding to only one of the possible configurations.Mathematically, it...
and entanglement
Quantum entanglement
Quantum entanglement occurs when electrons, molecules even as large as "buckyballs", photons, etc., interact physically and then become separated; the type of interaction is such that each resulting member of a pair is properly described by the same quantum mechanical description , which is...
to perform computations.
A qubit can hold a "0", a "1", or a quantum superposition of these.
A quantum computer operates on qubits with quantum logic gates
Quantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...
.
Through Shor's polynomial algorithm for factoring integers, and Grover's algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
for quantum database search that has a quadratic time advantage, quantum computers were shown to potentially possess a significant benefit relative to electronic computers.
Quantum cryptography
Quantum cryptography
Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...
is not based on the complexity of the computation, but on the special properties of quantum information
Quantum information
In quantum mechanics, quantum information is physical information that is held in the "state" of a quantum system. The most popular unit of quantum information is the qubit, a two-level quantum system...
, such as the fact that quantum information cannot be measured reliably and any attempt at measuring it results in an unavoidable and irreversible disturbance.
A successful open air experiment in quantum cryptography was reported in 2007, where data was transmitted securely over a distance of 144 km.
Quantum teleportation
Quantum teleportation
Quantum teleportation, or entanglement-assisted teleportation, is a process by which a qubit can be transmitted exactly from one location to another, without the qubit being transmitted through the intervening space...
is another promising application, in which a quantum state (not matter or energy!) is transferred to an arbitrary distant location. Implementations of practical quantum computers are based on various substrates such as ion-traps
Ion trap
An ion trap is a combination of electric or magnetic fields that captures ions in a region of a vacuum system or tube. Ion traps have a number of scientific uses such as mass spectrometery and trapping ions while the ion's quantum state is manipulated...
,
superconductors, nuclear magnetic resonance
Nuclear magnetic resonance
Nuclear magnetic resonance is a physical phenomenon in which magnetic nuclei in a magnetic field absorb and re-emit electromagnetic radiation...
, etc.
As of 2006, the largest quantum computing experiment used liquid state nuclear magnetic resonance quantum information processors, and could operate on up to 12 qubits.
Nature as information processing
The dual aspect of natural computation is that it aims to understand nature by regarding natural phenomena as information processing.The two main directions of research in this area are systems biology and synthetic biology.
Systems biology
Further information: systems biologySystems biology
Systems biology is a term used to describe a number of trends in bioscience research, and a movement which draws on those trends. Proponents describe systems biology as a biology-based inter-disciplinary study field that focuses on complex interactions in biological systems, claiming that it uses...
Computational systems biology (or simply systems biology) is an integrative and qualitative approach that investigates the complex communications and interactions taking place in biological systems.
Thus, in systems biology, the focus of the study is the interaction network
Interaction network
Interaction network is a network of nodes that are connected by features. If the feature is a physical and molecular, the interaction network is molecular interactions usually found in cells...
s themselves and the properties of biological systems that arise due to these networks, rather than the individual components of functional processes in an organism.
This type of research on organic components has focused strongly on four different interdependent interaction networks: gene-regulatory networks, biochemical networks, transport networks, and carbohydrate networks.
Gene regulatory networks comprise gene-gene interactions, as well as interactions between genes and other substances in the cell.
Gene
Gene
A gene is a molecular unit of heredity of a living organism. It is a name given to some stretches of DNA and RNA that code for a type of protein or for an RNA chain that has a function in the organism. Living beings depend on genes, as they specify all proteins and functional RNA chains...
s are transcribed into messenger RNA
Messenger RNA
Messenger RNA is a molecule of RNA encoding a chemical "blueprint" for a protein product. mRNA is transcribed from a DNA template, and carries coding information to the sites of protein synthesis: the ribosomes. Here, the nucleic acid polymer is translated into a polymer of amino acids: a protein...
(mRNA), and then translated into protein
Protein
Proteins are biochemical compounds consisting of one or more polypeptides typically folded into a globular or fibrous form, facilitating a biological function. A polypeptide is a single linear polymer chain of amino acids bonded together by peptide bonds between the carboxyl and amino groups of...
s according to the genetic code
Genetic code
The genetic code is the set of rules by which information encoded in genetic material is translated into proteins by living cells....
.
Each gene is associated with other DNA segments (promoters, enhancer
Enhancer (genetics)
In genetics, an enhancer is a short region of DNA that can be bound with proteins to enhance transcription levels of genes in a gene cluster...
s, or silencer
Silencer (DNA)
In genetics a silencer is a DNA sequence capable of binding transcription regulation factors termed repressors. Upon binding, RNA polymerase is prevented from initiating transcription thus decreasing or fully suppressing RNA synthesis....
s) that act as binding site
Binding site
In biochemistry, a binding site is a region on a protein, DNA, or RNA to which specific other molecules and ions—in this context collectively called ligands—form a chemical bond...
s for activator
Activator
Activator may mean:* Activator , a DNA-binding protein that regulates one or more genes by increasing the rate of transcription* Activator , a type of effector that increases the rate of enzyme mediated reactions...
s or repressor
Repressor
In molecular genetics, a repressor is a DNA-binding protein that regulates the expression of one or more genes by binding to the operator and blocking the attachment of RNA polymerase to the promoter, thus preventing transcription of the genes. This blocking of expression is called...
s for gene transcription.
Genes interact with each other either through their gene products (mRNA, proteins) which can regulate gene transcription, or through small RNA species that can directly regulate genes.
These gene-gene interactions, together with genes' interactions with other substances in the cell, form the most basic interaction
network: the gene regulatory network
Gene regulatory network
A gene regulatory network or genetic regulatory network is a collection of DNA segments in a cell whichinteract with each other indirectly and with other substances in the cell, thereby governing the rates at which genes in the network are transcribed into mRNA.In general, each mRNA molecule goes...
s. They perform information processing tasks within the cell, including the assembly and maintenance of other networks. Models of gene regulatory networks include random and probabilistic Boolean network
Boolean network
A Boolean network consists of a set of Boolean variables whose state is determined by other variables in the network. They are a particular case of discrete dynamical networks, where time and states are discrete, i.e. they have a bijection onto an integer series...
s, asynchronous automata, and network motif
Network motif
Network motifs are connectivity-patterns that occur much more often than they do in random networks. Most networks studied in biology, ecology and other fields have been found to show a small set of network motifs; surprisingly, in most cases the networks seem to be largely composed of these...
s.
Another viewpoint is that the entire genomic regulatory system is a computational system, a genomic computer. This interpretation allows one to compare human-made electronic computation with computation as it occurs in nature.
| Genomic computer | Electronic computer | |
|---|---|---|
| Architecture | changeable | rigid |
| Components construction | as-needed basis | ab initio |
| Coordination | causal coordination | temporal synchrony |
| Distinction between hardware and software | No | Yes |
| Transport media | molecules and ions | wires |
In addition, unlike a conventional computer, robustness in a genomic computer is achieved by various feedback mechanisms by which poorly functional processes are rapidly degraded, poorly functional cells are killed by apoptosis
Apoptosis
Apoptosis is the process of programmed cell death that may occur in multicellular organisms. Biochemical events lead to characteristic cell changes and death. These changes include blebbing, cell shrinkage, nuclear fragmentation, chromatin condensation, and chromosomal DNA fragmentation...
, and poorly functional organisms are out-competed by more fit species.
Biochemical networks refer to the interactions between proteins, and they perform various mechanical and metabolic tasks inside a cell. Two or more proteins may bind to each other via binding of their interactions sites, and form a dynamic protein complex (complexation). These protein complexes may act as catalysts for other chemical reactions, or may chemically modify each other.
Such modifications cause changes to available binding sites of proteins. There are tens of thousands of proteins in a cell, and they interact with each other. To describe such a massive scale interactions, Kohn maps were introduced
as a graphical notation to depict molecular interactions in succinct pictures. Other approaches to describing accurately and succinctly protein-protein interactions include the use of textual bio-calculus or pi-calculus
Pi-calculus
In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, and David Walker as a continuation of work on the process calculus CCS...
enriched with stochastic features.
Transport networks refer to the separation and transport of substances mediated by lipid membranes.
Some lipids can self-assemble into biological membranes. A lipid membrane consists of a lipid bilayer
Lipid bilayer
The lipid bilayer is a thin membrane made of two layers of lipid molecules. These membranes are flat sheets that form a continuous barrier around cells. The cell membrane of almost all living organisms and many viruses are made of a lipid bilayer, as are the membranes surrounding the cell nucleus...
in which proteins and other molecules are embedded, being able to travel along this layer. Through lipid bilayers, substances are transported between the inside and outside of membranes to interact with other molecules.
Formalisms depicting transport networks include membrane systems and brane calculi.
Synthetic biology
- Further information: synthetic biologySynthetic biologySynthetic biology is a new area of biological research that combines science and engineering. It encompasses a variety of different approaches, methodologies, and disciplines with a variety of definitions...
Synthetic biology aims at engineering synthetic biological components, with the ultimate goal of assembling whole biological systems from their constituent components. The history of synthetic biology can be traced back to the 1960s
1960s
The 1960s was the decade that started on January 1, 1960, and ended on December 31, 1969. It was the seventh decade of the 20th century.The 1960s term also refers to an era more often called The Sixties, denoting the complex of inter-related cultural and political trends across the globe...
, when Francois Jacob
François Jacob
François Jacob is a French biologist who, together with Jacques Monod, originated the idea that control of enzyme levels in all cells occurs through feedback on transcription. He shared the 1965 Nobel Prize in Medicine with Jacques Monod and André Lwoff.-Childhood and education:François Jacob is...
and Jacques Monod
Jacques Monod
Jacques Lucien Monod was a French biologist who was awarded a Nobel Prize in Physiology or Medicine in 1965, sharing it with François Jacob and Andre Lwoff "for their discoveries concerning genetic control of enzyme and virus synthesis"...
discovered the mathematical logic in gene regulation. Genetic engineering techniques, based on recombinant DNA
Recombinant DNA
Recombinant DNA molecules are DNA sequences that result from the use of laboratory methods to bring together genetic material from multiple sources, creating sequences that would not otherwise be found in biological organisms...
technology, are a precursor of today's synthetic biology which extends these techniques to entire systems of genes and gene products.
Along with the possibility of synthesizing longer and longer DNA strands, the prospect of creating synthetic genomes with the purpose of building entirely artificial synthetic organisms became a reality.
Indeed, rapid assembly of chemically synthesized short DNA strands made it possible to generate a 5386bp synthetic genome of a virus.
Alternatively, Smith et al. found about 100 genes that can be removed invidually from the genome of Mycoplasma Genitalium
Mycoplasma genitalium
Mycoplasma genitalium is a small parasitic bacterium that lives on the ciliated epithelial cells of the primate genital and respiratory tracts. M. genitalium is the smallest known genome that can constitute a cell, and the second-smallest bacterium after the recently-discovered endosymbiont...
.
This discovery paves the way to the assembly of a minimal but still viable artificial genome consisting of the essential genes only.
A third approach to engineering semi-synthetic cells is the construction of a single type of RNA-like molecule with the ability of self-replication. Such a molecule could be obtained by guiding the rapid evolution of an initial population of RNA-like molecules, by selection for the desired traits.
Another effort in this field is towards engineering multi-cellular systems by designing, e.g., cell-to-cell communication modules
Cell signaling
Cell signaling is part of a complex system of communication that governs basic cellular activities and coordinates cell actions. The ability of cells to perceive and correctly respond to their microenvironment is the basis of development, tissue repair, and immunity as well as normal tissue...
used to coordinate living bacterial cell populations.
Cellular computing
Computation in living cells (a.k.a. cellular computing, or in-vivo computing) is another approach to understand nature as computation.One particular study in this area is that of the computational nature of gene assembly in unicellular organisms called ciliate
Ciliate
The ciliates are a group of protozoans characterized by the presence of hair-like organelles called cilia, which are identical in structure to flagella but typically shorter and present in much larger numbers with a different undulating pattern than flagella...
s.
Ciliates store a copy of their DNA containing functional genes in the macronucleus
Macronucleus
A macronucleus is the larger type of nucleus in ciliates. Macronuclei are polyploid and undergo direct division without mitosis. It controls the non-reproductive cell functions, the everyday tasks, such as metabolism...
, and another "encrypted" copy in the micronucleus
Micronucleus
A the micronucleus is the smaller nucleus in ciliate protozoans, such as the paramecium. In fission it divides by mitosis, and in conjugation furnishes the pairing of gamete nuclei, by whose reciprocal fusion a zygote nucleus is formed, which gives rise to the macronuclei and micronuclei of the...
. Conjugation of two ciliates consists of the exchange of their micronuclear genetic information, leading to the formation of two new micronuclei, followed by each ciliate re-assembling the information from its new micronucleus to construct a new functional macronucleus.
The latter process is called gene assembly, or gene re-arrangement. It involves re-ordering some fragments of DNA (permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s and possibly inversion) and deleting other fragments from the micronuclear copy.
From the computational point of view, the study of this gene assembly process led to many challenging research themes and results, such as the Turing universality of various models of this process.
From the biological point of view, a plausible hypothesis about the "bioware" that implements the gene-assembly process was proposed, based on template guided recombination.
Other approaches to cellular computing include developing an in vivo programmable and autonomous finite-state automaton with E. coli
Escherichia coli
Escherichia coli is a Gram-negative, rod-shaped bacterium that is commonly found in the lower intestine of warm-blooded organisms . Most E. coli strains are harmless, but some serotypes can cause serious food poisoning in humans, and are occasionally responsible for product recalls...
, and designing and constructing in vivo cellular logic gates and genetic circuits that harness the cell's existing biochemical processes.
See also
- DNA computingDNA computingDNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
- Quantum computing
- Synthetic biologySynthetic biologySynthetic biology is a new area of biological research that combines science and engineering. It encompasses a variety of different approaches, methodologies, and disciplines with a variety of definitions...
- Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
- Natural Computing Journal
Further reading
This article was written based on the following references with the kind permission of their authors:Many of the constituent research areas of natural computing have their own specialized journals and books series.
Journals and book series dedicated to the broad field of Natural Computing include the journals International Journal of Natural Computing Research (IGI Global),Natural Computing (Springer Verlag), Theoretical Computer Science, Series C: Theory of Natural Computing (Elsevier), the Natural Computing book series (Springer Verlag), and the upcoming Handbook of Natural Computing (G.Rozenberg, T.Back, J.Kok, Editors, Springer Verlag).
- E. Ridge, D. Kudenko, D. Kazakov, and E. Curry,“Moving Nature-Inspired Algorithms to Parallel, Asynchronous and Decentralised Environments,” in Self-Organization and Autonomic Informatics (I), 2005, vol. 135, pp. 35–49.
- Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff,