1.3 生物計算的研究意義與進展
從1994年至今，DNA計算的研究已有三十年的歷史。這些年來，DNA計算主要用于求解NP完全問題、研發DNA計算機。另外，從DNA計算的研究過程中衍生出來的DNA分子自組裝技術，促進了DNA納米器件領域的研究，為用于腫瘤診斷與藥物遞呈的納米機器人的研發提供了條件。
在生物計算研究領域內，DNA計算異軍突起的主要原因是：目前對DNA分子及相關生化技術的操控比RNA和蛋白質容易實現，且DNA計算具有如下四大優勢[4-8]。
（1）并行性高。DNA計算中的“數據”是DNA分子，數據間的“運算”是雙鏈DNA（double-stranded DNA，dsDNA）的解鏈、單鏈DNA（single-stranded DNA，ssDNA）的連接和切割等基本運算，這些基本運算可并行處理。特別是DNA分子的海量性，使得DNA計算的并行性極高。
（2）信息存儲量巨大。由于組成DNA分子的4個堿基（A、C、G、T，詳見3.1.1小節）的平均長度僅為0.34nm，按每條DNA序列有1000bp[1]計算，長度也僅有340nm。可以粗略地估計，1m3DNA可存儲1萬億億個二進制數據，遠超當前全球所有電子計算機的總存儲量。
[1] 堿基對（base pair，bp）是核酸分子的雙螺旋結構中，一條鏈上的堿基與另一條鏈上的堿基之間通過氫鍵形成的一種化學結構，常用作表征DNA或雙鏈RNA長度的單位，如千堿基對（kbp）和兆堿基對（Mbp）。
（3）能耗極低。粗略估計，DNA計算求解一個問題所消耗的能量僅為一臺電子計算機完成同樣計算所消耗能量的十億分之一。
（4）算子豐富。DNA計算中的算子眾多，如dsDNA分子的解鏈運算、兩個ssDNA之間的連接運算、將一個DNA分子切割成兩個或多個的切割運算、DNA鏈的復制運算（聚合酶）等。此外，還包括已有生化儀器的運算，如PCR擴增運算等。
DNA計算的上述優勢吸引了不同領域（如生物工程、計算機科學、數學、物理、化學、控制科學等）的許多研究人員開展相關研究。
DNA計算的研究目標是研發出實用的DNA計算機。研究進展顯示，DNA計算距實用化越來越近。例如，在搜索一個賦權圖中兩個頂點間的所有路徑時，只需要將這兩個頂點所代表的DNA鏈作為引物，實施一次PCR擴增運算，即可獲得所有路徑。又如，倫納德·阿德曼（Leonard M.Adleman）組在2002年求解可滿足性（Satisfiability，SAT）問題時，搜索次數是220次[10]。文獻[11]建立了求解圖頂點著色問題的DNA計算模型，給出了61個頂點3-著色的所有解，搜索次數已達359次，這是截至本書成稿之日生物計算中搜索規模最大的實例，此例也證明了DNA計算的巨大潛力。
NP完全問題有很多，但斯蒂芬·阿瑟·庫克（Stephen Arthur Cook）在1971年證明了所有NP完全問題在多項式時間內均可相互歸約（Cook憑此項證明于1982年獲得圖靈獎）。這就意味著，所有的NP完全問題均可轉化為圖著色這個典型的NP完全問題。而DNA計算在求解圖著色問題的進展已凸顯出它在求解NP完全問題上的優勢，為求解NP完全問題提供了新思路。NP完全問題的每一點進步，都會給當今社會發展帶來不可估量的貢獻。例如，蛋白質結構預測、列車調度、航跡規劃等NP完全問題有望取得突破，基礎科學領域（特別是數學、運籌學與理論計算機科學）中的一些難題有望得到解決。
按模型特點的不同，DNA計算的研究可分如下4個方向。
（1）枚舉型DNA計算模型（1994—2005年）。DNA計算處于起步階段，許多工作處于探索期。該方向主要針對一些困難的NP完全問題，研究如何基于DNA分子的特性構建計算模型，怎樣對DNA鏈進行編碼；如何進行生化實驗，如何實施解的檢測[怎樣把問題的解從生物化學反應（簡稱生化反應）池中找出來]等。因此，在這段時間，絕大多數研究人員誤以為DNA計算可利用DNA分子的微小性，以空間換時間。枚舉型DNA計算模型將在第6章介紹。
（2）非枚舉型圖頂點著色DNA計算模型（始于2006年）。很容易算出，若用枚舉型DNA計算模型求解200個頂點的4-著色問題，所需的DNA分子質量比地球質量還大。因此，DNA計算必須走非枚舉型之路。作者團隊首先提出非枚舉型DNA計算模型，相關研究將在第7章詳細介紹。
（3）并行型圖頂點著色DNA計算模型（簡稱并行DNA計算模型）（始于2007年）。在非枚舉型DNA計算模型的基礎上，作者團隊于2007年提出并行DNA計算模型。該模型的創新點在于并行性：將一個給定的圖劃分為若干個子圖，并求出每個子圖的著色；在求解每個子圖著色的過程中，給出一種并行PCR連續刪除非可行解（簡稱非解）技術；最后，將所有子圖解連接起來，采用類似刪除子圖的非可行解法，刪除整圖中其余非可行解。并行DNA計算模型將在第8章詳細介紹。
（4）探針機（始于2002年）。在建立圖頂點著色DNA計算模型時，作者團隊發現了一種僅通過一次運算就可獲得一個圖的全部k-色圖的方法，并由此提出了一種全并行的新型DNA計算模型——探針機。探針機相關研究及應用將在第9章簡要介紹。