基於新興領域DNA Computing具有解答高複雜度計算問題的潛力；因此近幾年來，許多歐美的計算機科學家、（分子）生物學家、數學家等積極地投入此領域之研究。DNA Computing目前已被應用在解答NP complete及NP hard問題。故本研究主題係以DNA平行計算研究與應用為主，內容著重在以基礎DNA Computing操作，研究以此為基礎之平行計算之演算法，除解決NP complete及NP hard問題外，並研究將DNA Computing之應用延伸到資訊系統上的可能。
本論文提出了兩個新的DNA演算法，以低時間複雜度解決一著名的NP hard問題:Binary Integer Programming (BIP) problem及針對rule-based system之驗證。文中，我設計一DNA演算法以用來驗證複雜的rule-based system，及一個新的DNA平行加法演算器，利用DNA生物指令操作及此DNA平行加法演算器，以低時間複雜度來快速解決大量資料處理時之NP hard問題，改進以往當隨資料量增加時，解題速度之時間複雜度隨指數成長之困境。本研究之理論基礎與原理是依據Adleman的生物指令及sticker model及Amos之Parallel filter模式為基礎，其研究架構為：
(ㄧ) 設計將資料以DNA strand格式呈現，並對要分析處理之DNA資料下定義。
(二) 針對rule-based system的驗證及BIP問題，描述過去解此類問題的作法，並設計出此兩個問題之複雜度較低的求解之可能的DNA Computing方法，再針對所提出之rule-based system驗證及求解BIP問題之DNA演算法加以分析其時間複雜度。
(三) 最後，將上述的內容用簡單範例，以演算法加以計算，驗證DNA演算法的正確性。
本研究藉由以DNA表示資料的方式，利用DNA可利用在大量平行處理之特質，針對要解答之複雜度高的問題提出演算法，其研究結果可作為DNA Computing的可能應用範圍之探討依據。

Numerous architectures for molecular computing have been proposed. Deoxyribonucleic acid (DNA) based computing, inherently huge parallelism, has been proved of neatly solving some NP complete problems, such as 3-SAT problem, with linearly increasing time as compared to the exponentially increasing time required by Turning machine. The practice of DNA computing has also grown significantly in solving the number of difficult problems. However, the DNA computing technique has not been applied in information system solution to the best of our knowledge. The purpose of this study focuses on the molecular verification of rule-based systems and molecular solutions to the binary integer programming problem based on DNA computation. It consists of three parts: (1) representing data by DNA strands, (2) developing DNA computing algorithms for verifying rules inference by DNA operations to explore the possibility of existing practice and solving BIP problem and (3) solving two instances of verifying rule based system and BIP problem by DNA computing.
Considering the verification of rule-based system, various graphic techniques have been developed to analyze structure errors in rule-based systems that utilize inference (propositional) logic rules. Four typical errors in rule-based systems are: redundancy (numerous rule sets resulting in the same conclusion); circularity (a rule leading back to itself); incompleteness (deadends or a rule set conclusion leading to unreachable goals); and inconsistency (rules conflicting with each other). This study presents a new DNA-based computing algorithm mainly based upon Adleman’s DNA operations. It can be used to detect such errors. There are three phases to this molecular solution: rule-to-DNA transformation design, solution space generation, and rule verification. We first encode individual rules using relatively short DNA strands, and then generate all possible rule paths by the directed joining of such short strands to form longer strands. We then conduct the verification algorithm to detect errors. The potential of applying this proposed DNA computation algorithm to rule verification is promising given the operational time complexity of O(n*q), in which n denotes the number of fact clauses in the rule base and q is the number of rules with longest inference chain.
Binary optimization is a widely investigated topic in integer linear programming. This study proposes a DNA-based computing algorithm for solving the significantly large binary integer programming (BIP) problem. The proposed approach is based upon Adleman and Lipton’s DNA operations to solve the BIP problem. The potential of DNA computation for the BIP problem is promising given the operational time complexity of O(n*k). Indeed, a further analysis of the time complexity may be achieved by experimental means, a possible future work.

