10-04-2017, 07:43 PM
[attachment=3397]
DNA BASED EMPLOYEE RECOGNITION
Presented BY,
Rahul.R,
Adith.N.S,
Ashwin Deepu,
Priyanka .E.Nair
S8 CS,
MBCET
Introduction to DNA:
The life s molecule:
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 !
1/ there are two words >
_ DNA a molecule that has an important place in the life process..
However in this context we must consider it as a mere molecule with interesting aspects
_ computing computing research aims at make computations efficiently,
so in this context parallel computing is born which purpose is to do several computations in the same time by distributing them on several processors.
Nevertheless nowadays the biggest parallel computer has at most 2000 processors running simultaneously
For common people this would be large enough but to solve some problems, it appears to be insufficient.
In the 50ies Richard Feynman the physicist spoke about doing some computations on a molecular level
The molecular computing had to wait almost 50 years to get the first real proof of its validity with the experiment of Adelman in 1994.
What is DNA
DNA stands for Deoxyribonucleic Acid
DNA represents the genetic blueprint of living creatures
DNA contains instructions for assembling cells
Every cell in human body has a complete set of DNA
DNA is unique for each individual
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)
Double Helix
Sides
Sugar-phosphate backbones
ladders
complementary base pairs
Adenine & Thymine
Guanine & Cytosine
Two strands are held together by weak hydrogen bonds between the complementary base pairs
Source: Human Physiology: From Cells to System
4th Ed., L. Sherwood, Brooks/Cole, 2001, C-3
Instructions in DNA
Instructions are coded in a sequence of the DNA bases
A segment of DNA is exposed, transcribed and translated to carry out instructions
DNA/CPU COMPARISON
CPU
Sequential Operations
addition, bit-shifting, logical operations (AND, OR, NOT, NOR)
DNA
Parallel Operations
Cut, Copy, Paste, Repair
Can DNA Compute
DNA itself does not carry out any computation. It rather acts as a massive memory.
BUT, the way complementary bases react with each other can be used to compute things.
Proposed by Adelman in 1994
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.
Ligases
Bind molecules together
Concatenates DNA strands
Polymerase
Copies DNA
Primers (Start, Complement of End)
PCR
Gel Electrophoresis
Sort molecules by length
Molecules have a charge
Magnets used
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
Leonard M. Adleman
Background in Mathematics & Computer Science
HIV Research
DNA/Turing Machine similar
Proof of Concept
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 s Experiment
Hamilton Path Problem
(also known as the travelling salesperson problem)
Adleman s Experiment (Cont d)
Solution by inspection is:
Darwin Brisbane Sydney Melbourne Perth Alice Spring
BUT, there is no deterministic solution to this problem, i.e. we must check all possible combinations.
Adleman s Experiment (Cont d)
1. Encode each city with complementary base - vertex molecules
Sydney - TTAAGG
Perth - AAGG
Melbourne - GATACT
Brisbane - CGGTGC
Alice Spring CGTCCA
Darwin - CCGATG
Adleman s Experiment (Cont d)
2. Encode all possible paths using the complementary base edge molecules
Sydney Melbourne AGGAT
Melbourne Sydney ACTTA
Melbourne Perth ACTGG
etc
Recipe
In a test tube add
10^14 molecules of each city
10^14 molecules of each flight
Water, ligase, salt
Answer generated in about one second
100 trillion molecules representing wrong answers also generated
Adleman s Experiment (Cont d)
3. Marge vertex molecules and edge molecules.
All complementary base will adhere to each other to form a long chains of DNA molecules
Adleman s Experiment (Cont d)
The solution is a double helix molecule:
Operations
Melting
breaking the weak hydrogen bonds in a double helix to form two DNA strands which are complement to each other
Annealing
reconnecting the hydrogen bonds between complementary DNA strands
Operations (Cont d)
Merging
mixing two test tubes with many DNA molecules
Amplification
DNA replication to make many copies of the original DNA molecules
Selection
elimination of errors (e.g. mutations) and selection of correct DNA molecules
Pros and Cons
+ Massively parallel processor
DNA computers are very good to solve Non-deterministic Polynomial problems such as DNA analysis and code cracking.
+ Small in size and power consumption
Pros and Cons (Cont d)
- Requires constant supply of proteins and enzymes which are expensive
- Errors occur frequently
a complex selection mechanism is required and errors increase the amount of DNA solutions needed to compute
- Application specific
- Manual intervention by human is required
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
Many issues to be overcome to produce a useful DNA computer.
It will not replace the current computers because it is application specific, but has a potential to replace the high-end research oriented computers in future.
Nanotechnology
Bibliography:
DNA Computing, New Computing Paradigms. Gheorghe Paun,Grzegorz Rozenberg, Arto Salomaa
DIMACS: DNA based computers
Reducing Errors in DNA Computing
by Appropriate Word Design. wdesign.pdf
Links:
http://cs.wayne.edu/ kjz/KPZ/NaturalComputing.html
http://dna2zdnacpu/dna.html
http://intermondeadn/liens.html