中文摘要

現代數位計算機可分硬體及軟體兩大應用領域，硬體是以電子電路及數位晶片架構在以布林代數(Boolean Algebra)為數學理論基礎而發展出來的電腦母板及一系列的PC板等應用。軟體的濫觴則是源自於計算理論(Automata Theory) 而有了state, input, output 等概念而發展至現今的視窗程式設計…等領域。
然而我們對電腦速度的追求總是無止盡的，許多的應用(例如氣象預報，或模擬一顆核子彈的爆炸，或在網路上追求更完美、極至的影音表現)或數學上的難題(例如NP-Complete…等問題) 都須要速度更快的電腦。 然而如上所述的傳統由電子電路所造的數位計算機其運算速度幾已達極限，很難再有突破性的五十倍或百倍的速度上的進展。所以我們必須揚棄傳統的思維，而另行思考不一樣的、替代性的計算模式 (Alternative Computing Model)。
在國外，替代性的計算模式 (Alternative Computing Model)已被思考多年， 諸如函數計算(Functional Programming)，或邏輯計算(Logic Programming)，或於1990年由Adleman 博士所提出的 DNA 計算模式 … 等， 本文即是以 DNA 計算模式的思維，對三個傳統難解的NP-Complete 問題， 提出其在DNA 計算模式下的數學演算法，期待隨著DNA 計算模式發展的日趨成熟，藉由其高度的平行運算，快速增進電腦的運算速度， 進而解決在傳統數位計算機上難解的數學問題或實際的應用。
本論文針對三個NP-Complete 的問題( Not-All-Equal 3-SAT問題，One-In-Three 3-SAT 問題，Hitting-set 問題 )，分別提出了DNA 計算模式下的演算法。
日本學者 Junzo Watada 在2008 年的ISDA 國際學術研討會裏發表論文，說到目前 DNA 計算模式的研究有兩個主流，一為致力於發展精確的數學模型，另一則根據正確的數學模型，專心的在奈米級的實驗室裏操作DNA生物指令。 本論文所做的研究是屬於第一流派，發展了三個DNA計算模式下的演算法。

Abstract

This dissertation is to illustrate the current state of the art of DNA computing achievements, especially of new approaches to solve theoretical 3-SAT problems and the hitting-set problem. Beginning with Adleman’s breakthrough which is an molecular algorithm for the solution of a NP-complete, combinatorial problem, the directed Hamiltonian path problem (HPP). Today, many researchers all over the world concentrate on proposing new methods to solve engineering or application problems with a DNA computing approach.
Satisfiability problem is given a Boolean formula, and decide if a satisfying truth assignment exists. ( ) ( ) … ( ) ( ) is an example of Boolean formula. k-SAT problem means that each clause has exactly k literals. Not-All-Equal (NAE) 3-SAT problem and One-In-Three (1IN3) 3-SAT problem are both NP-complete problems. In this dissertation, we present molecular solutions to find all true assignments (3-SAT problem) and furthermore find Not-All-Equal (NAE) solutions and One-In-Three (1IN3) solutions in DNA-based Supercomputing.
Hitting-set problem assume that there exists a collection C of subsets of a finite set S, and a positive integer K  |S|, and we need to know if there is a subset  S with | |  K such that contains at least one element of each subset in C. In other words, is the subset that intersects every subset in C and is called the hitting-set.
In this dissertation, a DNA-based algorithm is proposed to solve the small hitting-set problem. A small hitting-set is a hitting-set with the smallest K value, i.e., the hitting-set with the smallest number of elements. Furthermore, an algorithm is introduced to find the number of ones from 2n combinations and minimum numbers of ones represents the small hitting-set since K is expected to be as small as possible.
The complexity of all the presented DNA-based algorithms is also discussed. We describe time complexity and volume complexity of three Algorithms, numbers of test tube used and the longest library strand in solution space of all three Algorithms.
Finally, the simulated experiment is applied to verify correctness of the proposed DNA-based algorithm for solving the One-In-Three (1IN3) 3-SAT problem, and simulation of Not-All-Equal (NAE) 3-SAT problem is similar. Also, another simulated experiment is applied to our proposed DNA-based algorithm 6-2, in order to solve the well-known hitting-set problem.
This research has been motivated by the benefit and the application of DNA computing and gives new methods to solve two 3-SAT problems and the hitting-set problem which are NP-complete.

