Adleman1994 年在Science 上发表的文章“Molecular Computation of Solutions to Combinatorial Problems”,成功地用DNA 计算方法求解有向图的Hamilton有向路问题,标志着一个全新的研究领域——DNA计算的随之产生。由于DNA计算机具有的巨并行性、海量存储以及低能耗等特点,该领域的研究引起了众多学者的关注。本文结合生物学的研究方法和实验技术,对DNA 计算及其模型生物实现过程中的编码问题做了初步地探讨,并就DNA计算中的简单0-1 规划问题和排课表问题进行了初步研究。在DNA 计算中,信息是以DNA 序列为载体并通过DNA 分子间的特异性杂交来完成信息的处理的,因此,DNA 计算首要的问题就是DNA编码问题。由于DNA计算编码问题实质上属于NP 问题,目前的编码方法还无法很好地满足特定DNA计算模型的实际要求。本文在对DNA 计算中编码问题的产生背景和主要研究进展做了简单介绍,并进一步综合分子生物学实验涉及到DNA 设计基本原则的基础上,提出利用计算机辅助生物软件来对DNA编码链进行验证。结合对一DNA计算模型的DNA编码链的理论及实验结果验证,表明该方法对DNA编码验证是可行的。DNA 计算离不开生物反应,并且在很大程度上依赖于生物技术的发展,而代表生物技术前沿技术的生物芯片技术,其在对信息的处理和DNA 计算上有诸多相似之处。本文用DNA计算解决规划问题的研究中,对0-1 规划问题分别给出了基于溶液计算、表面计算和溶液表面结合计算的三类DNA 计算模型,分别强调了溶液计算的高度并行和高存储性,表面计算的高自动化程度等优点,并进一步利用溶液与表面计算相结合的方法来避免各自的缺点,突出其优点,生物实验对溶液与表面计算相结合的模型进行了验证。另外,我们指出生物芯片技术可以被用于构建DNA计算的芯片,而可能解决更复杂的规划问题的DNA 计算模型,将是溶液与表面计算、常规和先进生物技术结合的产物。对于DNA计算而言,其关注的焦点在于能否解决现实中的难计算问题。目前研究者逐渐意识到,除非可以获得极大的反应规模,否则理论上仅仅通过增加反应规模来增强计算能力并无助于DNA 计算的进一步发展。基于此原因,我们利用两项生物技术:Acrydite~TM 凝胶技术和缩微实验室技术(Lab-on-chip),首次在理论上构建了解决简单排课表问题的DNA 计算模型,尽管其在运算规模上还无法达到大容积溶液计算的高并行性和高存储量,但两类模型都具有自动化,微型和高通量分析的特征。我们认为通过将前沿的生物技术和计算的新形式的相互结合,在一定程度上对并行性和可行性进行取舍,探索构建杂交型的微型DNA计算机将有助于DNA