Transcript 1 1 1 1 1 1 1 0 0 0 0 0 0 0 parents cut cut 1 1 1 0 0 0 0 0 0 0

Artificial Intelligence:
from Computer Science
to Molecular Informatics
Joost N. Kok
Artificial Intelligence


Movie Artificial Intelligence by Steven
Spielberg
Five year studies at universities of Utrecht,
Amsterdam, Groningen and Maastricht
Artificial Intelligence


The concept that machines can be improved
to assume some capabilities normally
thought to be like human intelligence such as
learning, adapting, self-correction, etc.
The extension of human intelligence through
the use of computers, as in times past
physical power was extended through the use
of mechanical tools.
Artificial Intelligence

On May 11, 1997, an IBM computer named
Deep Blue whipped world chess champion
Garry Kasparov in the deciding game of a sixgame match
Artificial Intelligence


First Robot World Cup Soccer Games held in
Nagoya, Japan in 1997
Goal: team of robots beats the FIFA World
Cup champion in 2050
Artificial Intelligence




Alan Turing
Turing Award
Turing Machine
Turing Test
Artificial Intelligence

Turing Test
Artificial Intelligence




Natural language processing: it needs to be
able to communicate in a natural language
like English
Knowledge representation: it needs to be able
to have knowledge and to store it somewhere
Automated reasoning: it needs to be able to
do reasoning based on the stored knowledge
Machine learning: it needs to be able to learn
from its environment
Artificial Intelligence

Turing Machine
Time Complexity






Turing machine gives notion of computability
Time complexity: how many steps does it
take to find an answer?
Combinatorial Explosion
Problems that are computable in polynomial
time (class P)
Problems that are verifiable in polynomial
time (class NP)
P equals NP ?
Natural Computing

Computing carried on
or inspired by (gleaned from)
nature
Natural Computing

Computers are to Computer Science as
Comic Books to Literature (Joosen)
Natural Computing

Natural Computing
– Evolutionary Computing
– Molecular Computing
– Gene Assembly in Ciliates
Evolutionary Computing
Evolutionary Computing
Initialize population, evaluate
(terminate)
select
survivors
evaluate
select mating partners
recombine
mutate
Examples


Evolutionary Art
Nozzle
Example: Discrete Representation

Genotype: 8 bits

Phenotype:
– integer
1*27 + 0*26 + 1*25 + 0*24 + 0*23 + 0*22 + 1*21 + 1*20
= 163
– a real number between 2.5 and 20.5
2.5 + 163/256 (20.5 - 2.5) = 13.9609
– schedule
Example: Mutation
before
1 1 1 1 1 1 1
after
1 1 1 0 1 1 1
mutated bit
Mutation happens with probability pm for each
bit
Example: Recombination

Each chromosome is cut into 2 pieces which
are recombined
cut
cut
1 1 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 0 0 0 0
0 0 0 1 1 1 1
parents
offspring
Example: Fitness proportionate selection

Expected number of times fi is selected
equals fi / average fitness

Better (fitter) individuals
have:
– more space
– more chance to be
selected
Best
Worst
Evolutionary Computing
Initialize population, evaluate
(terminate)
select
survivors
evaluate
select mating partners
recombine
mutate
Molecular Computing
Molecular Computing




Implementation of algorithms in biological
hardware, e.g. using DNA molecules and
enzymes
Power lies in massive parallel search
Test tube may contain easily 1015 strands of
DNA
Compared to computers very efficient in
energy consumption, storage density and
number of operations per second
Molecular Computing
Molecular Computing


DNA: sequence of nucleotides linked together
by strong backbone
Nucleotides have attached bases A, T, C, G:
–
–
–
–

Adenine
Thymine
Guanine
Cytosine
Watson-Crick complementarity A-T C-G
Molecular Computing
Hamiltonian path problem
in
out
Molecular Computing

Algorithm
– generate random paths through graph
– keep only paths from the initial to the final
node
– keep only paths that enter exactly n nodes
– keep only paths that enter all nodes
– if any paths remain, the graph contains a
Hamiltonian path
Molecular Computing


For each node, take unique random sequence
over A, C, T, G
For each node, the sequence is of the same
length
Molecular Computing

For every connection, construct a sequence
from the sequences of the two nodes
– Node 1: TATCGGATCGGTATATCCGA
– Node 2: GCTATTCGAGCTTAAAGCTA


Inverse: GTATATCCGAGCTATTCGAG
Sequence: CATATAGGCTCGATAAGCTC
Molecular Computing

Generate random paths through graph
– Mix strings for all nodes with strings for all
arrows, together with Ligase enzyme
Molecular Computing

Apply PCR (Polymerase Chain Reaction)
amplification using as primers string for in
and complement for string out
Molecular Computing

Select molecules that encode paths that enter
exactly n nodes by running contents of test
tube through agarose gel and save DNA
strands of the right length
Molecular Computing


Create single strands by melting
For each node, select those sequences that
anneal to the string of that node
Molecular Computing

Result: implementation of algorithm in DNA
– First experiment took seven days
– Now possible in seven seconds
Molecular Computing



Operations: denaturing, annealing,
separation, selection, multiplying
Simulation of Turing Machine is possible
Problems:
– PCR and separation procedures are error
prone
– DNA may form non-existing pseudo-paths
– DNA may form hairpin loops
– Scalability
Molecular Computing

Combine Evolutionary Computing with
Molecular Computing (EDNA project)
– Use potential errors as feature
– Huge population sizes
– Automation of DNA processing necessary

Many more techniques from molecular
biology can be used
– Plasmids
– Restriction Enzymes
– Fluorescence
Evolutionary Molecular Computing
Gene Assembly in Ciliates
Ciliates



Very ancient ( ~ 2 . 109 years ago)
Very rich group ( ~ 10000 genetically different
organisms)
Very important from the evolutionary point of
view
Ciliates
micronucleus
macronucleus
Ciliates


DNA molecules in micronucleus are very long
(hundreds of kilo bps)
DNA molecules in macronucleus are genesize, short (average ~ 2000 bps)
Gene Assembly in Ciliates
Gene Assembly in Ciliates
Gene Assembly in Ciliates

Micronucleus: cell mating
Macronucleus: RNA transcripts (expression)
Micro: I0 M1 I1 M2 I2 M3 … Ik Mk Ik+1

M = P1 N P 2

Macro: permutation of (possibly rotated)
M1,…, Mk and I0 ,…, Ik+1are removed


Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Molecular Operators
Gene Assembly


Pointer structures
Linked Lists
Natural Computing

Computing carried on
or inspired by (gleaned from)
nature
–
–
–
–
–
Evolutionary Computing
Neural Computing
Molecular Computing
Quantum Computing
Ant Computing