Transcript Emergent Evolutionary Dynamics of Self

Emergent Evolutionary Dynamics
of Self-Reproducing Cellular Automata
Chris Salzberg
1
Credits
Research for this project fulfills requirements for the
Master of Science Degree - Computational Science
Universiteit van Amsterdam
Project work conducted jointly with Antony Antony (SCS)
Supervised by Dr. Hiroki Sayama
(University of Electro-Communications, Japan)
Mentor: Prof. Dick van Albada
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
2
Lecture Plan
Context & History
Self-reproducing loops, the evoloop
A closer look
I.
II.
III.
a)
b)
New discoveries
IV.
a)
b)
c)
V.
New method of analysis
Genetic, phenotypic diversity
Mutation-insensitive regions
Emergent selection, cyclic genealogy
The evoloop as quasi-species
Conclusions
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
3
Context

Artificial Life:


Study of ”life-as-it-could-be” (Langton).
Emphasizes “bottom-up” approach:
synthesize using e.g. cellular automata (CA)
 study collective behaviour emerging from local
interactions (complex systems)


Artificial self-reproduction:

“abstract from the natural self-reproduction
problem its logical form” (von Neumann)
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
4
A brief history
John von Neumann
Morita & Imai
(shape-encoding worms)
Chou & Reggia
(emergence of replicators)
Imai, Hori, Morita
(3D self-reproduction)
1970
1984
2003
1989
1950s
1996
Conway’s
Game of Life
First international
conference on
Artificial Life
Langton’s
SR Loop
Suzuki & Ikegami
(interaction-based
evolution)
Sayama
(SDSR Loop, Evoloop)
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
5
Self-reproduction in Biology

Traditionally (pre-1950):



Self-reproduction associated with biological systems
of carbon-based organisms.
Research limited by variety of natural self-replicators.
Problem of machine self-replication discussed purely
in philosophical terms.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
6
Theory of self-reproduction

John von Neumann (1950s):

First attempt to formalize self-reproduction:
Theory of Self-Reproducing Automata
 Universal Constructor (UC)



Cellular Automata (CA) introduced (with S.
Ulam).
This seminal work later spawns the field
of Artificial Life (late 1980s).
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
7
The Universal Constructor

Universal Constructor
(1950s):



29 state 5-neighbour cellular
automaton.
Capable of universal
construction.
Predicts separation between
genetic information and
translators/transcribers prior to
discovery of DNA/RNA.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
8
Separation for evolution
P = r-b-r-y
C = r-b-y-y

Separation is necessary for evolution:


Self-description enables exact duplication.
Modified self-description (by noise, etc.)
introduces inexact duplication (mutation).
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
9
UC-based replication: Loops

Loop structure used to represent a cyclic
set of instructions.


Langton (SR Loop), Morita & Imai, Chou &
Reggia, Sayama, Sipper, Suzuki & Ikegami
Self-replication mechanism dependent on
structural configuration of self-replicator.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
10
The self-reproducing loop
genes
sheath
arm
tube




Sheath: Outer shell housing gene sequence.
Genes: 7s (straight growth) and 4s (turning).
Tube: core (1) states within sheath.
Arm: extensible loop structure for replication.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
11
The evolving SR loop
(evoloop)

A new self-reproducing loop by Sayama
(1999), based on SR Loop (Langton, 1984):




9-state cellular automaton.
5-state (von Neumann) neighbourhood.
Modifications to earlier models (SR, SDSR)
enable adaptivity leading to evolution.
Mutation mechanisms are emergent.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
12
Evolutionary dynamics
8
7
6
5
4



Continuous reproduction leads to high-density
loop populations
Evolution ends with a homogeneous, singlespecies population
Evolutionary dynamics seem predictable.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
13
Hidden complexity?



Emergent evolutionary dynamics demand
sophisticated analysis routines.
Original methods use size-based
identification only.
Missing structural detail:



gene arrangement and spacing
genealogical ancestry
Computational routines highly expensive.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
14
A closer look
w
phenotype
l
genotype



Loops composed of phenotype and genotype:
 Phenotype: inner and outer sheath of loop
 Genotype: gene sequence within loop
Define loop species by phenotype + genotype.
Sufficient information for loop reconstruction.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
15
Parallels to biology
remnants

The evoloop is a “messy” system:




dynamic
structures
replication is performed explicitly
mutation operator is emergent
interactions (collisions) produce “remnants” of inert
sheath states and anomalous dynamic structures
Birth and death must be externally defined.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
16
Birth detection
Umbilical Cord
Dissolver (6)
w
phenotype
l
genotype
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
17
Scan-layer tracking
umbilical cord dissolver
Loop Layer
to parent loop
Scan Layer
“footprint”
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
18
Death detection
Dissolver state
Scan layer I.D.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
19
Labeling scheme
G
G
growth
turning
core
G
T
C
G
G C G C G
T
T
G CC CC G
GGGGCGCGTTGCCCCG
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
20
How many permutations?
(n-1) free ‘G’s
‘T’
n

