and their Application to the Artificial Evolution of Genetic Regulatory Networks
Genetic Algorithms
Tutorial ICSB 2007
Johannes F. Knabe, Katja Wegner, and Maria J. Schilstra
University of Hertfordshire, UK
STRI, University of Hertfordshire
Overview
Fundamentals
Biological evolution Evolutionary algorithms
Genetic algorithms
Modelling Gene Regulatory Networks (GRNs) Evolution of biological clocks with GRNs Evolution in NetBuilder
STRI, University of Hertfordshire 2
Part 1: Fundamentals
Biological Evolution
STRI, University of Hertfordshire
Biological Evolution
Evolution = change in the gene pool of a population over time Gene = hereditary unit - can be passed on unaltered for many generations Gene pool = set of all genes in a species or population
STRI, University of Hertfordshire
Biological Evolution - Example
English moth, Biston betularia:
Two color morphs: light and dark 1848 dark moths <= 2% of the population Frequency of the dark morph increased:
industrialized areas
1898 95% were dark in Manchester and other highly Soot from factories darkened birch trees the moths landed on Birds could see the ligther colored moths better and
ate more of them more dark moths survived
STRI, University of Hertfordshire 5
Why? natural selection
[Link]
Biological Evolution contd
Natural selection:
Favors those species for further survival and evolution that are best adapted to their environment see English moth
Population is evolving ratio of different genetic types is changing and new types are created
Not each individual !!
Darwin:
Evolution through random variations of heritable characteristics and natural selection
STRI, University of Hertfordshire 6
Evolutionary cycle : Generation
Selection
Parents Recombination Population Mutation
Replacement
Offspring
7
STRI, University of Hertfordshire
Dictionary 1
Gene smallest unit with genetic information Genotype collectivity of all genes Phenotype expression of genotype in environment Individual single member of a population with genotype and phenotype Population set of several individuals Generation one iteration of evaluation, selection and reproduction with variation
STRI, University of Hertfordshire 8
Selection and Reproduction
Selection does not act on genotype at all but on the performance of the phenotype (fitness) There is differential reproduction phenotypes better adapted to the environment are likely to produce more offspring Slightly unfaithful reproduction creates genotypic variations affect traits of the phenotype, which in turn affect fitness These genotypic variations are heritable
STRI, University of Hertfordshire
Recombination (crossover)
Choose two individuals from current population parents New combination of the genetic material of these individuals offspring No new genetic information, only reshuffling of existing information But can have strong effects on phenotype
STRI, University of Hertfordshire
[Link] .edu/honors2001/group12/int [Link]
10
Duplication
[Link] 11
Any doubling of a certain region, e.g. through unequal recombination If this region consists of a gene, it is called gene-duplication
STRI, University of Hertfordshire
Mutation
[Link]
Permanent changes to genetic material
Can be caused by errors during reproduction of DNA
Mutation rate: i.e. 1 in 10.000 bases is incorrectly reproduced
Brings variability into reproduction
Usually small changes at individual level but strongly depends on importance of mutated base to phenotype
STRI, University of Hertfordshire 12
The Evolutionary Mechanisms
Selection and differential reproduction DECREASE diversity in population Genetic operators (mutation, recombination) INCREASE diversity of population
STRI, University of Hertfordshire
13
Part 1: Fundamentals (2)
Evolutionary Computation Genetic Algorithms (GA)
STRI, University of Hertfordshire
14
Evolutionary Computation
Evolutionary Computation
Exploitation of concepts of natural evolution for problem solving using computers Simulation of evolutionary processes (recombination, mutation, selection) for solving a desired problem Particularly well-suited to complex, multidimensional problems too big to search exhaustively (non-linear optimization problems) Cannot solve all problems perfectly, but has fewer restrictions than most problem-solving algorithms
STRI, University of Hertfordshire 16
Optimization
Finding the best solution to a problem Mathematically: finding the minimum or maximum of a function (optimum)
Maximum
Minimum
STRI, University of Hertfordshire 17
Optimization - Problems
Example: hill-climbing
Start with estimate of global maximum Try to improve by finding other solutions that have
a greater value than the current estimate (local search)
STRI, University of Hertfordshire
18
Optimization - Problems
Example: hill-climbing
Start with estimate of global maximum Try to improve by finding other solutions that have
a greater value than the current estimate (local search)
STRI, University of Hertfordshire
19
Optimization - Problems
Example: hill-climbing
Start with estimate of global maximum Try to improve by finding other solutions that have
a greater value than the current estimate (local search) Global
Local maximum maximum
Local maxima = hazards could converge to
local maximum instead of global
STRI, University of Hertfordshire 20
Evolutionary cycle - revisited
(random) start population
Evaluation Population
End? Selection
Parents Recombination Mutation Offspring
21
Replacement
STRI, University of Hertfordshire
Dictionary 2
Individual - one candidate solution Population - set of individuals Genotype - encoded representation of individual Phenotype - decoded representation of individual Mapping - decodes the phenotype Mutation - variability operator that modifies a genotype Recombination/Crossover - variability operator mixing genotypes Fitness - performance of a phenotype with regard to objective Iteration - Generation
STRI, University of Hertfordshire 22
EC - General properties
Exploit collective learning process of a population (each individual = one solution = one search point) Evaluation of individuals in their environment = measure of quality = fitness comparison of individuals Selection favors better individuals who reproduce more often than those that are worse Offspring is generated by random recombination and mutation of selected parents
STRI, University of Hertfordshire 23
Main trends
Genetic algorithms (GAs) Genetic programming (subform of GAs) Evolutionary strategies (ES) Evolutionary programming (EP)
STRI, University of Hertfordshire
24
Genetic Algorithms
GAs - Simple Example
Simple example f(x) = x
Finding the maximum of a function:
f(x) = x Range [0, 31] Goal: find max (31 = 961) Binary representation: string length 5 = 32 numbers (0-31)
= f(x)
STRI, University of Hertfordshire 27
F(x) = x - Start Population
binary String 1 00110 value 6 fitness 36
String 2
String 3 String 4
00011
01010 10101
3
10 21
9
100 441
String 5
00001
STRI, University of Hertfordshire
28
F(x) = x - Selection
binary String 1 00110 value 6 fitness 36
String 2
String 3 String 4
00011
01010 10101
3
10 21
9
100 441
String 5
00001
Worst one removed
STRI, University of Hertfordshire
29
F(x) = x - Selection
binary String 1 00110 value 6 fitness 36
String 2
String 3 String 4
00011
01010 10101
3
10 21
9
100 441
String 5
00001
Best individual: reproduces twice keep population size constant
STRI, University of Hertfordshire 30
F(x) = x - Selection
binary String 1 00110 value 6 fitness 36
String 2
String 3 String 4
00011
01010 10101
3
10 21
9
100 441
String 5
00001
All others are reproduced once
STRI, University of Hertfordshire
31
F(x) = x - Recombination
Parents and x-position randomly selected (equal recombination)
String 1 String 3
partner String 2 String 4
x-position 4 2
String 1:
0 0 1 1 0
0 0 0 1 1
0 0 1 1 1 0 0 0 1 0
String 2:
STRI, University of Hertfordshire
32
F(x) = x - Recombination
Parents and x-position randomly selected (equal recombination)
String 1 String 3
partner String 2 String 4
x-position 4 2
String 3:
0 1 0 1 0
1 0 1 0 1
0 1 1 0 1 1 0 0 1 0
String 4:
STRI, University of Hertfordshire
33
F(x) = x - Mutation
bit-flip:
Offspring -String 1: String 4:
00111 (7) 10111 (23)
10101 (21) 10001 (17)
STRI, University of Hertfordshire
34
F(x) = x
All individuals in the parent population are replaced by offspring in the new generation
(generations are discrete!)
New population (Offspring):
String 1 String 2 String 3 String 4 String 5 binary 10111 00010 01101 10000 10001 value 23 2 13 16 17 fitness 529 4 169 256 289
35
STRI, University of Hertfordshire
F(x) = x - End
Iterate until termination condition reached, e.g.:
Number of generations Best fitness Process time No improvements after a number of generations Best individual: 10111 (23) fitness 529
STRI, University of Hertfordshire 36
Result after one generation:
F(x) = x - Animation
Java-Applet (html page) with examples
STRI, University of Hertfordshire
37
GAs - General
Genetic algorithms
Differences to other search and optimization algorithms:
GAs search from a population of points
(possible solutions), not from a single point GAs use probabilistic, not deterministic rules
STRI, University of Hertfordshire
39
History
In 1960s John H. Holland, University of Michigan:
Abstraction and generalisation of the
population concept with genetic coding and operators
Use in Bioinformatics, e.g.:
motif discovery, sequence alignment, protein structure prediction etc.
STRI, University of Hertfordshire
40
Coding and Mapping
Genetic coding
Finite strings (= genome, represents genotype) Strings consists of units with information (unit = gene) One string ( individual) = one possible solution of the problem Genotype often real numbers or bit string:
1.853
0.492
STRI, University of Hertfordshire
42
Genetic coding and mapping
What should the phenotype look like and how to encode it as a genotype? How does one map from genotype to phenotype, considering the sources of variation (mutation and recombination)?
Highly problem dependent! Hint: small changes to genotype should often result in small changes to phenotype, i.e. similar performance: heritability of traits! heritability of traits is important otherwise GA becomes only random search
STRI, University of Hertfordshire 43
Mapping Example
Binary coding versus Gray coding of a number
Hamming distance:
Number of bits that have to be changed to map one string into another one E.g. 000 and 001 distance = 1
Remember: small changes in genotype should cause small changes in phenotype
STRI, University of Hertfordshire
44
Mapping Example contd
Binary coding of 0-7 (phenotype):
0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111
STRI, University of Hertfordshire 45
Mapping Example contd
Binary coding of 0-7 (phenotype):
0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111
Hamming distance, e.g.:
000 (0) and 001 (1)
Distance = 1 (optimal)
011 (3) and 100 (4)
Distance = 3 (max possible)
STRI, University of Hertfordshire
46
Mapping Example contd
Gray coding of 0-7:
0 1 2 3 4 5 6 7 000 001 011 010 110 111 101 100
STRI, University of Hertfordshire 47
Mapping Example contd
Gray coding of 0-7:
0 1 2 3 4 5 6 7 000 001 011 010 110 111 101 100
Hamming distance:
Two neighboring numbers (phenotypes) have always a genotype distance of 1 (all differ only by one bit flip) OPTIMAL mapping
STRI, University of Hertfordshire 48
Mapping Example contd
Comparing kinship with distance = 1
Binary:
Gray:
STRI, University of Hertfordshire
49
Selection
Selection
Based on fitness function:
Determines how good an individual is (fitness)
Better fitness, higher probability of selection
Selection of individuals for differential reproduction of offspring in next generation Favors better solutions Decreases diversity in population
STRI, University of Hertfordshire
51
Selection - Roulette-Wheel
Each solution gets a region on a roulette wheel according to its fitness Spun wheel, select solution marked by roulette-wheel pointer stochastic selection (better fitness = higher chance of reproduction)
[Link]
STRI, University of Hertfordshire
52
Selection - Elitism
Individual(s) kept unchanged for next population Example:
Selection based on fitness values Keep the best individual of current population unrealistic but ensures best fitness of a
generation never decreases decrease of diversity
STRI, University of Hertfordshire 53
Selection - Tournament
randomly select q individuals from current population Winner: individual(s) with best fitness among these q individuals Example:
select the best two individuals as parents for
recombination
q=6
selection
STRI, University of Hertfordshire
54
Genetic variability operators
Mutation
Varies details, usually exploitive Changes one position in the string
each position same small probability of undergoing a mutation
Goal: search around existing good solution, possibly leave local optima
1.853 1.807
STRI, University of Hertfordshire
56
Recombination/Crossover
Usually explorative Creates new strings by combining parts of two existing strings
Parents:
0 1 1
1 1 0
Offspring:
0
57
STRI, University of Hertfordshire
Recombination
Unequal:
Crossover points independent for each string chosen
Parents:
0 1 1
1 1 0
Offspring:
1
58
STRI, University of Hertfordshire
Fitness
Fitness function
Nature:
only survival and reproduction count how well do I do in my environment
Defined by kinship of genotypes and fitness function Advantage: visual representation can be useful when thinking about model design Limitation: ideas might be too simplistic when not working on toy-problems - complex spaces and movements (think crossover!)
Fitness space structure:
STRI, University of Hertfordshire
60
Fitness space or landscape
0110
0100 0000
0010
0001
0011
1100
1000
1001
Schema of genetic kinship
How we move in that landscape over generations is defined by our variability operators, usually mutation and recombination Now add fitness
STRI, University of Hertfordshire 61
Fitness space or landscape
0110
fitness
0010
0001
0011
0100
0000
1100
1000
1001
Schema of genetic kinship
How we move in that landscape over generations is defined by our variability operators, usually mutation and recombination Now add fitness
STRI, University of Hertfordshire 62
Fitness landscapes contd.
Every snowflake one individual, search focuses on promising regions (due to differential reproduction)
STRI, University of Hertfordshire 63
Animation adapted from Andy Keane, Uni. Of Southampton
x/y axes: kinship, i.e. the more genetic resemblance the closer together z axis: fitness
Fitness space Good design
Easy to find the optimum by local search neighboring genotypes have similar fitness (smooth curve high evolvability)
Fitness
Genotypes
STRI, University of Hertfordshire 64
Fitness space - Bad design
Here we will have a hard time finding the optimum Low evolvability (fitness is right/wrong) Either problem not well suited for GA or bad design
Fitness
Genotypes
STRI, University of Hertfordshire 65
Fitness space Mediocre design
Many local optima, so we are likely to find one However not much of a gradient to find global optimum, random search could do as well
Fitness
Genotypes
STRI, University of Hertfordshire 66
Dynamic fitness landscape
Animation by Michael Herdy, TU Berlin
67
Fitness does not need to be static over generations Can allow to reach regions otherwise uncovered Natural fitness certainly very dynamic
STRI, University of Hertfordshire
Design issues
Integrating problem knowledge
Always to some degree in representation/ mapping Create more complex fitness function Start population chosen instead of a uniform random one
Useful e.g. if constraints on range of solutions Possible problems: Loss of diversity and bias
STRI, University of Hertfordshire 69
Design decisions
GAs: high flexibility and adaptability because of many options:
Problem representation Genetic operators with parameters Mechanism of selection Size of the population Fitness function
Decisions are highly problem dependent Parameters not independent, you cannot optimize them one by one
STRI, University of Hertfordshire 70
Hints for the parameter search
Find balance between:
Exploration (new search regions) Exploitation (exhaustive search in current region) Parameters can be adaptable, e.g. from high in the beginning (exploration) to low (exploitation), or even be subject to evolution themselves
Balance influenced by:
Mutation, recombination:
create indiviuals that are in new regions (diversity!!) fine tuning in current regions
STRI, University of Hertfordshire 71
Selection: focus on interesting regions
Keep in mind
Start population has a lot of diversity Invest search time in areas that have proven good in the past Loss of diversity over evolutionary time Premature convergence: quick loss of diversity poses high risk of getting stuck in local optima Evolvability:
Fitness landscape should not be too rugged Heredity of traits Small genetic changes should be mapped to small phenotype changes
STRI, University of Hertfordshire
72
Wrapping up Part 1
GA- Summary
Selection:
Focus on fittest individuals Adds alternative solutions to population Makes sure that most of the search space is reached
Recombination:
Mutation:
STRI, University of Hertfordshire
74
GA- Summary cont'd
Advantages: Basic method simple and broadly applicable No need for very detailed understandung of the problem But can be adjusted to problem if knowledge present Fast and can be scheduled in parallel Disadvantages: No guarantee to find best solution High computational demands Adapting to problems at hand can be hard, e.g. finding suitable representation/mapping and evolutionary operators Search can get caught in local optima
STRI, University of Hertfordshire 75
More recent inputs from Biology
Populations are spatial, e.g. for speciation interaction (mating, competition) localized to maintain diversity Populations have structure, e.g. niche protection competition will be stronger if many individuals do the same to maintain diversity Diploidy with dominance / recessivity N-point crossover and other variants Morphogenesis instead of simple function mapping (allowing for modularity, making crossover less fatal)
STRI, University of Hertfordshire 76
Part 2: Modelling GRNs
Gene Regulatory Networks (GRNs)
STRI, University of Hertfordshire
77
Evolutionary cycle - again
(random) start population End? End? Selection Parents Parents
Recombination Mutation
Population Population
Replacement
Offspring Offspring
STRI, University of Hertfordshire 78
Evolutionary cycle - again
(random) start population End? End? Selection Parents Parents
Recombination Mutation
Population Population
Replacement
Offspring Offspring
STRI, University of Hertfordshire 79
Selection
Selection based on comparison of individual phenotypes with target phenotype For phenotype read: input/output system
Individual strings in population contain
parameter sets Each parameter set is used to build a different input/output system
STRI, University of Hertfordshire
80
Decoding, Evaluating, Comparing
Decoding
info string 1
info string 2
info string 3
STRI, University of Hertfordshire
82
Decoding
info string 1
System 1
info string 2
System 2
info string 3
System 3
STRI, University of Hertfordshire
83
Evaluating
Input
System 1 Output 1 System 2 Output 2 System 3 Output 3
STRI, University of Hertfordshire
84
Comparing
Output 1
Output 2
Compare wrt
Target
Output 3
STRI, University of Hertfordshire
85
Decoding, Evaluating, Comparing
Input
info string 1
System 1 Output 1
info string 2
System 2 Output 2
Compare wrt
Target
info string 3
System 3 Output 3
STRI, University of Hertfordshire
86
Decoding, Evaluating, Comparing
(Input) info string 1 System 1 Output 1
Decoding rules
Example F(x) = x2
Info
Rules 27
System f(x)
Input -
Output 729
Target Max
11011
STRI, University of Hertfordshire
87
Decoding, Evaluating, Comparing
(Input) info string 1 System 1 Output 1
Decoding rules
Example F(x) = x2 GRN
Info
Rules 27 build GRN
System f(x) GRN
Input -
Output 729
Target Max
11011
Connectivity; parameter values
STRI, University of Hertfordshire
88
(Artificial) Genetic Regulatory Networks (aGRN)
GRNs and aGRNs
Genetic Regulatory Networks (GRN)
The basic control networks that underlie the development and responses of organisms Involve interactions between genes, RNA, proteins Input output transformation systems Built using concepts taken from GRN-theory assumptions on how GRNs work As (very crude) models of the real thing Interest in computational potential
Artificial Genetic Regulatory Networks
Why aGRNs?
STRI, University of Hertfordshire
90
GRN-theory Central Dogma
DNA
(Transcription)
RNA
(Translation)
Protein
(Reverse transcription)
Information flow
STRI, University of Hertfordshire
91
GRN-theory Central Dogma
Control
DNA
(Transcription)
RNA
(Translation)
Protein
(Reverse transcription)
Information flow
STRI, University of Hertfordshire
92
GRN Control
Control of gene expression
Standard notation
Promoter
DNA
Coding region Non-coding region
STRI, University of Hertfordshire
94
Control of gene expression
Single gene
Promoter: Starting point for transcription
Upstream region: Often contains interaction points for Transcription Factors: proteins that repress or activate transcription
STRI, University of Hertfordshire
95
Control of gene expression
TFx (activator) TFy (repressor)
STRI, University of Hertfordshire
96
Control of gene expression
Genetic Regulatory Network
External factors (signals, maternal proteins, )
No limit to number of activators or repressors Protein that acts as an activator for one gene may act as a repressor for another
STRI, University of Hertfordshire
97
GRN Dynamics
Dynamics: Petri-net notation
Messenger RNA dynamics
mRNA
RNA building blocks STRI, University of Hertfordshire 99
Dynamics: Petri-net notation
Messenger RNA dynamics
Factors affecting transcription rate Factors affecting breakdown rate
mRNA
transcription, modification, transport RNA building blocks STRI, University of Hertfordshire
breakdown
100
Symbols: Nodes
State, Store, Place,
SBML: Species
Transition, Process,
SBML: Reaction
STRI, University of Hertfordshire
101
Symbols: Arrows
Function of connected species:
Modifier, Inhibitor, Repressor, Activator, Enhancer,
SBML: ModifierSpecies
Function of connected species
SBML: Reactant
Input,
Funcion of connected species:
SBML: Product
Output,
STRI, University of Hertfordshire
102
Dynamics: what happens?
mRNA production
STRI, University of Hertfordshire
103
Dynamics: what happens?
mRNA production
STRI, University of Hertfordshire
104
Dynamics: what happens?
mRNA production
STRI, University of Hertfordshire
105
Dynamics: what happens?
mRNA breakdown
STRI, University of Hertfordshire
106
Dynamics: what happens?
mRNA breakdown
STRI, University of Hertfordshire
107
Dynamics: what happens?
mRNA breakdown
STRI, University of Hertfordshire
108
Dynamics: what happens?
No activator, no production
STRI, University of Hertfordshire
109
Dynamics: what happens?
No activator, no production
STRI, University of Hertfordshire
110
Worth remembering (1)
Reactant - Consumed during reaction
Reactant stoichiometry > 0 Product stoichiometry > 0
Product - Produced during reaction
Modifier - Neither: only affects reaction rate
Stoichiometry = 0 Dependence defined in the reactions rate equation
(SBML: KineticLaw; transfer function, ) Shape of rate equation depends on process (and how much we know about it)
STRI, University of Hertfordshire
111
Dynamics
Messenger RNA and protein product dynamics
mRNA
protei n
STRI, University of Hertfordshire
112
Dynamics
Messenger RNA and protein product dynamics
protein
STRI, University of Hertfordshire
113
Worth remembering (2)
Constant production without breakdown:
Amount will increase linearly over time
exceptions)
Production plus breakdown:
Amount will reach plateau (usually; there are In general: breakdown processes determine
Time to reach plateau determined by breakdown rate, not production rate
how rapidly a system can respond (adapt) to new external conditions
STRI, University of Hertfordshire 114
Combining control and dynamics
Creating a dynamic GRN model Questions (1)
Aim:
Model as realistic as possible? Computational tool? Control network? Genes (if so: what do they represent)? Transcription factors? Other regulators (e.g. regulatory RNA)? Intermediates (e.g. mRNA)? Signals? Transcription? Translation? Breakdown? Signalling?
GRN constituents
Processes to incorporate Multicellularity
STRI, University of Hertfordshire 116
Creating a dynamic GRN model Questions (2)
Equations that describe process dynamics
Mass-action type rate equations? Saturable? Additive? Logical? Continuous? Discrete multivalued? Boolean (if so: what do 0 and 1 represent)? Continuous? Discrete? Numerical integration of rate equations (if so: stochastic or deterministic)? Finite state automaton? Boolean switching?
Rules for (combined) effects of regulatory interactions
Numerical representation of component values
Representation of time
Evaluation method
STRI, University of Hertfordshire
117
Basic GRN model
Control
Dynamics
STRI, University of Hertfordshire 118
Possible dynamic representation
Rate equations
Product production rate:
v k f ( modifiers ) p p
Product breakdown rate:
v [P ] b k b
Plateau value (steady state):
k p [ P ] f ( modifiers ) k b
kp, kb: production and breakdown rate constants [x]: concentration or amount of species x P: gene product
STRI, University of Hertfordshire
120
Rules for activation and repression
Saturable activation:
p m [ M ] p 1 m [ M ] S ,A
Saturable repression:
1 S , R p 1 m [ M ]
Linear activation:
L ,A m [ M ]p
Linear repression:
L ,R p m [ M ]
m: multiplier p: exponent
STRI, University of Hertfordshire
121
Rules for combinatorial modifier effects
Logical disjunction (or) (saturable):
S S S f ( modifiers ) ( 1 ) 1 2 1 S S f ( modifiers ) 1 2
Logical conjunction (and) (saturable):
S S f ( modifiers ) 1 2 S S f ( modifiers ) 1 2
Addition, multiplication (linear):
L L f ( modifiers ) 1 2 L L f ( modifiers ) 1 2
STRI, University of Hertfordshire
122
Note on GRN representation
No single proper representation method Chosen method depends on aim of study and personal preference However, be aware of:
the way your representation relates to the real thing the type of simplifications that have been made
Tips:
usually, amounts or concentrations do not have negative values simple negative feedback systems are often oscillatory, but the oscillations may well disappear when using smaller time steps, or a less crude representation
STRI, University of Hertfordshire
123
Part 3: Evolving biological clocks
with artificial genetic regulatory networks (aGRNS)
STRI, University of Hertfordshire
124
Introduction
Biological clocks abound in all organisms, even the simplest single celled ones like Gonyaulax' (red tide organism): characteristic example of responsiveness of life on earth
Evolvability of Genetic Regulatory Networks (GRNs) as a paradigm for novel computation
developmental mapping parallelism
STRI, University of Hertfordshire
125
Schematic drawing
Note: no proper genotype/phenotype distinction is made in this drawing!
STRI, University of Hertfordshire 126
Schematic drawing - Phenotype
A gene is a gene-node in a regulatory network here This is the phenotype!!!
STRI, University of Hertfordshire
127
What does a gene-node consist of?
module binding site binding site activatory/inhibitory Protein produced activation type
... + / - ...
gene-node
binding sites: protein input from other genes module: grouping of inputs any number of binding sites, any number of modules one protein output type and one activation type
STRI, University of Hertfordshire 128
Encoding of gene-nodes and genome
Genome consists of a number of genes plus a compartment coding parameters global to the cell '0'/'1' code, '2' module boundary, '3' gene boundary; used for compartmentalization
encodes one gene-node
0210013
010111021101020011113
gene delimiter
0110011
module boundary
STRI, University of Hertfordshire
129
Encoding of gene-nodes and genome contd
Two modules:
1) inhibitory (starting with 0) binding a combination of proteins 5 (101) and 6 (110) 2) activatory cis-module (starting with 1) to which protein 5 (101) will bind.
gene activation type modules 1) and 2) output binding sites b. site protein
010111021101020011113
regulator type junk (ignored bits)
Last three zeros of 11010200 are ignored junk. Will produce protein 7 (111) and is off by default (last bit is 1).
STRI, University of Hertfordshire
130
Activation
binding sites: AND(
modules: OR( gene (activiation function):
activation increases one protein level
+ + -
protein levels: (global, 8 here)
7
131
STRI, University of Hertfordshire
Activation contd
As protein values are not boolean, AND is actually minimum and OR is a sum, but effect very similar
every gene is either of constituitive (default on, dotted line) or induced (default off, continuous line) type
STRI, University of Hertfordshire 132
Gene-node activation example
protein 5: 20 per site and type 6: 1 per site bind
binding sites: modules:
5:20
6:1
-
[=1] [-1]
5:20
[=20]
+ [+20]
gene: (activation function f)
[f(-1+20)=~125]
activation increases
protein level:
7:+125
STRI, University of Hertfordshire 133
Environmental in-/output
simple protein in-/output periodic functions used:
input 1)-4), 400 time steps wavelength 20 time steps
variations with perturbations: +/- noise with std. dev. 0.1 +/- 2x blackout of 20 steps desired behaviors 1) or 3) closeness of match = fitness
STRI, University of Hertfordshire 134
Selection and Variation
Tournament selection:
15 individuals randomly picked from population,
best two of them chosen as parents weak elitism (only the best individual copied over)
Mutation:
1% chance for every bit to flip 0->1, 1->0
Recombination:
unequal crossing over, always two parents for two
children Length of genes might change, number of genes is held constant in these experiments
STRI, University of Hertfordshire 135
Recombination
Unequal crossing-over allows for genomes of varying length, important for varying number of binding sites and modules Unequal crossover point is shifted by an offset Note that offset always stays within the compartment, so all crossover point genes but one are kept intact 0210013
010111021101020011113 1100110 110111021101020011113 0110011 +
parents
1102103
offset of 3
offspring
0210013
010111021 020011113 0110011
1102103 110111021 021101020011113 1100110
STRI, University of Hertfordshire 136
Population development example
Can easily evolve to show cyclic behavior Genome length and junk length increase on average (average over 10 runs)
STRI, University of Hertfordshire
137
Individual dynamics analysis
internalization of (quasi-) periodic behaviour in many cases the more unreliable the input the more this was found
two evolved GRNs getting out of synchrony when stimuli are missing
two evolved GRNs with extremely different internalized wavelengths
STRI, University of Hertfordshire 138
Evolvability - Heterochronicity
slightly mutated variants
evolved wild type
all variants are one or two bit flips away from each other can allow heterochronic control: changes in timing are possible while preserving general dynamics remember: small genotype changes usually should cause small phenotype changes for smooth adaptation
STRI, University of Hertfordshire 139
Differentiation schematic
Individual has two cells with same genome and almost same input, but different behavior required
Note: Again no clear seperation of genotype and phenotype in this drawing!
STRI, University of Hertfordshire 140
Differentiation: two pathways
Same ultimate goal functions (periodic and inverse) but different fitness evaluations over initial generations
Immediate setting:
fitness is final objective from beginning: one cell reproduces phase of input while the other has to produce inverse
gradual setting:
fitness is initially the same phase reproduction from beginning, but target phase shifts for one of the cells over generations changing fitness landscape!
STRI, University of Hertfordshire 141
Typical example runs for the two settings
1) immediate
2) gradual evaluation
Best results similar, but average much better for 2), robustly finds good results
STRI, University of Hertfordshire 142
Part 4: Netbuilder'
a tool for construction, simulation and evolution of GRNS
STRI, University of Hertfordshire
143
NetBuilder (Project Apostrophe)
A tool for construction modelling simulation (stochastic, deterministic, hybrid) evolution future: Analysis of GRNs Uses the Petri-net formalism
Download:
[Link]
STRI, University of Hertfordshire 144
NetBuilder NetBuilder
NetBuilder':
completely overhauled version different model visualisation more simulation and analysis methods
STRI, University of Hertfordshire 145
NetBuilder - Petri net
bipartite graph place e.g. proteins (circle) transition e.g. reaction, gene (rectangle) arc - connection between a place and a transition (what is
consumed to produce what)
transition
place
STRI, University of Hertfordshire
146
NetBuilder - GUI
STRI, University of Hertfordshire
147
NetBuilder - GUI
Drawing area
arcs layers places transitions text objects
STRI, University of Hertfordshire
148
NetBuilder - GUI
Table of attributes of an selected object
STRI, University of Hertfordshire
149
NetBuilder - GUI
Model hierarchy
overview about which place/transition belongs
to which layer
STRI, University of Hertfordshire
150
NetBuilder - GUI
Tool bar
open
new layer
save
print zoom
copy paste
new layer place
arc text
select rectangular delete region
transition
STRI, University of Hertfordshire
151
Evolution in NetBuilder'
Based on Johannes' GA Differences:
Genotype: list of arcs, places, transitions,
parameters Phenotype: Petri net Mapping: Petri net construction Fitness: likeness to target function (sum square error)
STRI, University of Hertfordshire 152
Genotype - Phenotype
Gene:
These arcs or nodes in a gene are fixed and cannot be removed by evolutionary operators but attributes can be adjusted
STRI, University of Hertfordshire
153
Genotype Phenotype (2)
Network:
Activation and inhibition of protein production between genes Changeable
STRI, University of Hertfordshire
154
Furthermore
Remember:
No limit to number of activators or repressors Protein that acts as an activator for one gene may act as a repressor for another
Mathematical description:
Automatically created by NetBuilder' or users add their own function to each transition
Environmental input:
Each place can have any input function (e.g. sine or step functions like in Johannes' GA)
STRI, University of Hertfordshire 155
Selection
Tournament:
Select randomly 15 networks (default) The two best networks of these 15 are
recombined
Elitism:
By default the best network is kept in the next
generation (fitness never decreases)
STRI, University of Hertfordshire 156
Recombination
Two networks recombined A gene and its arcs go into the child Probability: 90% (default)
STRI, University of Hertfordshire
157
Mutations
Add or remove arcs
Increase or decrease arc attributes (e.g. arc weight = stochiometry)
Duplicate or remove genes (inluding arcs)
Increase or decrease transition rate Probability: 1% (default)
STRI, University of Hertfordshire
158
Fitness
Fitness: Likeness between target function and current results protein
STRI, University of Hertfordshire
159
Parameters
as adjustable as possible
General parameters:
STRI, University of Hertfordshire
160
Parameters
as adjustable as possible
General parameters:
Probabilities:
STRI, University of Hertfordshire
161
Parameters
as adjustable as possible
Probabilities:
General parameters:
Setting parameters to 0 turns operators off
STRI, University of Hertfordshire 162
Summary NetBuilder'
Easy-to-use GUI
Free and open-source Create network, simulate (and evolve) it
Evolution adjustable to user's needs
Evolutionary algorithm in test phase now and will be available in NetBuilder soon !!
[Link]
STRI, University of Hertfordshire
163
ICSB 2007 - Posters
For further discussions meet us at our posters (Tuesday and Wednesday):
Johannes: In Silico Evolution Of Biological Clocks With Genetic Regulatory Networks, F5 Katja: Netbuilder' - A Tool For The Modeling And Simulation Of Genetic Regulatory Networks, G8
STRI, University of Hertfordshire
164
Acknowledgement
Chrystopher L. Nehaniv
Ralph Gauges Mark Robinson Slides:
[Link]
STRI, University of Hertfordshire
165
Resources
Evolutionary Algorithms
[Link] Evonet flying circus [Link] The on-line tutorial on evolutionary computation [Link] Bck, T, Fogel, D B and Michalewicz, Z, ed.: Evolutionary Computation 1 & 2. Taylor & Francis 2000 Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley 1989 Langdon, W.B. and Poli, R. Foundations of Genetic Programming. Springer 2002
STRI, University of Hertfordshire
166
References
Evolving biological clocks with aGRNs
Knabe, J. F., Nehaniv, C. L. and Schilstra, M. J. Genetic Regulatory Network models of Biological Clocks: Evolutionary history matters. In Artificial Life, 2007 (in press). [Link] Knabe, J. F., Nehaniv, C. L. and Schilstra, M. J. Evolutionary Robustness of Differentiation in Genetic Regulatory Networks. In Proceedings of the 7th German Workshop on Artificial Life 2006 (GWAL7), pages 75-84, Akademische Verlagsgesellschaft Aka, Berlin, 2006. [Link] Knabe, J. F., Nehaniv, C. L. and Schilstra, M. J. The Essential Motif that wasn't there: Topological and Lesioning Analysis of Evolved Genetic Regulatory Networks. In IEEE Symposium on Artificial Life (CI-ALife'07), pages 69-76, Omnipress, 2007. [Link] and references therein
STRI, University of Hertfordshire
167