DNA Computing and its Application
- 格式：pdf
- 大小：727.75 KB
- 文档页数：25
DNA Computing and its ApplicationJunzo WatadaGraduate School of Information,Production and Systems,Waseda University, Kitakyushu,Japan808-0135,junzow@osb.att.ne.jp1IntroductionThe objectives of this Chapter are twofold:firstly to introduce DNA compu-tation,and secondly to demonstrate how DNA computing can be applied to solve large,complex combinatorial problems,such as the optimal scheduling of a group of elevators servicing a number offloors in a multi-storey building.Recently,molecular(or wet)computing has been widely researched not only within the context of solving NP-complete/NP-hard problems–which are the most difficult problems in NP–but also implementation by way of digital(silicon-based)computers[23].We commence with a description of the basic concepts of‘wet computation’,then present recent results for the efficient management of a group of elevators.2DNA ComputingThe main idea behind DNA computing is to adopt a biological(wet)technique as an efficient computing vehicle,where data are represented using strands of DNA.Even though a DNA reaction is much slower than the cycle time of a silicon-based computer,the inherently parallel processing offered by the DNA process plays an important role.This massive parallelism of DNA processing is of particular interest in solving NP-complete or NP-hard problems.It is not uncommon to encounter molecular biological experiments which involve6×1016/ml of DNA molecules.This means that we can effectively real-ize60,000TeraBytes of memory,assuming that each string of a DNA molecule expresses one character.The total execution speed of a DNA computer can outshine that of a conventional electronic computer,even though the execution time of a single DNA molecule reaction is relatively slow.A DNA computer is thus suited to problems such as the analysis of genome information,and the functional design of molecules(where molecules constitute the input data). J.Watada:DNA Computing and its Application,Studies in Computational Intelligence(SCI) 115,1065–1089(2008) c Springer-Verlag Berlin Heidelberg20081066J.WatadaDNA consists of four bases of molecular structure,named adenine(A), guanine(G),cytosine(C)and thymine(T).Furthermore,constraints apply to connections between these bases:more specifically,A can connect only with T,and G only with C–this connecting rule is referred to as‘Watson-Crick complementarity’.This property is essential to realize the separate operation (discussed later).In other words,it is possible to separate a partial string of characters‘ad’so that a DNA sequence complementary to the DNA denoting ‘ad’is marked,input into a test tube,hybridized to form a double-strand helix of DNA,then abstracted.Further,this property enables us to randomly create a set of character strings according to some rule.Since Adleman described a method for solving a directed Hamiltonian path problem with seven cities using DNA molecules[1],researchers have pursued theoretical studies to realize general computation using DNA molecules–for example,[31].Adleman has developed a computational model to realize, via experimental treatment of DNA molecules,operations on multiple sets of character strings,following the encoding offinite alphabet characters onto DNA molecules[2].As previously mentioned,DNA molecules can be used as information stor-age ually,DNA sequences of around8–20base-pairs are used to represent bits,and numerous methods have been developed to manipulate and evaluate these.In order to manipulate a wet technology to perform com-putations,one or more of the following techniques are used as computational operators for copying,sorting,splitting or concatenating the information contained within DNA molecules:•ligation,•hybridization,•polymerase chain reaction(PCR),•gel electrophoresis,and•enzyme reaction.In the following Section we briefly describe the specific bio-chemical process which serves as the basis of our DNA computing approach.A DNA computer performs wet computation based on the high ability of special molecule recognition executed in reactions among DNA molecules. Molecular computation wasfirst reported in[1],where it was found that a DNA polymerase–which incorporates an enzyme function for copying DNA–is very similar in function to that of a Turing Machine.DNA polymerase composes its complementary DNA molecule using a single-strand helix of a DNA molecule as a mold.On the basis of this characteristic,if a large amount of DNA molecules is mixed in a test tube,then reactions among them occur simultaneously.Therefore,when a DNA molecule representing data or code reacts with other DNA molecules,this corresponds to super-parallel processing and/or a huge amount of memory in comparison with a conventional(electronic)computer.DNA Computing and its Application1067 2.1Encoding SchemeIn any DNA computational procedure,the main challenge is to encode each object of interest into a DNA sequence.A correct design is essential in order to ensure optimal results;an incorrect design could result in wrong sequences following the ligation process.Ligation and HybridizationWhen DNA sequences are dropped in a test tube using a micro pipet-tor(Fig.1),the DNA sequences recombine with each other by means of some enzyme reaction,this process being referred to as‘ligation’.All DNA sequences to be used in the experiment–along with their complements–are mixed together in a single test tube.Normally the oligonucleotide or DNA mixture is heated to95o centigrade(celsius)and cooled to20o C at 1o C per minute for hybridization,as indicated in Fig.1.The reaction is then subjected to a ligation.At the end of this process,a certain DNA sequence will ligate together with another DNA sequence in order to produce a new sequence.Polymerase Chain Reaction(PCR)Polymerases perform several functions,including the repair and duplication of DNA.Polymerase Chain Reaction(PCR)is a process that quickly ampli-fies the amount of specific DNA molecules in a given solution,using primer extension by polymerase.Each cycle of the reaction doubles the quantity ofFig.1.Droppers for spoiding and hybridizing1068J.Watadathis molecule,leading to an exponential growth in the number of sequences. It consists of the following key processes:1.Initialization:a mix solution of template,primer,deoxynucleotide-triphos-phate(dNTP)and enzyme is heated to94–98◦C for1−9minutes to ensure that most of the DNA template and primers are denatured;2.Denaturation:heat the solution to94–98◦C for20–30seconds for separationof DNA duplexes;3.Annealing:lower the temperature enough(usually between50–64◦C)for20–40seconds for primers to anneal specifically to the single-strand DNA (ssDNA)template;4.Elongation/Extension:raise temperature to optimal elongation tempera-ture of Taq or similar DNA polymerase(70–74◦C)for the polymerase adds dNTP’s from the direction of5 to3 that are complementary to the template;5.Final Elongation/Extension:after the last cycle,a5–15minute elongationmay be performed to ensure that any remaining ssDNA is fully extended.Steps2through4are repeated20–35times;less cycles result in less prod-uct,too many cycles increases the proportion of incomplete and erroneous products.PCR is a routine job in the laboratory that can be performed by an apparatus called a thermal cycler.Denaturation Temperature Gradient PCRDenaturation temperature gradient PCR(DTG-PCR)is a modified PCR method in which the denaturation temperature changes with cycle[22].In DTG-PCR,conventional PCR is performed where the temperature of the denaturation step(step2of the aforementioned PCR procedure)is gradually increased.Quantitative PCRQuantitative PCR(Q-PCR)is a modification of the PCR used to rapidly measure the quantity of DNA,complementary DNA(cDNA)or Ribonucleic Acid(RNA)present in a sample.It may be used to determine if a DNA sequence is present in a sample,as well as the number of copies produced in PCR.Affinity SeparationThe objective of the affinity separation process is to verify whether each datum includes a certain sequence.This process permits single strands containing a given subsequence v to befiltered out from a heterogeneous pool of other sequences.After synthesizing strands complementary to v and attaching themDNA Computing and its Application1069Fig.2.Electrophoresisto magnetic beads,the heterogeneous solution is passed over the latter.Those strands containing v anneal to the complementary sequence and are retained; those strands not containing v pass through and are discarded.Normally,in this process a double-stranded DNA is incubated with the Watson-Crick complement of data that is conjugated to magnetic beads.A bead is attached to a fragment complementary to a sub-string,then a magnetic field used to extract all the DNA fragments containing such a sequence.The process is then repeated.Gel ElectrophoresisGel electrophoresis is an important technique for sorting DNA strands by their size[4].Electrophoresis enables charged molecules to move in an electric field,as illustrated in Fig.2.Basically,DNA molecules carry negative charge. Thus,when we place them in an electricalfield,they tend to migrate towards a positive pole.Since DNA molecules have the same charge per unit length, they all migrate with the same force in an electrophoresis process.Smaller molecules therefore migrate faster through the gel,and can be sorted according to size(usually agarose gel is used as the medium here).At the end of this process the resultant DNA is photographed,as indicated in Fig.3.3Comparison with Conventional ComputingNow DNA computing employs completely different tactics when allocating an independent letter code(such as ATCG,GTAC or CAAC)to each sample. Next,DNA sequences corresponding to the number of possible combinations are prepared.After they are hybridized in super-parallel fashion,the remain-ing DNA fragments are amplified to obtain an answer sequence–note that this procedure is carried out only once[17].1070J.WatadaFig.3.CameraThe main benefit of using DNA computation to solve complex problems is that all possible solutions are created concurrently–in other words,it offers massively parallel processing.By contrast,humans–as well as most electronic computers–solve problems in a step-by-step manner(in other words,sequentially).DNA provides other benefits,including low cost,and energy efficiency[2].The main steps in DNA computing are:1.Separate(T,s):this operation separates a given set T into the set+(T,s)of characters,including character string s and the set−(T,s)of character strings that do not contain character string s.This operation corresponds to abstract experimentation on DNA molecules in a test tube.DNA Computing and its Application1071 2.Mix:this operation mixes sets T1and T2into the union set T1∪T2.Thisoperation corresponds to mixing test tubes T1and T2.3.Detect(T):this operation returns‘YES’if the test tube T is not empty,and‘NO’if it is empty.The operation corresponds to an experimental treatment procedure that detects the existence of DNA molecules by the electrophoreticalfluorescent method.4.Amplify(T):this operation corresponds to creating multiple sets T1and T2with the same contents as the given set T.This corresponds to an experi-mental treatment that amplifies the amount of molecules using polymerase chain reaction(PCR).Now from the perspective of DNA computing,the most important char-acteristic of a DNA molecule is its Watson-Crick complementarity.In Adleman’s model,a set of character strings–computed using hybridiza-tion–is computed according to the four steps described ing this computation,an NP-complete problem can be solved using an algorithm based on production-detection PCR.DNA computers can be used to solve real-world problems using this method.4Applications of DNA ComputingThe theory of DNA computing is discussed in[2,27,29].DNA computing has been applied to variousfields,including nanotechnology,combinatorial optimization[25,26],Boolean logic circuit development[27],and of particular relevance to the present Chapter,scheduling[18,20,23,29,33].5Approaches to Optimization and SchedulingWe have a long history of mathematical approaches for solving optimization problems.However there are limitations with such methods,resulting in many problems remaining unsolved.Beyond such mathematical methods,‘problem solving’in general attempts to mimic human or empirical approaches as a ‘rule-of-thumb’.This became prevalent after the von Neuman computer was invented in1945.Subsequently,this led to a‘golden era’in artificial intelli-gence(AI)during the late1970s and early1980s,even though logic approaches (including production systems,predicate logic,semantic networks,and frame systems),present their own challenges,and can lead to combinatorial explo-sion.On the other hand,in order to mimic human thinking,many other methods have been proposed,including fuzzy systems,genetic algorithms (GAs),chaotic systems,artificial neural networks(ANNs),and so on–which are collectively referred to as‘soft computing’.If we intend to solve large-scale,real-world problems,we need to overcome this issue of combinatorial explosion.In short,NP-complete problems cannot be solved using present-day silicon-based computers.1072J.WatadaGenetic Algorithm(GA)A genetic algorithm(GA)is a soft computing technique modeled on genetic mechanisms within biological organisms,and which searches for optimal val-ues,obeying a number of simple constraints in each successive generation. GAs have been successfully applied to elevator group management[8,15]. The setting of parameters in such elevator group control systems is difficult to achieve manually;[10]demonstrated that GAs are able to provide good parameter settings.Artificial Neural Network(ANN)In articial neural networks(ANNs),optimization of an evaluation function can be implemented using backpropagation(BP)learning based on past transactions[28,32].Fuzzy Logic and Other Soft Computing ApproachesIn the fuzzy logic approach,the ease of update rules comes as a welcome relief in comparison with GAs and/or ANNs[16,19].Other soft computing methods that have been successfully applied to elevator group control optimization include reinforcement learning agents[11],evolutionary strategies[7],and genetic network programming[12–14].New DemandsRecently,new generation elevator systems–such as the elevator group super-visory control system(EGSCS)[5,6]–have been developed to satisfy the various needs of users and to enable the‘verticalization’of buildings[3]. These new types of elevator system place additional constraints on group management.When searching a large number of alternatives,they require fast processing and large computer overhead.Accordingly,group management systems have been intensively studied in order to improve elevator transporta-tion efficiency and age conditions of an elevator system are changed depending on time and customers.Business people don’t like to wait very long,whereas hotel guests do not like crowded elevators,even if it they are transported quickly.Elevator systems are required to fulfill passengers’different preferences.6Elevator Management SystemMultiple elevators are commonly used in high-rise buildings(‘skyscrapers’). Effective control of such multiple elevators is essential.The overall aim in con-trolling a group of elevators is to satisfy the time constraints of all passengers,DNA Computing and its Application1073 at the same time providing the most efficient system.The basic problem is to decide which elevator should stop at a particularfloor where passengers are waiting to go up(down).Even in peak(rush)hours,it is possible tofind all elevators moving in the same direction,or alternatively all elevators arriving simultaneously at the samefloor.In order to resolve such situations,all elevators need to be optimally assigned to passengers,regardless of the latter’s changing arrival times at the variousfloors in the multi-storey building.The group control system selects elevator movement patterns according to random changes in traffic volumes and/or driving management,or in the eventuality of an accident.Such group control realizes comfortable,safe and economical management of elevators.Suppose that a building has Nfloors and m elevators.Table1shows the current position of each elevator and the destinations of passengers in each elevator,together with the intended travel direction of passengers waiting on eachfloor.Figure4illustrates this situation graphically:the left-hand graph shows an upward movement,and the graph on the right-hand side a downward movement,respectively.Elevators A,B and M stop atfloors2,N−1,and 3,respectively.On the other hand,there are people onfloor1who desire to go up,and people onfloors N−1and N who desire to go down.At time t, Elevator A atfloor2has passengers who are going tofloors3,4and N−1. Furthermore,there are passengers onfloors N,N−1and1who are going down,down,and up,respectively.Accordingly,in this research,the input information to the elevator man-agement system is as follows:1.The present position of each elevator;2.The destinationfloors of each elevator(the requiredfloor numbers wherepassengers in each elevator are going are input to the system);3.Thefloors from which each elevator have been called(people on eachfloorcan indicate their direction but they cannot input their destinationfloor).Table1.Elevator information at time-tFloor Queuing Elevator-A Elevator-B···Elevator-mN↓N−1↓(1,3,5)...3(4,N−1,N)2(3,4,N−1)1↑1074J.WatadaElevator MUPWARDFig.4.Whole paths of M elevatorsAs previously mentioned,Table 1shows that Elevator-A is at Floor 2and has passengers who are going to floors 3,4and N −1;likewise Elevator-B is at Floor N −1and has passengers travelling down to Floors 1,3and 5.There are people who are going up on Floor 1,down on Floor N −1,and down on Floor N .Based on this information,the challenge is to efficiently manage all elevators.6.1Restrictions on Elevator MovementsThe problem is to determine the optimal scheduling of all m elevators –in other words to provide the shortest overall wait time –given the wait queueand the initial position of each elevator at any time t.Let us denote the following variables:|d(m)−o(m)|is the total number offloors movedC t is the time cost of an elevator traveling between adjacentfloorsC s is the time cost of an elevator stopping at afloorThe elevator moves betweenfloors–denoted by m–must be consecutive, in other words,d(m i)=o(m i+1)∨1≤i<N(1) where o(m)is the originalfloor,and d(m)is the destinationfloor The traveling time T betweenfloors can be represented asT(|d(m)−o(m)|)=[|d(m)−o(m)|]C t+C s m=destination,0otherwise.(2)The output of the graph G given by the sum of the costs thus represents the total travel time of elevator-E,that isG(E)=Nm=1T(|d(m)−o(m)|)(3)For a building with M elevators,the graph of single elevator movements shown in Table2can be duplicated M times in representing the whole paths of elevator travel.The total traveling time of M elevators can thus be calculated by summing the traveling time of each single elevator asG(E1,E2,...,E M−1,E M)=Mk=1G(E k)(4)The optimal travel route–denoted O–is thus given by the minimum total traveling time of all elevators with all initial conditions and requirements satisfied,namelyO=min{G(E1E1,E2,...,E M−1,E M)}(5)Table2.Elevator management informationFloor Calling Elevator-A Elevator-B6(2,3)5↓4↑3↓21(3,5)6.2Elevator SchedulingNow since we have m elevators,we can duplicate m graphs and connect between all vertices in the one graph.Figure5shows the case where m=2.The left-hand side of Fig.5illustrates all paths which are going up,and the right-hand side all paths going down.Elevator-A atfloor1can move to allfloors from2to n.However when Elevator-A is atfloor j,it can move to allfloors from j+1to n,but cannot move down,for example tofloors1 through i.The right-hand side graph shows the same situation concerning the downward movement of the same Elevator-i.The connections between both graphs show the changing of direction from down to up(or from up to down). These changes of direction happen on allfloors.The connections between elevators on the samefloor show that passengers can move from one elevator to another(but these movements are not considered in the computations because they depend on passenger preferences).It is therefore sufficient that one of the m elevators may reach the calling floor on the line of graph A,B,···,m.Let us construct a graph for each case where elevator-A or elevator-B,···,and elevator-m reach afloor where the button has been pushed.UPWARDFig.5.Whole paths of two elevatorsConsidering all combinations,let us calculate the shortest path of each graph A,B,···,m.Suppose that f(1,2,···,m)denotes the largest value of graphs A,B,···,m.By calculating all combinations f x(A,B,···,m),we can obtain the optimal allocation of elevators by selecting the minimum value of f x(A,B,···,m),where x denotes the number of combinations.For example, when the number of elevators is2and the number of callingfloors is3,the number of combinations is23.It is possible to represent elevator-B by a graph,just as we did in the case of elevator-A.Figure5illustrates the graph of all paths of the two elevators A and B.Now,elevator-A is currently atfloor-1and its destinationfloors are3and 5.The destinationfloors of elevator-B atfloor-6are2and3.There are also upward calls.Figure5shows thefloors with a symbol where one or both elevators should stop.In this case,if the destinationfloor has been decided for elevator A or B, then the other one is automatically assigned to the other destinationfloor.As a result,it is necessary to calculate the optimal paths for two kinds of graphs for elevators A and B.The larger value for both elevators A and B is denoted by f x(A,B).The problem here is to select the smallest value–min(f(A,B),(x= 1,2,···,8)).The obtained schedule which gives the smallest value is the opti-mal solution for elevators A and B.There are16kinds of graph which can be obtained from8combinations,as shown in Figs.4and5.The next Section shows how to calculate the shortest path schedule for both elevators.7Bio-Soft Computing Based on DNA LengthIn DNA computation,each base sequence is assigned to afloor,as shown in Table3.Let us denote the connection between two base sequences corresponding to eachfloor as the movement between twofloors.Further,let us assign an Table3.Correspondence betweenfloors and base sequences123456AAAA CCCC T T T T AT AT GAGA GGGG1’2’3’4’5’6’CACA T CT C T GT G GCGC CAGT GAT Cappropriate length of DNA sequence to the edge weight:rllψk=f(k)+T Eψ1=f(1)+T E string of two random characters(ZZ)...ψ5=f(5)+T E string of ten random characters(Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y)(6) f(A,B)=max(4+4+4+4+4,4+2+4+4+4+2+4+4+4+4) =max{20,36}=36(7) These values show the time spent moving between twofloors,which are combined in the base sequence.In this problem all movements betweenfloors comprise40roots.Let us produce DNA sequences corresponding to these roots in Table4.Let us produce DNA fragments corresponding to afloor in Table3and DNA fragments corresponding to a root in Table4.Next,place these DNA fragments and combining polymerase in the same test tube and store the test tube at an appropriate temperature;all combinations will be automatically created.Various DNA sequences are automatically created by combining fragments shown as eachfloor,andfilaments shown as each movement root,respectively, in Table4.These DNA sequences correspond to combinations of feasible solu-tions.In order to solve the graph shown in Fig.5,DNA sequences which have‘AA’(the former two characters upward at thefirstfloor)at the start, and‘GA’(the latter two characters upward at thefifthfloor)at the end are detected,out of the many DNA sequences,using various polymerase.As we know thefloors where elevators should stop,only DNA sequences with AA∗T T T T∗GA are selected–in other words those where the DNA sequences start with‘AA’,pass through‘T T T T’,and terminate at‘GA’. Then,the shortest DNA sequence shows the optimal solution which starts at the1stfloor,stops at the3rdfloor,and reaches the6thfloor.This procedure can be abstracted by the weight of a DNA sequence,since long DNA sequences are‘heavy’and short DNA sequences are‘light’.At the end we check the DNA sequence and convert it to afloor number.The shortest roots for graphs5 through12contain the following DNA sequences,and the length of these DNA sequences can be calculated.The shortest sequence is the schedule where elevator-A stops at the4th floor,and elevator-B stops at the3rd and5thfloors.Therefore,the optimal schedule for elevators-A and B is obtained for the present state of elevators and callingfloors.If this computation is pursued to obtain the optimal schedule whenever buttons are pushed at a callingfloor,the schedule with the shortest wait time will always be obtained.Table4.Representation of roots by DNA sequence(edge DNA oligonucleotides) 1→2AAZZCC6’→5’GAZZGTT T EEGG CT EECA1→3AAW W W W T T6’→4’GAW W W W CGT T F F F F AA CT F F F F GC1→4AAV V V V V V AT6’→3’GAV V V V V V T G T T HHHHHHT A CT HHHHHHAG1→5AAXXXXXXXXGA6’→2’GAXXXXXXXXT C T T IIIIIIIICT CT IIIIIIIIAG1→6AAY Y Y Y Y Y Y Y Y Y GG6’→1’GAY Y Y Y Y Y Y Y Y Y CA T T JJJJJJJJJJCC CT JJJJJJJJJJGT2→2’CCT C5’→5CAZZGAGGAG GT EECT2→3CCZZT T5’→4’CAZZCGGGEEAA GT EEGC2→4CCW W W W AT5’→3’CAW W W W T GGGF F F F T A GT F F F F AC2→5CCV V V V V V GA5’→2’CAV V V V V V T C GGHHHHHHCT GT HHHHHHAG2→6CCXXXXXXXXGG5’→1’CAXXXXXXXXCA GGIIIIIIIICC GT IIIIIIIIGT3→3’T T T G4’→4GCATAAAC CGT A3→4T T ZZAT4’→3’GCZZT GAAEET A CGEEAC3→5T T W W W W GA4’→2’GCW W W W T CAAF F F F CT CGF F F F AG3→6T T V V V V V V GG4’→1’GCV V V V V V CA AAHHHHHHCC CGHHHHHHGT4→4’AT CG3’→3T GT TT AGC ACAA4→5AT ZZGA3’→2’T GZZT CT AEECT ACEEAG4→6AT W W W W GG3’→1’T GW W W W CAT AF F F F CC ACF F F F GT5→5’GACA2’→2T GCCCT GT CT GG5→6AT ZZGG2’→1’T GZZCAT AEECC CT EEGT6→6’GGGA1’→1CAAACCCT GT T T8Bio-Soft Computing with Fixed-Length DNAFor the elevator dispatching problem,an N-story building equipped with M identical elevator cars given by up calls,down calls,and car calls.The optimal route is given by min{G(1,2,···,N)}.The key factor to cost sequence design is the T m of a DNA strand.The concept is to design the DNA sequences that have heavier weights with higher T m then those lighter weights.DNA amplification and detection techniques often depend on oligonucleotide T m.The T m of a DNA duplex is defined as the temperature where one-half of the nucleotides are paired and one-half are unpaired[34].The T m indicates the transition from double helical to random coil formation and is related to the DNA GC base content[24]. Usually expressed as a percentage,it is the proportion of GC-base pairs in the DNA molecule or genome sequence being investigated.GC-pairs in the DNA are connected with three hydrogen bonds instead of two in the AT-pairs, which makes the GC-pair stronger and more resistant to denaturation by high temperatures.In our encoding scheme,the DNA sequences that represent floor nodes arefixed length,and costs are distinguished by T m of the given DNA strands.This design makes an oligonucleotide with lighter weight,which means that more economical path tend to have a lower T m.All the possible solutions are randomly generated by DNA hybridization and ligation with the oligonucleotides representingfloors,edges,and costs.To satisfy the conditions of an elevator dispatching problem,the route must begin and end at a specified node,and the route must pass by each consecutivefloor until it reaches thefinal destination.The PCR can be applied to test the former requirement,which is a tech-nique for amplifying DNA that rapidly synthesizes many copies of a specific DNA segment by providing specific complementary sequences(primers)and enzymes(DNA polymerases–for example,Pfu and Taq).The DNA strands corresponding to the originalfloor and the complement of thefinal destination floor are used as two primers in two successive PCRs to reproduce the routes.To test the latter requirement,agarose gel electrophoresis is applied. Agarose gel electrophoresis is a method to separate DNA strands by size,and to determine the size of the separated strands by comparison with strands of known length.All PCR products are sieved by agarose gel electrophoresis, and unreasonable lengths are excluded.To verify the DNA strands pass by every consecutivefloor,the product from the above step is affinity-purified with a biotin-avidin magnetic bead system.To solve the elevator routing problem with our molecular algorithm,note that all possible end paths of elevator-i are joined with the start path of elevator-(i+1),so that the total output of the graph G(1,2,···,N)–representing the travel route of all elevators–can be calculated.DTG-PCR is a specified PCR protocol that modifies the denaturation temperature profile.If the denaturation temperature is decreased to a certain level in PCR,the DNA strands with denaturation temperatures lower than that temperature will be denatured and amplified.As the denaturation tem-perature is increased cycle-by-cycle in PCR,other DNA strands with higher denaturation temperature will also be amplified.However,the economical。
