肽运算

肽运算是一种与传统的硅基计算机技术不同的，运用了多肽-分子生物学的运算形式。

简介这种计算模型是基于抗体在肽序列（氨基酸序列）的链接。与DNA运算相仿，肽序列与抗体之间的平行相互作用已被利用于这个模型来解决一些“NP完备”问题。具体来说，现在已经运用这种计算模型解决了汉米尔顿路径问题（HPP）和一些版本的集合覆盖问题。这种计算模型也显示出自身的具有等用于通用图灵机的计算能力(或者说是“图灵完全”的)。

这种计算模型比起DNA运算有些关键优势。打个比方，如果说DNA由4块积木砌成（4种碱基），多肽就用了20块积木砌成（20种氨基酸）。肽-抗体相互作用也在相互识别及链接上比一条单链DNA及其互补链更加灵活。但是与DNA运算不同的是，这种模型还没用实现现实中的利用。 主要的限制是该模型所需的单克隆抗体的有效性。1

DNA运算DNA运算（DNA computing，或译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中存储了大量文件，并成功读取。2

集合覆盖问题集合覆盖问题（Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。

集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。1

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学