[Adleman, 1994] L.M. Adleman, “Molecular Computation of Solutions to Combinatorial Problems”, Science, vol. 266, pp. 1021-1024, 1994.
[Amos, 1998] M. Amos, DNA Computation. PhD thesis, Department of Computer Science, University of Warwick, UK, September 1997.
[Amos, 2004] M. Amos, Theoretical and Experimental DNA Computation, Springer, New York, 2004.
[Balas, 1965] E. Balas, “An additive Algorithm for Solving Linear Programs with zero-One Variables”, Operations Research, vol.13, pp.517-546, 1965
[Beigel, 1998] R. Beigel, and B. Fu, “Solving Intractable Problems with DNA Computing”, in proceedings of the 13th Annual Conference on Computational Complexity (invited lecture), pp.154-168, 1998.
[Boneh, 1996] D. Boneh, C. Dunworth and R.J. Lipton, “Breaking DES using a molecular computer”. Proc. of a DIMACS Workshop, April 4, 1995, Princeton University, volumn 27 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, pp. 37-65, Providence, RI, 1996.
[Boneh, 1996] D. Boneh, C. Dunworth, and R.J. Lipton,”On the Computational Power of DNA”, Discrete Applied Math., Special Issue on Computational Molecular Biology, vol. 71, pp. 79-94, 1996.
[Braich, 1999] R.S. Braich, C. Johnson, P.W.K. Rothemund, D. Hwang, N. Chelyapov and L.M. Adleman, “Solution of a Satisfiability Problem on a Gel-Based DNA Computer”, Proc. 6th Int’l Conf. DNA computation in the Springer-Verlag Lecture Notes in Computer Science series, 1999.
[Cardona, 2005] M. Cardona, M.A. Colomer, J. Conde, J.M. Miret, J. Miró and A. Zaragoza, “Markov chains: Computing limit existence and approximations with DNA”, BioSystems, vol. 81, pp. 261-266, 2005.
[Chang,2003] W.-L. Chang and M. Guo, “Solving the set cover problem and the problem of exact cover by 3-sets in the Adleman-Lipton model”, BioSystems, vol. 72, pp. 263-275, 2003.
[Chang, 2004] W.-L. Chang and M. Guo, “Molecular Solutions for the Subset-Sum Problem on DNA-Based Supercomputing”, BioSystems, vol. 73, pp. 117-130, 2004.
[Feynman, 1960] R.P. Feynman and D. Gilbert, “There’s Plenty of Room at the Bottom”, Eng. Sci. Mag., vol. 23, no. 5, 1960.
[Fu, 1999] B. Fu, R. Beigel, and F.X. Zhou, “An Õ(2n) Volume Molecular Algorithm for Hamiltonian Path”, Biosystems, vol. 52, pp. 217-226, 1999.
[Gasieniec, 2007] L. Gasieniec, C.Y.Li, P. Sant and P.W.H. Wong, “Randomized probe selection algorithm for microarray design”, J. Theoretical Biology, vol. 248, pp. 512-521, 2007.
[Gursaran, 1999] G.S. Gursaran, S. Kanungo, and A.K. Sinha, “Rule-Base Content Verification Using a Digraph-Based Modelling Approach”, Artif. Intell. Eng., vol. 13, pp. 321-336, 1999.
[He, 2003] X. He, W.C. Chu, and H. Yang, “A New Approach to Verify Rule-Based Systems Using Petri Nets”, Inform. Software Tech., vol. 45, pp. 663-669, 2003.
[Guo, 2005] M. Guo, W.-L. Chang, M. Ho, J. Lu and Cao. J., “Is optimal solution of every NP-complete or NP-hard problem determined from its characteristic for DNA-based computing”, BioSystems, vol. 80(1), pp.71-82, 2005.
[Henkel, 2007] C. V. Henkel, T. Bäck, J. N. Kok, G. Rozenberg and H. P. Spaink, ”DNA computing of solutions to knapsack problems”, BioSystems, vol. 88, pp.156-162, 2007.
[Letchford, 2002] A. N. Letchford and A. Lodi,” Primal cutting plane algorithms revisited”, Math. Methods of Oper. Res., vol. 56(1), pp. 67-81, 2002.
[Lin, 2007] C.-H. Lin, H.-P. Cheng, C.-B. Yang and C.-N. Yang, “Solving satisfiability problems using a novel microarray-based DNA computer, BioSystems, vol. 90, pp.242-252, 2007.
[Lipton, 1995] R.J. Lipton, “Using DNA to solve NP-complete problems”, Science, vol. 268, pp. 542-545, 1995.
[Liu, 1996] Q. Liu, Z. Guo, A.E. Condon, R.M. Corn, M. G. Lagally, and L.M. Smith, “A Surface-Based Approach to DNA Computation”, Proc. 2nd Annual Meeting on DNA-Based Computers, American Mathematical Society, 1996.
[Nazareth,1991] Nazareth and M.H. Kennedy, “Verification of Rule-Based Knowledge Using Directed Graphs”, Knowl. Acquisition, vol.3, pp. 339-360, 1991.
[Nazareth, 1993] D.L. Nazareth, “Investigating the Applicability of Petri Nets for Rule-Based System Verification”, IEEE Trans. Knowledge and Data Eng., vol.4, no. 3, pp. 402-415, 1993.
[Nguyen , 1987] T.A. Nguyen, W.A. Perkins, T.J. Laffey, and D. Pecora, “Knowledge Base Verification”, AI Mag., vol.8, no.2, pp. 69-75, 1987.
[Paun, 1998] G. Paun, G. Rozenberg, and A. Salomaa, DNA Computing: New Computing Paradigms. Springer – Verlag, New York, 1998.
[Ramaswamy, 1997] M. Ramaswamy, S. Sarkar, and Y.S. Chen, “Using Directd Hypergraphs to Verify Rule-Based Expert Systems”, IEEE Trans. Knowledge and Data Eng., vol.9, no. 2, pp. 221-236, 1997.
[Roweis, 1998] S. Roweis, E. Winfree, R. Burgoyne, N.V. Chelyapov, M.F. Goodman, P.W.K. Rothemund, and L.M. Adleman, “A Sticker-Based Model for DNA Computing”, J. Compu. Biol., vol. 5, no. 4, pp. 615-629, 1998.
[Valiente, 1993] G..Valiente, “Verification of Knowledge Based Redundancy and Subsumption Using Graph Transformations”, Int’l J. Expert Syst., vol. 6, no. 3, pp.341-355, 1993.
[Wang, 2006] Z. Wang, D. Xiao, W. Li and L. He, “A DNA procedure for solving the shortest path problem”,Appl. Math. Comp., vol. 183, pp. 79-84, 2006.
[Wolsey, 1998] L. A., Wolsey, Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization. pp. 113-129, 1998.
[Xiao, 2005] D. Xiao, W. Li, Z. Zhang and L. He, “Solving maximum cut problems in the Adleman-Lipton model”, BioSystems, vol. 82, pp.203-207, 2005.
[Xiao, 2005] D. Xiao, W. Li, J. Yu, X. Zhang, Z. Zhang and L. He, “Procedures for a dynamical system on {0,1}n with DNA molecules”, BioSystems, vol. 84, pp.207-216, 2006.
[Yang, 2003] S.J.H. Yang, J.P. Tsai, and C.C. Chen, “Fuzzy Rule Base Systems Verification Using High-Level Petri Nets”, IEEE Trans. Knowledge and Data Eng., vol.15, no. 2, pp. 457-473, 2003.
[Yeh, 2006] C.-W. Yeh, C.-P. Chu and K.-R. Wu, “Molecular solutions to the binary integer programming problem based on DNA computation”, BioSystems, Vol. 83, pp.56-66, 2006.
[Yeh, 2008] C.-W. Yeh and C.-P. Chu, ”Molecular verification of rule-based system based on DNA computation”, IEEE Trans. on Knowledge and Data Engineering.