基本介紹
- 中文名：肽運算
- 領域：計算機
簡介,DNA運算,集合覆蓋問題,
簡介
這種計算模型是基於抗體在肽序列（胺基酸序列）的連結。與DNA運算相仿，肽序列與抗體之間的平行相互作用已被利用於這個模型來解決一些“NP完備”問題。具體來說，現在已經運用這種計算模型解決了漢米爾頓路徑問題（HPP）和一些版本的集合覆蓋問題。這種計算模型也顯示出自身的具有等用於通用圖靈機的計算能力(或者說是“圖靈完全”的)。
這種計算模型比起DNA運算有些關鍵優勢。打個比方，如果說DNA由4塊積木砌成（4種鹼基），多肽就用了20塊積木砌成（20種胺基酸）。肽-抗體相互作用也在相互識別及連結上比一條單鏈DNA及其互補鏈更加靈活。但是與DNA運算不同的是，這種模型還沒用實現現實中的利用。 主要的限制是該模型所需的單克隆抗體的有效性。
DNA運算
DNA運算，或更廣泛的說，分子運算，是一個新出現的交叉學門領域。此領域內研究熱點包括理論、實驗和DNA運算的套用。
DNA運算最先由南加州大學的倫納德·阿德曼在1994年實現。Adleman演示了一種將DNA套用於解決七點哈密頓路徑問題的概念驗證方法。自Adleman的實驗以後，學界又取得了許多進展，多種圖靈機被證明是可行的。
儘管一開始的研究熱點集中在解決P/NP問題，但人們旋即意識到此類問題並不是DNA運算的最佳套用場合，以致有多種意見要求尋找殺手級套用。1997年，計算機學家Mitsunori Ogihara和生物學家Animesh Ray一道提出了一種組合邏輯電路的評價方法，並描繪了實現方法。2002年，來自Weizmann Institute of Science的研究者公開了一種由DNA分子和酶，而不是矽組成的計算機器。2004年3月28日，Weizmann Institute的Ehud Shapiro, Yaakov Benenson, Binyamin Gil, Uri Ben-Dor,和Rivka Adar在自然雜誌上發表文章稱，他們實現了一種整合了輸入輸出的DNA計算機，理論上可以實現細胞內的癌症診斷，並釋放抗癌藥物。DNA分子由四種鹼基組成，通過酶改變他們的排列可以進行計算。近日，英國科學家成功的在一小團DNA中存儲了大量檔案，並成功讀取。
集合覆蓋問題
集合覆蓋的決定性問題是卡普的二十一個NP-完全問題之一。
