Application Of Nearest Neighbor Clustering And MCP In K- Arm DNA Computing

Biomolecules are in nanoscale and have good maneuverability as well as powerful signaltransduction capacity, which makes it possible to assemble biological computerbybiomolecules. Winthin the field of bio-computing, DNA computing has gained widespreadconcern since the first time when Dr. Adleman using DNA molecules in labsolvedsuccessfully the famous NP complete problem, Hamilton with7vertices.DNAcomputing try to solve the problem, usually complex prolem in biological laboratry,usingDNA strands asthe basic information carrier, bio-enzyme as the computing tools,bio-manipulation at molecule level as the computing method, and with the original prolemmapped into DNA strands. As a cross-disciplinary subject,which has been developed around20years, many researchers in the field of mathematics, biology, nanoscience and computerand information science have dedicated into this totally new domain.In the view of recentdevelopment, DNA computing has advantages in optimal computation, information securityand so on. In both theory and practice, DNA computing has achieved breakthrough. Howeveras a relatively new subject,DNA computing hasn’t matured and also has numbers of limitionsand difficulties to deal with, especially when it comes to biology operations which hvenalways been high cost and DNA models which haven’t been flexible enough to use.This paperis committed in the study of k-arm DNA molecular model,trying to develop the relationshipbetween k-armed DNA model and the hairpin strcuture model and then based on that to solveNP problems. And the main contents are as follows:Chapter one firstly introduces the research background and significance. After thar, frommacro and micro perspectives summary the condition of DNA computing over the pasttwenty years, including literature statistics, core journals, core authers and the like, providingthe later researchers with some reference.Chapter two mainly introduce the basic knowledge about DNA computing, and putsstrength on three DNA models, k-armed molecules, hairpin structure, and triple-strand DNAmodel, their structure, their respective advatages, and thus the possibility to mix themtogether to solve problems. That is to say, the hairpin structures can be used as the controlmodel of k-armed DNA structure, the the triple-strand structure can be used when screen theDNA pool according to the limit conditions. In order to fully illustrate all the respect, theencoding way, the bio-manipulation as well as DNA models can play the key role to promotethe DNA computing.So the later part of chapter, based on the triple-strand DNA model, wepropose an advanced algorithm by changing the encoding way and the way to read result tosolve the0-1programming.In chapter three, we talk about a special case of k-armed DNA model,3-armed structure.Because the3-armed ones can represent the binary tree structure intuitively, we propese touse them as the basic model, assisted with hairpin structure to close the cleaved arms and thetriple-strand structure to screen to solve the nearest-neighbor clustering. The algorithmanalysis shows that this algorithm does a better job in the scale of encoding and thecomplexity of operations. In addition, what we have done brodes the application territory of k-armed DNA models, which can be used to solve the problems having binary tree as theirstructure.Thek-armed DNA molecules have ability to represent the graph structure, which providesitself good quality to solve problems about graph theory. As to these problems, mainly try tofind some special induced graph that its edges and vertices satisfy some conditions. Thek-armed DNA molecules together with hairpin structure can do a good job to control whichedges to compute and which not. Based on that theory, we propose an algorithm on the basicof k-armed molecules to solve the maximum clique problem. The simulation about thegeneral condition shows that the amount of building blocks we need is polynomial, better thanO(（√3）n). Additionly, the idea of evolutionary computationhas benn involved, trying to easethe difficulity of the index level of the solution space. Then we use C++to do the simulationexperiment of evolutionary computation to see the effect.In chapter five, to illustrate the feasibility and validity of all those proposed algorithms,we give the application examples and their specific encoding and biological operations. Andthe final results show their theoreticalfeasibility and validity.