Untangling Complex Systems, page 90
and memory is to extend the electronic devices into a third, or vertical, dimension, by stacking
together microprocessors and memory chips. 3-D architecture could reduce energy use to less than
one-thousandth that of standard 2-D chips (Sabry Aly et al. 2015).
The constant improvement of electronic computers along with cloud computing (Waldrop 2016),
which is the practice of using a worldwide network of remote servers (computer or software) hosted
on the Internet to store, manage, and process data, are bringing benefits to the study of Complex
Systems. However, this is not the only path that must be followed to succeed in our goal of winning
the Complexity Challenges. We must also trust in the promising route being tracked by the interdis-
ciplinary research line of Natural Computing.
13.3 NATURAL COMPUTING
Researchers working on Natural Computing (Rozenberg et al. 2012) draw inspirations from nature
to propose:
• New algorithms;
• New materials and architectures to compute and store information;
• New methodologies and models to interpret Natural Complexity.
Natural Computing is based on the rationale that every natural transformation is a kind of compu-
tation because information can be encoded through the states of natural systems (Landauer 1991).
The processes that occur in nature can be grouped into two sets: those that involve living beings and
are information-driven, and those that involve only inanimate matter and are driven by force fields.
We can take inspiration from both kinds of natural transformations, as shown in the next paragraphs.
A useful methodology to succeed is that proposed by the cognitive scientists Gallistel and King
(2010), and the neuroscientist Marr (2010). Such methodology requires an analysis of natural phenom-
ena at three levels (as indicated in Figure 13.5). The first is the analysis at the “computational level”
Analysis at the
Implementation
level
Analysis at the
Algorithmic
level
Analysis at the
Computational
level
Natural
phenomena
FIGURE 13.5 A useful methodology for studying complex natural phenomena.
462
Untangling Complex Systems
that consists in determining the inputs, outputs, and the computations that the system can perform.
The second is the analysis at the “algorithmic level” that consists in formulating algorithms that
might carry out the computations defined in the previous level of analysis. Finally, the third is the
analysis at the “implementation level” that consists in looking for mechanisms that can implement
the algorithms.
13.3.1 comPuTing insPired by naTural informaTion sysTems
There are four main categories of natural information systems (see Chapter 12): Biomolecular
Information Systems (BIS, such as a cell), Immune Information Systems (IIS), Neural Information
Systems (NIS), and Social Information Systems (SIS). Their structures, working mechanisms, and
peculiar phenomena, such as evolution and learning, constitute wealthy sources of inspiration for
new algorithms, new computing materials and architectures, and new models to try to understand
Complexity (see Figure 13.6).
In the following section, I report a brief description of some results achieved by imitation of the
Natural Information Systems.
13.3.1.1 Artificial Life, Systems Chemistry, Systems Biology, and Synthetic Biology
The research line called “Artificial life” refers to the theoretical studies and the experimental
implementation of artificial systems that mimic living beings. Its birth is normally attributed to
Chris Langton, who used the term as a title for the “interdisciplinary workshop on the synthesis
and simulation of living systems,” organized in September 1987, in Los Alamos, New Mexico
(Langton 1990). Although life has been studied for a long time, its fundamental principles are still
hidden (Schwille 2017). In fact, there is not a universally accepted definition of life, and we do
not know if the project of producing artificial life is feasible yet. This state of affairs means that
the first level of the analysis of life, the computational level (refer to Figure 13.5), is incomplete.
We can have an idea of the complexity of life if we compare a BIS with a von Neumann computer.
A peculiarity of BIS is the lack of crisp boundaries between memory, processor, input and output
components (Brent and Bruck 2006), and between software and hardware. The hardware of BIS is
made of macromolecules, such as DNA, RNA, proteins, and simple molecules and ions. But DNA
Inspired by natural information systems
Biomolecular information
systems (BIS)
Artificial life; Systems
chemistry; Synthetic biology;
Systems biology;
Membrane computing;
Neural information
Evolutionary computation;
systems (NIS)
DNA, RNA computing;
Immune information
Protein computing
Artificial intelligence;
systems (IIS)
Fuzzy logic;
Artificial immune
Artificial Neural
systems; Chemical
Social information
Networks;
robots; Protein
systems (SIS)
Neuromorphic
computing
Swarm intelligence,·
engineering;
Agent-based modeling;
Robots
Cellular automata;
Amorphous computing;
Systemic computation
FIGURE 13.6 Some of the algorithms, materials, and architectures for computing, and models for interpret-
ing Complex Systems, proposed by drawing inspiration from the Natural Information Systems.
How to Untangle Complex Systems?
463
is also the software (Ji 1999). The DNA code uses the four nucleotides (adenine, cytosine, guanine,
thymine) as letters; the genes as words; the conformations of chromatin as sentences. As we learned
in Chapter 12, a BIS is more comparable to a Neural Information System. In fact, in a cell there
are sensory proteins that collect information; such information is processed within the signaling
network; the output of the computation triggers the genetic network; the latter has the power of
affecting both the metabolic and the signaling network. Systems Biology investigates the char-
acteristic networks of a cell and their interactions (Klipp et al. 2016). The best way to check our
degree of comprehension of life is to develop Systems Chemistry (Ashkenasy et al. 2017) and try
to implement a so-called protocell (Luisi 2006). A protocell is a system that should mimic the first
unicellular organism supposed to be the ancestor of all forms of life on Earth, called LUCA that is
the acronym of Last Universal Common Ancestor (Weiss et al. 2016). This system should have the
properties we consider fundamental for life. The first is teleonomy, which is the quality of having
the purposes of surviving and reproducing. The second is the ability to use matter and energy to
encode information and exploit it to accomplish its objectives. The third is a boundary that sepa-
rates these information-based processes from the environment. The fourth is a metabolic network
to self-sustain the system. The fifth is adaptability to an ever-changing surrounding. The sixth is
the possibility of reproduction, hence birth and death. So far, no one has succeeded to obtain life
from scratch. Perhaps, the easiest way for implementing artificial biological systems is through
“Synthetic Biology.” Synthetic biologists take parts of natural biological systems (“bio-bricks”)
and use them to build artificial biological systems. Their activity is essential not only for under-
standing the phenomenon of life, but also for biomedical application, and production of chemicals
and fuels (Stephanopoulos 2012).
13.3.1.2 Membrane Computing
A cell is a really crowded environment. Nevertheless, sophisticated and reliable computations are car-
ried out within it, continuously. The strategical secret is the presence of many compartments, delimited
by membranes, organized hierarchically, and in selective communication. A generic membrane system,
called P-system in honor of its inventor (Paun G. 2002), is a schematic nested hierarchical structure
of compartments, like that shown in Figure 13.7. Each membrane-enveloped region contains objects
and transformation rules that modify these objects, specify whether they will be transferred outside or
stay inside the region, dissolve membranes, and create new membranes. The rules in each region of a
P-system work in a parallel manner. A computation consists in repeatedly applying rules to an initial
configuration of the P system until no rule can be applied anymore, in which case the objects in a priori
specified regions are considered the output of the computation.
Membrane computing finds application in biological modeling, linguistics, computer graphics,
economics (modeling transformations in economy is more difficult than in biochemistry because
the reactions occur not only through encounter of the reagents but also by psychological factors),
cryptography, and computer science to devise sorting, ranking algorithms, and innovative proce-
dures to find approximate solutions of some NP-problems (Nishida 2004).
1
1
2
4
5
6
3
2
4
8
9
3
7
5
6
7
10
10
8
9
FIGURE 13.7 An example of a cell-like structure (on the left) and its tree representation (on the right).
464
Untangling Complex Systems
13.3.1.3 DNA and RNA Computing
The basic idea of DNA computing is to exploit (1) the bases of DNA strands to encode information
and (2) molecular biology tools to make computations. It was Leonard Adleman (1994) who pioneered
the field when he solved a small instance of the Hamiltonian Path Problem (commonly known as the
Travelling Salesman Problem) solely by manipulating DNA strands in a test tube. The Hamiltonian
Path is an example of NP-complete problem (read Chapter 12): given a graph with a certain number
of nodes, i.e., given a map with a certain number of cities, and given a certain number of intercon-
nections between nodes, find the path that starts at the start node and ends at the end node and passes
through each remaining node exactly once. So far, no one has proposed an algorithm that gives the
exact solution in a short time for maps with many nodes (whose number is indicated by N). There are
only algorithms that give approximate solutions, achievable in reasonable time. An algorithm of this
kind requires the generation of random paths through the graph. Then, for each randomly generated
path, it is necessary to follow the instructions reported in the flowchart of Figure 13.8.
Adleman (1994) chose a Hamiltonian Path Problem with seven cities and fourteen flights shown
in Figure 13.9 (You may try to solve this problem as an exercise. Usually, it takes about one minute).
For understanding the main idea and procedure contrived by Adleman, it is enough (Adleman 1998)
to consider a map that contains four cities (Rome, Berlin, London, and Madrid) linked by six flights, as
shown in Figure 13.10. The task is to determine a Hamiltonian Path that starts from Rome and ends in London. Each city is named through a sequence of bases, defined randomly. In the example of Figure 13.9,
Rome is encoded through a sequence of eight bases, as ACTTGCAG; the first half of the sequence is
conceived as the first name of the city, whereas the second half is the last name. So, Rome’s last name
is GCAG. London is encoded as CCGAGCAA, and its first name is CCGA. Of course, each city has
its complementary DNA-name, which is the Watson-Crick complement of the strand used as the name.
The next step is to encode the direct flight numbers with specific DNA sequences. The idea
of Adleman was to concatenate the last name of the city of departure with the first name of the
city of destination. Therefore, the flight from Rome to London is GCAGCCGA. Then, Adleman
took a pinch (roughly 1014 molecules) of each complementary DNA city name and a pinch of
Check whether that path starts
at the start node and ends with
the right end node.
NO
YES
Remove that path
Check if that path passes
through exactly N nodes
NO
YES
Remove that path
For each node, check if that
path passes through that node.
NO
YES
Solution not found
Solution found
FIGURE 13.8 Flowchart containing the instructions of the algorithm suitable to solve the Hamiltonian Path
Problem.
How to Untangle Complex Systems?
465
Start
End
FIGURE 13.9 The Hamiltonian Path Problem solved by Adleman (1994) with DNA strands.
City
DNA Name
Complement
ROME
ACTTGCAG
TGAACGTC
BERLIN
TCGGACTG
AGCCTGAC
MADRID
GGCTATGT
CCGATACA
London
Berlin
LONDON
CCGAGCAA
GGCTCGTT
Flight
DNA Flight number
ROME–BERLIN
GCAGTCGG
ROME–LONDON
GCAGCCGA
BERLIN–MADRID
ACTGGGCT
Madrid
Rome
BERLIN–LONDON
ACTGCCGA
BERLIN–ROME
ACTGACTT
MADRID–LONDON
ATGTCCGA
FIGURE 13.10 A trivial Hamiltonian Path Problem solvable by using strands of DNA and the DNA-
hybridization reaction.
each DNA flight number and put them together in a test tube. To trigger the computation, he
added water, DNA ligase (it binds strands of DNA), salt, and a few other ingredients to mimic
a cell environment. Within about one second, the solution of the Hamiltonian Path Problem
was inside the test tube. How was it possible? In the solution, a countless number of collisions
among the many strands occur every instant. It is possible that the strand representing the
Rome-to-Berlin flight number (GCAGTCGG) and that representing the complementary name
of Berlin (AGCCTGAC) meet and stick together through hydrogen bonds, because the last four
bases of the sequence encoding the flight number is the complement of the first four bases of the
sequence encoding the complement of Berlin’s name (see Figure 13.11). If the resulting complex
By DNA ligase
By DNA ligase
By DNA ligase
Complements of
Rome
Berlin
Madrid
London
TGAACGTC AGCCTGAC CCGATACA GGCTCGTT
GCAGTCGG ACTGGGCT ATGTCCGA
Flights from
Rome-to-Berlin
Berlin-to-Madrid
Madrid-to-London
By DNA ligase
By DNA ligase
FIGURE 13.11 Solution of the Hamiltonian Path Problem illustrated in Figure 13.10.
466
Untangling Complex Systems
encounters the strand representing the Berlin-to-Madrid flight number (ACTGGGCT), they
can bind together because the last four bases of the Berlin’s complement are complementary
with the first four bases of the strand representing the Berlin-to-Madrid flight number. The
DNA ligase, present in the solution, concatenates the strands of flight numbers. In this manner,
complexes grow in length. Of course, at equilibrium, the solution contains many combina-
tions of the original 8-bases strands introduced in the test tube. Such combinations represent
complete or incomplete paths, generated randomly as required by the algorithm mentioned at
the beginning of this paragraph. Since Adleman used a large number of DNA strands for each
flight and complementary city name, and since the Hamiltonian Path Problem contained just a
few cities, he was certain that at least one of the molecules formed in the test tube encoded the
Hamiltonian Path: GCAGTCGGACTGGGCTATGTCCGA. The DNA strands found quickly
the solution because the simultaneous interactions of hundreds of trillions of strands repre-
sented a clear manifestation of parallel molecular processing.
To verify if the chemical system in the test tube found the right solution of the Travelling
Salesman Problem, Adleman followed the flowchart illustrated in Figure 13.8 by exploiting molec-
ular biology tools. To discard complexes that did not both begin with the start city and terminate
with the end city, Adleman relied on the polymerase chain reaction (PCR). He introduced many
copies of two short pieces of DNA as primers to signal DNA polymerase to start its Watson-
Crick replication. The primers used were the last name of the start city (GCAG, for Rome) and
