Dna Computing A Number Of Issues

Since Adleman successfully solved an instance of Hamiltonian path problem with 7 vertexes, which is a NP-complete problem, biornolecular computation has become a new research field which sets up a bridge over computer science and biology.In this paper, some problems on algorithm and coding are studied within DNA computing, which is the most popular subfield of biomolecular computing.In the first chapter, some background is presented at first, and then a short overview of different researches is given, such as the models of DNA computing, methods to solve NP-complete problems, especially SAT.The idea to use parameterized algorithm to deduce the space complexity of DNA computing is given in the second chapter. In this chapter, a probabilistic parameterized algorithm for vertex cover in sticker model is designed. The probability that this algorithm always return the correct answer is close to 1.Based on the relationship between vertex cover and independent set, Another method for vertex cover is presented which still can deduce the space complexity greatly in case the parameter k is big. Consequently, the parameterized algorithm for independent set within sticker model is developed.In chapter 3, some NP-complete problem with numerical parameters are discussed, including partition and knapsack. The method to solve such...