生物分子的大小在纳米尺度，同时具有良好的可操作性和强大的信号转导能力，这为利用生物分子元件组装生物计算机的研究提供了可能。在生物计算领域，DNA计算从1994年Adleman博士成功采用生化试验解决了7顶点Hamilton问题以来，DNA计算的发展就引起了广泛的关注。DNA计算采用DNA链作为信息载体，将原始问题映射成DNA编码，采用生物酶为计算工具，分子水平的生化操作为计算方法，于生物实验室进行一些列操作而求解问题。DNA计算发展近20年来，诸多数学、生物、纳米科学和信息科学的科研人员都投身与这一领域。从目前来看，DNA计算在优化计算、信息安全，特别在求解组合优化问题中的NP问题上具有一种“天然”优势，同时无论在理论模型还是实践水平上，DNA计算都取得了很大的进展与突破，但其本身仍未成熟，仍然存在诸多理论问题和实际问题亟待解决，尤其是生物实验水平没有规范化和成熟，DNA模型的构建和使用由于其自身结构的限制而不能非常灵活。本文致力于对k-臂DNA分子模型的研究，在理论上完善该模型与发夹模型的关系，用以解决NP问题，具有十分重要的现实意义。本文的主要研究工作如下：第一章在介绍了研究背景和意义之后，从宏观和微观两个角度，采用文献计量学的方法，对DNA计算发展近20年的状况——包括文献计量、核心期刊、核心作者等问题——进行了研究综述，为以后的研究者提供参考。第二章介绍了DNA计算的基础理论知识，重点针对本文要使用的三类基础模型——k-臂分子模型、发夹模型、三链模型进行了阐述，并基于三者自身优势，探索了将其混合使用的可能性。即发夹模型完全可以作为k-臂分子模型的计算控制模型使用，而三链模型则是一种良性的筛选模型，可参与双链结构的筛选过程。为了充分说明DNA计算中编码水平、生物操作水平、模型发展对DNA计算会产生及其重要的推动作用，在第二章的后半部分，以三链模型为基础模型，改进原有编码水平并采用不同于原有读取解的方式，提出了对0-1规划问题的改进算法。第三章在第二章的基础上，讨论了k-臂DNA分子中的一种特殊结构——3-臂DNA分子的特性，其可以直观表达二叉树的结构。因此，本章提出了基于3-臂分子的结构优势，结合发夹模型和三链结构的筛选，求解最近邻层次聚类问题的算法。在算法复杂性分析过程中，可看出k-臂分子在编码规模和操作复杂性上的优势。另外，该算法的提出，也拓展了k-臂DNA分子模型的应用范围，可以用来解决更多基于二叉树进行优化求解的问题。k-臂DNA分子模型具有“天然”的表达图结构的能力，故对于图论问题的求解具有直观上的优势。图论问题中诸多问题是在寻找顶点与边满足一定关系的特殊子图或者集合，k-臂DNA分子与其控制模型——发夹模型结合，就可以有效控制k-臂分子上参与计算的边的数量和限制只有某些边才可以参与计算的实现。在该理论基础上，第四章提出了基于k-臂DNA分子模型求解最大团问题的算法。对一般情况的模拟发现，该算法所需的顶点块空间复杂性为多项式级别，优于O(（√3）n)。另外，引入进化计算的思想，给出算法流程，尝试改进解空间爆炸性问题，通过c++编写进化计算的仿真实验，检验进化计算为解空间爆炸问题的解决的贡献。第五章给出相应的应用实例，对问题进行编码和按照算法操作步骤进行求解，通过实例验证的方式，说明所提出的算法的可行性和有效性。