‘TG’
(n-2) free ‘C’s
Constraints for exact (stable) self-replicators:



2 T-genes, n G-genes, (n-2) C-genes.
T-genes must have no G-genes between them.
Second T-gene directly followed by G-gene.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
21
Genetic state-space
loop
size
4
5
6
7
8
# of
loop # of species loop
species
size
size
15
9
11,440
14
56
10
43,758
15
210
11
167,960
16
792
12
646,646
17
3,003
13 2,496,144
18
# of species
9,657,700
37,442,160
145,422,675
565,722,720
2,203,961,43
0
different
(
)
gene permutations resulting in exact self-
(2n-2)
 For a loop of size n, there are
n-2

replicators (stable species).
Do gene these permutations affect behaviour?
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
22
Phenotypic diversity
1000
2000
3000
4000
GCCCCGGGTTGG
GGGCGTTGCGCC
GGGGTTGCCCCG
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
23
Population dynamics
GCCCCGGGTTGG
size
6
7
6
5
4
4
Gene sequence
GCCCCGGGTTGG
GCCGGGCGTTGCCG
GCCGGGTTGCCG
GGCGTTGCCG
GGTTGCCG
GGTTGCGC
size
6
4
5
Gene sequence
GGGCGTTGCGCC
GCGTTGCG
GCGCGTTGCG
size
6
5
4
5
4
Gene sequence
GGGGTTGCCCCG
GGGTTGCCCG
GGTTGCGC
GGCGTTGCGC
GGTTGCCG
GGGCGTTGCGCC
GGGGTTGCCCCG
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
24
Emergent mutation
GCCCCGGGTTGG
GCCCCGGGTTGGGCCCCGGGTTGGGCCCC…
(a)
(a)
GTTGGGCCCCGGGC
GTTGGGCCCCGGGCGTTGGGCCCCG…
(b)
GGGCGTTGGGCC
GGGCGTTGGGCCGGGCGTTGGGCCGGGCG…
(b)
(c)
GGCCGGGCGTTGCC
GGCCGGGCGTTGCCGGCCGGGCGTTGCCG…
(c)
(d)
GCCGGGCGTTGCCG
(d)
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
25
Fitness landscape


Evolution to both smaller and larger loops
occurs.
Smaller loops dominate:



higher reproductive rate
structurally robust
Fitness landscape balances size-based
fitness with genealogical connectivity.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
26
Graph-based genealogy
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
27
Mutation insensitive regions
GGGGCGC GCCTCCTG G



Certain gene subsequences are insensitive to
mutations:
G{C}T{C}TG
These subsequences force a minimum loop
size.
Evolution confined to non-overlapping subsets of
genealogy state-space.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
28
New discoveries

Long-term genetic diversity:



System continues to evolve over millions of
iterations.
Selection criteria not exclusively size-based
for species with long subsequences.
Complex evolutionary dynamics:


Strong graph-based genealogy.
Genealogical connectivity plays more
important role in selection.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
29
Convergence to minimal loop
1
Size
14
15
16
17
15
14
15
13
2
3
4
5
Gene sequence
GGGGCGGGGGGG GTCCCCCCCCCCCTG
GGGGGCGGGGGGG GTCCCCCCCCCCCTG
GGGGGGCGGGGGGG GTCCCCCCCCCCCTG
GGGGGGGCGGGGGGG GTCCCCCCCCCCCTG
GGGGCGGGGGGGGC GTCCCCCCCCCCCTG
GGGGGGGGCGGG GTCCCCCCCCCCCTG
GGGGGGGGCGGGGC GTCCCCCCCCCCCTG
GGGGGGGGGG GTCCCCCCCCCCCTG
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
6
G
CG
CCG
CCCG
G
G
G
G
30
Cyclic genealogy
Size
18
19
19
20
20
20
20
19
20
Gene sequence
GGGGGGGGGGGGGGG GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGC GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGG GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGGC GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGG GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGCGC GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGG GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGG GCCCTCCCCCCCCCCCCCTG
GGGGGGGGGGGGGGGGGC GCCCTCCCCCCCCCCCCCTG
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
G
G
CG
CG
CCG
G
CGC
GC
GC
31
Observations

Fitness landscape:





fitness  reproduction rate
genealogical connectivity (cycles)
self-generated environments (remnants) ?
Stable state is reached with dominant
species + nearest relatives.
Similar to “quasi-species” model of Eigen,
McCaskill & Schuster (1988).
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
32
Conclusions

Simple models may hide their complexity:





graph-based genealogy
mutation-insensitive regions
emergent selection (self-generated env.)
Sophisticated observation and
interpretation techniques play critical role.
Complex evolutionary phenomena need
not require a complex model.
Section Computational Science, Universiteit van Amsterdam
University of Electro-Communications, Japan
33