Chinese Journal of Computers   Full Text
Title	A Molecular Solution for Routing Satisfying Explicit Node Constraint on DNA-Based Supercomputing
Authors	YANG Lei HUANG Qi-Xin LI Ken-Li LI Ren-Fa
Address	(College of Computer and Communication, Hunan University, Changsha 410082)
Year	2009
Issue	No.12(2373—2381)
Abstract &   Background	Abstract Routing algorithms satisfying explicit node constraint is a NP-hard mathematical problem.This problem is not only a obstacle for intelligent routing in telegraphic industry,but also for transportation and power transmission. Based on super parallel-computing of DNA computation, an algorithm that combined the merits of traditional computer and DNA computation is proposed to solve the routing algorithms satisfying explicit node constraint in this paper. The proposed algorithm consists of four sub-algorithms: Transform(), FirstEndSearcher(), DNASearcher(), ResultReader(). The theoretic analysis shows that the use of traditional computer part of the algorithm could cut down the amount of nodes and edges sharply so that the corresponding DNA volume strands could decrease from O((n-2)!) to O((m-2)!) where n and m are the amount of nodes and explicit node respectively. A series of biological operations are proposed to search for the accurate solution. In addition, in order to advance the coding-SNR of border-weight and make biological operation feasible,a new DNA-coding rule is also proposed. So that, fast routing algorithms satisfying explicit node constraint will be solved in reasonable time provided that the technology of DNA computing is mature enough in the future. Keywords DNA-coding; loose explicit node constraint route; explicit node constraint route; MPLS ASON Background This research is supported by the National Natural Science Foundation of China under grants (90715029,60603053), the Cultivation Fund of the Key. Scientific and Technical Innovation Project, Ministry of Edacation of China (Grant No.708066), the Program for New Century Excellent Talents in University, NCET): Research on a scalable DNA computer model, the Theory, Model and Method of DNA Computer etc. The projects mainly focus on DNA computer models for processing some hard problems, including encoding DNA sequences, synthesizing DNA molecules, setting up the model, detecting solutions, etc. Our research group has been working on many aspects of DNA computing since 1996 and have published a monograph and more than 50 papers on DNA computing and DNA computer. In this paper, the authors proposed an improved sticker model and DNA algorithm for the problem of routing satisfying explicit node constraint.