Team:AHUT China/Demonstrate
Demonstrate
Demonstrate
The shortest path problem has direct application value in the analysis of traffic network structure, choice of transportation lines (highway, railway, river shipping lines, air lines, pipeline transportation line etc.), building and maintenance of communication lines, the analysis of minimum cost of transport of goods and planning of city public transportation network and other aspects.
The shortest path problem is often used in the vehicle navigation system and a variety of emergency systems such as the 110 alarm, 119 fire and 120 medical rescue system.These systems generally are required to calculate the time should be in 1s to 5s when it comes to the best route to the scene. In the driving process calculating the route in front of the vehicle constantly is also needed. All of these determine that the realization of the shortest path problem should be efficient.
At present, the shortest path algorithm of the map navigation software on the market has been very perfect.Typical algorithms are Dijkstra algorithm, Ford algorithm, A* algorithm and so on. However, with the growth of the scale of the problem, the algorithm takes exponential growth. Thus, it is a new method to solve the shortest path problem with DNA computer.
The project of Biological compass in 2014 reflected the superiority of the DNA computer.The sections and locations are expressed by the DNA chain in this road network, computing time is significantly reduced and the specificity of the protease makes it easy to select a specific location.
This year's project aims to add new information to the path of the DNA chain including actual length of path,the number of path and so on. So we can simulate the actual road network better.
In this project, we expect to build a new bio-navigational system in order to find the shortest way between two points. We use the DNA single strand to represent 8 points and 13 sides we designed on the following map and find out the shortest way through biological methods.
Firstly, four quaternary numbers are used to represent site and pathway information. Then, the base sequence of 40bp is used to represent information of every site and lines are represented by 52bp DNA single strand. In the middle of each line is 12bp base sequence, that is the effective information. Respectively, pre-4bp sequence is GGGG’s identification code; mid-4bp sequence indicates the number of this part of path; post-4bp sequence indicates the length of path.
Later, we start bridging the sites and lines, random combination of sites and lines can get all possible path site combination from Site No.2 to Site No.8.
After that, we did experiments.
First, synthesize base sequence of sites and lines.
Next, design the primers according to Site No.2 and Site No.8.
Then, massively proliferate the DNA chain of “site” and “line” through PCR, make full reaction under optimum conditions.
After the reaction, electrophoresis method was used to get the electrophoretic map of all DNA chains, and the comparison was carried out to find out the shortest DNA chain.
Last, recover the DNA chain of the shortest strip and obtain the optimal answer by sequencing.
This is the shortest sequence of the optimal answer.
<2.6.8>=144bp
It is the single BioBrick part of the optimal answer <2.6.8>.
And this is the BioBrick device with the part guided into the Plasmid pSB1C3.
