DNA Computing For Solving Route Finding Problem
PROJECT DESCRIPTION:
DNA Computing For Solving PCR Problem “Hamiltonian Path Problem”
Will be established in Mansoura the city surrounding the Mansoura University
To solve the Traffic Problems as we can use it to reduce the time and choose the best
Way to reach my goal in a shortest way.
Solving this problem using DNA Computing will provide more speed to find
The true way in time less than traditional ways in time and performance to find
The best way to reach the exact location by using DNA strand and it’s
Methodology using molecules.
DNA Computer is a molecular computer that works biochemically.
It "computes" using enzymes that react with DNA strands, causing chain reactions.
The chain reactions act as a kind of simultaneous computing or parallel
Processing, whereby many possible solutions to a given problem can be presented
Simultaneously with the correct solution being one of the results.
The DNA double helix is stabilized by hydrogen bonds between the bases
Attached to the two strands. The four bases found in DNA are adenine
(abbreviated A), cytosine (C), guanine (G) and thymine (T). These four bases are
Attached to the sugar/phosphate to form the complete nucleotide, as shown for
Adenosine monophosphate.
DNA consists of two long polymers of simple units called nucleotides, with
Backbones made of sugars and phosphate groups joined by ester bonds. These two
Strands run in opposite directions to each other and are therefore anti-parallel.
Attached to each sugar is one of four types of molecules called bases. It is the
Sequence of these four bases along the backbone that encodes information. This
Information is read using the genetic code, which specifies the sequence of the
Amino acids within proteins. The code is read by copying stretches of DNA into
The related nucleic acid RNA, in a process called transcription.
BACKGROUND INFORMATION:
DNA molecular is 1.7 meters long
Stretch out all the DNA in your cells and you could reach the moon 6000 times!
DNA is the basic medium of information storage for all living cells. It has
contained and transmitted the data of life for billions of years.
Roughly 10 trillion DNA molecules could fit into a space the size of a marble.
Since all these molecules can process data simultaneously, you could
theoretically have 10 trillion calculations going on in a small space at once.
The DNA Computing start with Leonard M.Adleman in 1994, He took a
Giant step towards a different kind of chemical or artificial biochemical computer.
Leonard M.Adleman solved an unremarkable problem, A remarkable
Technique, The problem is Hamiltonian Path Problem.
A Hamiltonian path (or traceable path) is a path in an undirected graph
Visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is
A cycle in an undirected graph which visits each vertex exactly once and also
Returns to the starting vertex. Determining whether such paths and cycles exist in
A graph is the Hamiltonian path problem which is NP-complete.
A Hamiltonian path (black) over a graph (blue).
After Adleman successfully solved a directed Hamiltonian path problem
Using the tools of bio molecular engineering, others followed, applying similar
Algorithms to other hard computation problems, as well as devising more efficient
Computational schemes. A number of theoretical models for creating a universal
DNA computer have been developed, and mathematical proofs have shown that
Some models of DNA computing are at least equivalent to a classical Turing
Machine. Other work has concentrated on improving error rates and identifying
Specific types of bio-operations and molecular engineering techniques that could
Be harnessed for computational and storage-related purposes. A limited amount of
Work has been directed at real-life applications and the practical feasibility of
DNA computers.
PROJECT DETAIL:
Goals & Objectives
Goal #1 ــTo increase the speed of processing in finding the suitable way.
Goal #2 ــTo decrease the time in search in search
Goal #3 ــTo find the suitable way between all suggested ways.
Goal #4 ــTo get more speed than genetic algorithm in solving problem.
Clientele
Anybody can use this project on condition he own the program.
Methods
The primary methods for achieving the goals and objectives of the Project
Will be:
Is using DNA strand and it’s Methodology using molecules.
AVAILABLE RESOURCES
Encode city names in short DNA sequences. Encode paths by
connecting the city sequences for which edges exist.
generate random routes as the same asa DNA strands
Generate above Strands by DNA synthesizer mixed and Connected
together
Maps and computers are available
NEEDED RESOURCES
We need real tubes to To do experiments on it.
Also we need lab because when strands Fused make
New dna and new strands.
Real Data to work on it.
EVALUATION PLAN
APPENDIX A - TIME LINE (First Year)
