[科普中國(guó)]-肽運(yùn)算

肽運(yùn)算是一種與傳統(tǒng)的硅基計(jì)算機(jī)技術(shù)不同的，運(yùn)用了多肽-分子生物學(xué)的運(yùn)算形式。

簡(jiǎn)介這種計(jì)算模型是基于抗體在肽序列（氨基酸序列）的鏈接。與DNA運(yùn)算相仿，肽序列與抗體之間的平行相互作用已被利用于這個(gè)模型來(lái)解決一些“NP完備”問(wèn)題。具體來(lái)說(shuō)，現(xiàn)在已經(jīng)運(yùn)用這種計(jì)算模型解決了漢米爾頓路徑問(wèn)題（HPP）和一些版本的集合覆蓋問(wèn)題。這種計(jì)算模型也顯示出自身的具有等用于通用圖靈機(jī)的計(jì)算能力(或者說(shuō)是“圖靈完全”的)。

這種計(jì)算模型比起DNA運(yùn)算有些關(guān)鍵優(yōu)勢(shì)。打個(gè)比方，如果說(shuō)DNA由4塊積木砌成（4種堿基），多肽就用了20塊積木砌成（20種氨基酸）。肽-抗體相互作用也在相互識(shí)別及鏈接上比一條單鏈DNA及其互補(bǔ)鏈更加靈活。但是與DNA運(yùn)算不同的是，這種模型還沒(méi)用實(shí)現(xiàn)現(xiàn)實(shí)中的利用。 主要的限制是該模型所需的單克隆抗體的有效性。1

DNA運(yùn)算DNA運(yùn)算（DNA computing，或譯DNA計(jì)算）是一種電腦運(yùn)算形式，利用DNA、生物化學(xué)以及分子生物學(xué)原理，而非傳統(tǒng)上以硅為基礎(chǔ)的電腦技術(shù)。

DNA運(yùn)算，或更廣泛的說(shuō)，分子運(yùn)算，是一個(gè)新出現(xiàn)的交叉學(xué)門(mén)領(lǐng)域。此領(lǐng)域內(nèi)研究熱點(diǎn)包括理論、實(shí)驗(yàn)和DNA運(yùn)算的應(yīng)用。

DNA運(yùn)算最先由南加州大學(xué)的倫納德·阿德曼在1994年實(shí)現(xiàn)。Adleman演示了一種將DNA應(yīng)用于解決七點(diǎn)哈密頓路徑問(wèn)題的概念驗(yàn)證方法。自Adleman的實(shí)驗(yàn)以后，學(xué)界又取得了許多進(jìn)展，多種圖靈機(jī)被證明是可行的。

盡管一開(kāi)始的研究熱點(diǎn)集中在解決P/NP問(wèn)題，但人們旋即意識(shí)到此類(lèi)問(wèn)題并不是DNA運(yùn)算的最佳應(yīng)用場(chǎng)合，以致有多種意見(jiàn)要求尋找殺手級(jí)應(yīng)用。1997年，計(jì)算機(jī)學(xué)家Mitsunori Ogihara和生物學(xué)家Animesh Ray一道提出了一種組合邏輯電路的評(píng)價(jià)方法，并描繪了實(shí)現(xiàn)方法。2002年，來(lái)自Weizmann Institute of Science的研究者公開(kāi)了一種由DNA分子和酶，而不是硅組成的計(jì)算機(jī)器。2004年3月28日，Weizmann Institute的Ehud Shapiro, Yaakov Benenson, Binyamin Gil, Uri Ben-Dor,和Rivka Adar在自然雜志上發(fā)表文章稱(chēng)，他們實(shí)現(xiàn)了一種整合了輸入輸出的DNA計(jì)算機(jī)，理論上可以實(shí)現(xiàn)細(xì)胞內(nèi)的癌癥診斷，并釋放抗癌藥物。DNA分子由四種堿基組成，通過(guò)酶改變他們的排列可以進(jìn)行計(jì)算。近日，英國(guó)科學(xué)家成功的在一小團(tuán)DNA中存儲(chǔ)了大量文件，并成功讀取。2

集合覆蓋問(wèn)題集合覆蓋問(wèn)題（Set covering problem，SCP）是組合數(shù)學(xué)、計(jì)算機(jī)科學(xué)和計(jì)算復(fù)雜性理論中的一個(gè)經(jīng)典問(wèn)題。

集合覆蓋的決定性問(wèn)題是卡普的二十一個(gè)NP-完全問(wèn)題之一。1

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)