16-03-2011, 11:19 AM
Presented By
Thierry Metais
DNA computing.ppt (Size: 425.5 KB / Downloads: 153)
DNA Computing
Introduction to DNA:
The life’s molecule:
Introduction:
What is DNA computing ?
Around 1950 first idea (precursor Feynman)
First important experiment 1994: Leonard Adleman
Molecular level (just greater than 10-9 meter)
Massive parallelism.
In a liter of water, with only 5 grams of DNA we get around 1021 bases !
Each DNA strand represents a processor !
A bit of biology
The DNA is a double stranded molecule.
Each strand is based on 4 bases:
Adenine (A)
Thymine (T)
Cytosine ©
Guanine (G)
Those bases are linked through a sugar (desoxyribose)
IMPORTANT:
The linkage between bases has a direction.
There are complementarities between bases (Watson-Crick).
(A)ßà (T)
©ßà(G)
DNA manipulations:
If we want to use DNA as an information bulk, we must be able to manipulate it .
However we are talking of handling molecules…
ENZYMES = Natural CATALYSERS.
So instead of using physical processes, we would have to use natural ones, more effective:
for lengthening: polymerases…
for cutting: nucleases (exo/endo-nucleases)…
for linking: ligases…
Serialization: 1985: Kary Mullis à PCR
Thank this reaction we get millions of identical strands, and we are allowed to think of massive parallel computing.
And what now ?
Situation:
Molecular level.
Lots of “agents”. (strands)
Tools provided by nature. (enzymes)
How can we use all this? If there is a utility …
Coding the information:
1994: THE Adleman’s experiment.
Given a directed graph can we find an hamiltonian path (more complex than the TSP).
In this experiment there are 2 keywords:
massive parallelism (all possibilities are generated)
complementarity (to encode the information)
This experiment proved that DNA computing wasn’t just a theoretical study but could be applied to real problems like cryptanalysis (breaking DES ).
Adleman experiment:
Each node is coded randomly with 20 bases.
Let Si be a code, h be the complementarity mapping.
h(ATCG) = TAGC.
Each Si is decomposed into 2 sub strands of length 10: Si = Si’ Si’’
Edge(i,j) will be encode as h(Si’’Sj’)à( preserve edge orientation).
Code:
Input(N) //All vertices and edges are mixed, Nature is working
NßB(N,S0) //S0 was chosen as input vertice.
NßE(N,S4) //S4 was chosen as output vertice.
NßE(N,<=140) // due to the size of the coding.
For i=1 to 5 do Nß+N(N, Si) //Testing if hamiltonian path
Detect(N) //conclusion … ‘
New generation of computers?
In the second part of [1], it is proven through language theory that DNA computing “guarantees universal computations”.
Many architectures have been invented for DNA computations.
The Adleman experiment is not the single application case of DNA computing…
Stickers model:
Memory complex = Strand of DNA (single or semi-double).
Stickers are segments of DNA, that are composed of a certain number of DNA bases.
To use correctly the stickers model, each sticker must be able to anneal only at a specific place in the memory complex.
To visualize:
About a stickers machine?
Simple operations: merge, select, detect, clean.
à Tubes are considered (cylinders with two entries)
However for a mere computation (DES):
Great number of tubes is needed (1000).
Huge amount of DNA needed as well.
Practically no such machine has been created….
à Too much engineering issues.
Why don’t we see DNA computers everywhere?
DNA computing has wonderful possibilities:
Reducing the time of computations* (parallelism)
Dynamic programming !
However one important issue is to find “the killer application”.
Great hurdles to overcome…
Some hurdles:
Operations done manually in the lab.
Natural tools are what they are…
Formation of a library (statistic way)
Operations problems
Conclusion:
The paradigm of DNA computing has lead to a very important theoretical research.
However DNA computers won’t flourish soon in our daily environment due to the technologic issues.
Adleman renouncement toward electronic computing.
Is all this work lost ?
NO ! à “Wet computing”
Thierry Metais
DNA computing.ppt (Size: 425.5 KB / Downloads: 153)
DNA Computing
Introduction to DNA:
The life’s molecule:
Introduction:
What is DNA computing ?
Around 1950 first idea (precursor Feynman)
First important experiment 1994: Leonard Adleman
Molecular level (just greater than 10-9 meter)
Massive parallelism.
In a liter of water, with only 5 grams of DNA we get around 1021 bases !
Each DNA strand represents a processor !
A bit of biology
The DNA is a double stranded molecule.
Each strand is based on 4 bases:
Adenine (A)
Thymine (T)
Cytosine ©
Guanine (G)
Those bases are linked through a sugar (desoxyribose)
IMPORTANT:
The linkage between bases has a direction.
There are complementarities between bases (Watson-Crick).
(A)ßà (T)
©ßà(G)
DNA manipulations:
If we want to use DNA as an information bulk, we must be able to manipulate it .
However we are talking of handling molecules…
ENZYMES = Natural CATALYSERS.
So instead of using physical processes, we would have to use natural ones, more effective:
for lengthening: polymerases…
for cutting: nucleases (exo/endo-nucleases)…
for linking: ligases…
Serialization: 1985: Kary Mullis à PCR
Thank this reaction we get millions of identical strands, and we are allowed to think of massive parallel computing.
And what now ?
Situation:
Molecular level.
Lots of “agents”. (strands)
Tools provided by nature. (enzymes)
How can we use all this? If there is a utility …
Coding the information:
1994: THE Adleman’s experiment.
Given a directed graph can we find an hamiltonian path (more complex than the TSP).
In this experiment there are 2 keywords:
massive parallelism (all possibilities are generated)
complementarity (to encode the information)
This experiment proved that DNA computing wasn’t just a theoretical study but could be applied to real problems like cryptanalysis (breaking DES ).
Adleman experiment:
Each node is coded randomly with 20 bases.
Let Si be a code, h be the complementarity mapping.
h(ATCG) = TAGC.
Each Si is decomposed into 2 sub strands of length 10: Si = Si’ Si’’
Edge(i,j) will be encode as h(Si’’Sj’)à( preserve edge orientation).
Code:
Input(N) //All vertices and edges are mixed, Nature is working
NßB(N,S0) //S0 was chosen as input vertice.
NßE(N,S4) //S4 was chosen as output vertice.
NßE(N,<=140) // due to the size of the coding.
For i=1 to 5 do Nß+N(N, Si) //Testing if hamiltonian path
Detect(N) //conclusion … ‘
New generation of computers?
In the second part of [1], it is proven through language theory that DNA computing “guarantees universal computations”.
Many architectures have been invented for DNA computations.
The Adleman experiment is not the single application case of DNA computing…
Stickers model:
Memory complex = Strand of DNA (single or semi-double).
Stickers are segments of DNA, that are composed of a certain number of DNA bases.
To use correctly the stickers model, each sticker must be able to anneal only at a specific place in the memory complex.
To visualize:
About a stickers machine?
Simple operations: merge, select, detect, clean.
à Tubes are considered (cylinders with two entries)
However for a mere computation (DES):
Great number of tubes is needed (1000).
Huge amount of DNA needed as well.
Practically no such machine has been created….
à Too much engineering issues.
Why don’t we see DNA computers everywhere?
DNA computing has wonderful possibilities:
Reducing the time of computations* (parallelism)
Dynamic programming !
However one important issue is to find “the killer application”.
Great hurdles to overcome…
Some hurdles:
Operations done manually in the lab.
Natural tools are what they are…
Formation of a library (statistic way)
Operations problems
Conclusion:
The paradigm of DNA computing has lead to a very important theoretical research.
However DNA computers won’t flourish soon in our daily environment due to the technologic issues.
Adleman renouncement toward electronic computing.
Is all this work lost ?
NO ! à “Wet computing”