Transcript PPT - 서울대 Biointelligence lab

Molecular Evolutionary Computing
(MEC) for Maximum Clique Problems
March 9, 2004
Biointelligence Laboratory
School of Computer Science and Engineering
Seoul National University
Dong-Yeon Cho
([email protected])
Introduction (1/2)

Molecular Evolutionary Computing (MEC)
 Previous DNA computing techniques
 We
have to make all possible solutions but it is so difficult.
 Conventional Experiments
• A few pico mole: 6.02 1011
 Ex)
Binary problems (n = 50)
• 250  1.11015
 Ex)
Combinatorial problems (n = 20)
• 20!  2.41018
 Evolutionary Computation
 Evolutionary
computing uses the power of natural selection to
turn computers into automatic optimization and design tools.
 The three mechanisms that drive evolution forward are
reproduction, variation (crossover or mutation) and the Darwinian
principle of survival of the fittest.
© 2004 SNU CSE Biointelligence Lab
2
Introduction (2/2)

Previous Work [Wood et al., 2001]
 A design for DNA computation of the OneMax problem
 One
nucleotide for one gene
 It is difficult to implement crossover and mutation.
 I doubt that this approach can be applied to other problems.

Our Approach
 Constructive method
 Serially
assembling the building blocks
 Only primitive experiments
© 2004 SNU CSE Biointelligence Lab
3
Problem

Maximum Clique Problem
2
3
 Clique
1
 A set
of vertices in which every
vertex is connected to every
other vertices by an edge
4
0
 Maximum clique problem
5
1
4
 Given
a graph containing n
vertices and m edges, how many
vertices are in the larges clique?
0
2
 Example
1, 0) → 010011
 (5, 4, 3, 2) → 111100
 (4,
2
3
1
4
0
© 2004 SNU CSE Biointelligence Lab
5
4
Previous Work (1/3)

Basic Blocks [Ouyang et al., 1997]
 two DNA sections
bit’s value (Vi)
V0~V5
position value (Pi)
P0~P6
0 bp when Vi =1
10 bp when Vi =0
20 bp
Longest = 610 + 720 = 200bp (000000)
Shortest = 60 + 720 = 140bp (111111)
dsDNA
© 2004 SNU CSE Biointelligence Lab
5
Previous Work (2/3)

POA (parallel overlap assembly)
 12 oligonucleotides
PiViPi+1 for even i
P’i+1 V’i P’i for odd i
P0V0P1
P4V4P5
P’2V’1P’1
P’6V’5P’5
P2V2P3
P’4V’3P’3
DNA polymerase + dNTPs
© 2004 SNU CSE Biointelligence Lab
6
Previous Work (3/3)

Logical Process
 Unique restriction enzyme for
each Vi
 Not scalable
Unconnected edge 0-2
© 2004 SNU CSE Biointelligence Lab
7
Our Approach (1/3)

Preliminary Steps
 For each unconnected edge
 Make
3 different building-block sequences using POA in parallel.
 Ex) 0-2 {xxx0x0, xxx0x1, xxx1x0}
• In case <xxx010>
Before POA
After POA
• In case <xxx000>
Before POA
After POA
 PCR
with upper primer (P0) and lower primer (P’3).
© 2004 SNU CSE Biointelligence Lab
8
Our Approach (2/3)

Constructive method
 Serially assembling the building blocks
 Mix
<0-2> and <1-3>.
 Perform POA.
 PCR with (P0) and lower primer (P’4).
0-2
1-3
xxx0x0
xxx0x1
xxx1x0
 Gel
xx0x0x

xx0x1x
0-3
xx0000 xx0001 xx0100
=
xx1x0x
xx0010 xx0011 xx0110
xx1000 xx1001 xx1100
electrophoresis and extraction.
 Mix <0-3> and <1-5>, then we can obtain <0-5>.
© 2004 SNU CSE Biointelligence Lab
9
Our Approach (3/3)
 Split <0-5> into 3 tubes.
 PCR with different primers.
 P0V0(0)
and V’5(0)P’6
 P0V0(0) and V’5(1)P’6
 P0V0(1) and V’5(0)P’6

Final Step
 The mixed solution may contains the candidate DNA
molecules, that is, the cliques.
 The clique of largest size is represented by the shortest
length of DNA.
 The lowest band is the answer.
© 2004 SNU CSE Biointelligence Lab
10
Discussion

Advantage
 There is no restriction enzymes.
 Only primitive experimental steps
 POA (similar
to PCR), PCR, and Gel electrophoresis
 Scalability

Disadvantage
 Errors in POA step
 Serial constructive steps
 (n(n-1)/2
– m)
• m is the number of connected edges in the given graph.
© 2004 SNU CSE Biointelligence Lab
11