基于组合约束和热力学约束的DNA计算核酸序列设计研究

本课题主要研究DNA计算中核酸分子的编码问题，该问题是生物分子计算、分子自组装、DNA矩阵、DNA芯片等研究领域的重点和难点。目前的DNA编码算法集成的约束条件有限，不能普遍适用于各类生化实验；在约束严格的情况下生成的DNA分子数量较少，无法用于求解较大规模的NP完全问题的实例。本项目拟克服上述不足，设计满足各种组合约束和热力学约束的DNA编码算法。拟重点研究内容有：(1)建立新型DNA序列编码算法模型，利用整型规划将生物约束转换为数学约束，并通过剪枝策略高效搜索解空间，产生满足约束的最大的DNA序列集合。(2)构建基于Nearest Neighbor的最小自由能及二级结构预测模型，提高DNA计算的可靠性。(3)建立求解TSP问题的DNA计算模型，通过生化实验验证DNA分子的有效性。该研究将提高DNA计算可求解问题的规模，并为纳米结构设计、分子标记等其它工程应用提供可靠的理论和技术支持。

核酸分子已被广泛使用于各种工程应用，如DNA计算，DNA分子自组装，DNA纳米结构设计等。高质量的DNA编码可以避免DNA分子间的非特异性杂交，提高DNA计算的有效性和可靠性，因此核酸序列设计具有非常重要的作用和意义。本项目围绕设计满足组合约束和热力学约束的核酸分子展开研究，取得了一些有价值的进展。(1)提出了隐枚举核酸序列设计算法，通过将组合约束和热力学编码约束转换为整数线性规划的条件不等式，巧妙地产生并评价候选DNA序列。算法通过剪枝策略高效的搜索4的n次方的DNA编码解空间，找出满足约束条件的最大的DNA序列集合。通过和其它经典算法的比较，证明了算法的有效性和可靠性。(2)针对DNA分子伪结结构预测的难点，提出了一种基于遗传算法的DNA二级结构预测方法，该算法利用连续碱基堆栈选取优化结构，采用最小自由能作为适应度函数。针对算法特点设计了交叉算子和变异算子产生新的种群个体。为了证明算法的有效性，通过跟RNA Structure等经典预测软件进行对比，证明了本算法的有效性，可计算得到比RNA Structure连续互补碱基对更多，自由能更稳定的DNA伪结结构。(3)项目组了构建基于Nearest Neighbor的最小自由能及二级结构预测模型，提出一种动态规划回溯树搜索策略，改进了传统动态规划二级结构预测算法，有效减低算法时间和空间复杂度，如果满足最小自由能的二级结构不唯一，可以找到自由能相等的所有结构。因此，能够有效预测碱基数量多的长链DNA分子的二级结构。项目组主要成果包括，发表论文20 篇（其中SCI 国际期刊论文12 篇），已出版学术专著1部，获得软件著作权2项，申请国家发明专利2项，培养硕士研究生3 名，达到了预期的研究目标。