DNA計算之研究

Abstract

Leonard M. Adleman 於1994年提出一個生物實驗：利用DNA來解決有方 向性的Hamiltonian路徑問題(此問題為NP-complete)。他利用對DNA進行 編碼，以及現今生物技術中對於DNA的實驗操作，經由試管成功的解決此 問題，並證明其時間複雜度與輸入資料呈線性關係。由於在DNA計算模式 下，每個DNA分子就像是一個處理器(processor)，而一莫耳(mole)溶液中 就有6.02x10^23個分子，因此我們可以很輕易地達到10^20以上的平行處 理能力；相較於傳統的計算模式，DNA的計算模式在平行處理能力上，提 供非常大的潛力。 在這篇論文中，我們針對兩個最佳化問題( optimization problem)：推銷員旅行問題(traveling-salesman problem)和0-1整數規劃(0-1 integer programming)，設計出兩個DNA計 算模式下的演算法。 In 1994, Leonard M. Adleman used biological experiments with DNA strands to solve the directed Hamiltonian path problem, which is considered to be intractable because of its NP- completeness. The idea is to use strands of DNA to encode the problem and to manipulate them using techniques commonly available in any molecular biology laboratory. The potential benefits of using this particular molecule are enormous due to the massive inherent parallelism of performing concurrent operations on trillions of stran In this thesis, We proposed two different DNA algorithms solving the traveling-salesman problem and the 0-1 integer programming respectively. Both of them are NP-hard optimization problems.