References
[1] L. M. Adleman. “Molecular Computation of Solutions to Combinatorial Problems”. Science, 266, pp. 1021-1024, Nov. 11, 1994.
[2] L. M. Adleman, “On constructing a molecular computer”, in DNA-bsed computers, volume 27 of DIMACS
[3] L. M. Adleman, “Computing with DNA”, Scientific American, August, 1998
[4] M. Amos, Theoretical and Experimental DNA Computation. Springer, 2005
[5] 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” in Proceedings of the Sixth International Conference on DNA Computation ( DNA 2000 ), Lecture Notes in Computer Science 2054, pp. 27-42,2001
[6] R. S. Braich, C. Johnson, P.W.K. Rothemund, N. Chelyapov, and L. M. Adleman, 2002. Solution of a 20-variable 3-SAT problem on a DNA computer. Science, vol. 296, No. 5567, 499–502.
[7] R. Brijder, M. Cavaliere, A. Riscos-Núñez, G. Rozenberg, and D. Sburlan 2008. Membrane systems with proteins embedded in membranes. Theoretical Computer Science, 404, 26-39.
[8] J. Bishop and E. Klavins 2007. An improved autonomous DNA nanomotor. Nanoletters, Sep., Vol. 7, No. 9, 2574-2577.
[9] W. L. Chang and M. Guo, ”Solving the clique problem and the vertex cover problem in Adleman-Lipton’s model”, in Proceedings of IASTED International Conference, Networks, Parallel and Distributed Processing, and Applications, pp. 431-436, 2002
[10] W. L. Chang, M. Ho, and M. Guo, "Molecular Solutions for the Subset-sum Problem on DNA-based Supercomputing", BioSystems (Elsevier Science), Vol. 73, No. 2, 2004, pp. 117-130.
[11] W. L. Chang, M. Guo, and M. Ho, "Towards solution of the set-splitting problem on gel-based DNA computing", Future Generation Computer Systems, Volume: 20, Issue: 5, June 15, 2004, pp. 875-885.
[12] W. L. Chang, M. Guo and J. Cao, "Using Sticker to Solve the 3-Dimensional Matching Problem in Molecular Supercomputers", International Journal of High Performance Computing and Networking, 2004, Vol. 1, No.1/2/3 pp. 128 - 139.
[13] W. L. Chang, M. Guo, and J. Wu, “ Solving the Independent-set Problem in a DNA-based Super Computer Model “, Parallel Processing Letters, Vol. 15, No. 4 (2005) 469-479.
[14] W. L. Chang, M. Ho, M. Guo, C. Liu, “Fast Parallel Bio-molecular Solutions: the Set-basis Problem”, International Journal of Computational Science and Engineering, Volume 2, Number 1-2, 2006, pp. 72 – 80.
[15] W. L.Chang, “Fast Parallel DNA-based Algorithms for Molecular Computation: the Set-Partition Problem”, IEEE Transactions on Nanobioscience, Vol. 6, No. 1, 2007, pp 346 - 353.
[16] H. Chen, A. Goel, and C. Luhrs 2008. Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. ACM-SIAM Symposium on Discrete Algorithms (SODA) 409-418.
[17] M. Cook, P. W. K. Rothemund and E. Winfree Self-assembled circuit patterns. 2004. DNA Computers 9, LNCS v. 2943, 91-107.
[18] R. P. Feynman, “In Minaturization”. D.H. Gilbert, Ed., Reinhold Publishing Corporation, New York, 1961, pp. 282-296.
[19] M.R. Garey and D.S. Johnson (1979), “ Computers and Intractability A Guide to the Theory of NP-Completeness“, San Francisco, CA
[20] R. P. Goodman, I. A. T. Schaap, C. F. Tardin, C. M. Erben, R.M. Berry, C. F. Schmidt and A. J. Turberfield 2005. Rapid chiral assembly of rigid DNA building blocks for molecular nanofabrication. Science 310, 1661-1665.
[21] S.Y. Hsieh, C.W. Huang and H.H. Chou, “A DNA-based graph encoding scheme with its applications to graph isomorphism problems “, Applied Mathematics and Computation, Volume 203, Issue 2, 15 September 2008, Pages 502-512
[22] R. J. Lipton. “DNA Solution of Hard Computational Problems”. Science, 268, pp. 542-545, 1995.
[23] U. Majumder, J. H. Reif, and S. Sahu 2008. Stochastic analysis of reversible self-assembly. Journal of Computational and Theoretical Nanoscience, Volume 5, Number 7, 1289-1305.
[24] P. O'Neill, P.W.K. Rothemund, A. Kumar and D. K. Fygenson 2006. Sturdier DNA Nanotubes via Ligation. Nano Letters, 6:1379-1381.
[25] S. Roweis, E. Winfree, R. Burgoyne, N.V. Chelyapov, M.F. Goodman, P.W.K. Rothemund, L.M. Adleman, 1999. A sticker based model for dna computation. In: Landweber, L., Baum, E. (Eds.), Second Annual Workshop on DNA Computing, Princeton University. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp. 1–29.
[26] K. Suzuki and S. Murata 2007. Design of DNA spike oscillator. Unconventional Computing, 163-175.
[27] R. Yashin, R. Rudchenko, and M. N. Stojanovic 2007. Networking particles over distance using oligonucleotide-based devices. Journal of the American Chemical Society, 129 (50), 15581 -15584.
[28] P. Yin, H. M. T. Choi, C. R. Calvert and N.A. Pierce 2008. Programming biomolecular self-assembly pathways. Nature, 2008, 451: 318-322.
[29] D. Y. Zhang and E. Winfree Dynamic allosteric control of noncovalent DNA catalysis reactions. J. Am. Chem. Soc., 130 (42), 13921–13926.
[30] L. Kari, “From micro-soft to bio-soft: Computing with DNA”, Biocputing and emergent computation: Proceedings of BCEC97, World Scientific 1997, Skovde, Sweden, 1997, pp. 146-164.
[31] J. Watada and R. B. A. Bakar, “DNA Computing and Its Applications”, Eighth International Conference on Intelligent Systems Design and Applications, pp.288-294
[32] S. Zhou, Q. Zhang, J. Zhao and J. Li, Optimization of DNA Encodings Based on Free Energy, ICIC Express Letters, vol.1, no.1, pp.33-37, 2007.
[33] J. Li, Q. Zhang, R. Li and S. Zhou, Optimization of DNA Encoding Based on Combinatorial Constraints, ICIC Express Letters, vol.2, no.1, pp.81-88, 2008.
[34] Rohani Binti Abu Bakar, Junzo Watada and Witold Pedrycz, A Proximity Approach to DNA Based Clustering Analysis, International Journal of Innovative Computing, Information and Control, vol.4, no.5, pp.1203-1212, 2008.
[35] Tadahiro Kin, Ken-ichi Makino, Nobuo Noda, Kazuharu Koide and Masahiro Nakano, The Molecular Dynamics Calculation of Clathrate Hydrate Structure Stability for Innovative Organ Preservation Method, International Journal of Innovative Computing, Information and Control, vol.4, no.2, pp.249-254, 2008.
[36] D. Rooss, “Recent Developments in DNA-Computing”, Proceedings of the International Symposium on Multiple-Valued Logic, 1997, pp. 3-9