Research And Application On DNA Computing For Routing Problems With Constraint

Routing algorithms with constraints is always a hot issue in telecommunicationfield.Most routing problems with special constraints are NP-Complete problems,however.they can be solved in polynominal time only if NP=P.There are severalpseudo-polynominal time algorithms for these questions,but these algorithms must beconfined in restriceted conditions as to ensure the time efficiency.Dr.Adlemanproposed the concept of DNA computing firstly in1994,and he also solved a7nodeHamilton path problem by a DNA algorithm,which shows huge potential capacity ofsolving complicated questions by DNA computing.Because of the speciality ofrouting problems, the time complexity of these problems can be convert to spacecomplexity of DNA strands take advantage of highly parallelism of DNAcomputing.So we can work out exact solutions for these questions in polynominaltime.This paper proposed a commonly used DNA coding scheme for solving routingproblems,and we also worked out algorithms for two routing problems with specialconstraints by DNA computing.Routing problem with explicit node constraint can be generally defined asshortest path problem with explicit node constraint.An algorithm that combined theelectronic computer with DNA computing is proposed to solve the routing algorithmssatisfying explicit node constraint in this paper. The algorithm consists of foursub-algorithms: graph transform algorithms,start-end point search and cutalgorithms,result search algorithms for transformed graph,result reading algorithms.The theoretic analysis shows that the usage of electronic computer part of thealgorithm could cut down the number of nodes and links sharply so that thecorresponding DNA volume strands could be reduced. And the scale of nodes andlinks which can by solved by DNA computing is amplified as long as the DNA strandsnumber is constant in one test tube.The DNA computing part of the algorithms canparallel search for the shortest path and work out result in polynominal time.Link-disjoint paths can be used to ensure the stability of businesstransmission,increase transmission bandwidth and achieve network load balancing.Ahigh efficiency parallel algorithm is proposed in this paper by improving theelectronic computer algorithm LIDOMPA into DNA computing algorithm for solving Link-disjoint paths problem. This algorithm is mainly composed by route searchingalgorithm,route classify algorithm, link-disjoint paths construct algorithm.Thealgoritms proposed in this paper will oprimize the time complexity of the operationsfrom exponential time to polynominal time on DNA computing.We discussed DNA computing algorithms for two routing problems with specialconstraints and proposed an universial DNA coding scheme for solving routingproblems. As long as biotechnology of DNA computing become mature enough, theDNA computing will play a bigger role in solving routing problems.