基于图论方法的DNA序列编码研究

项目名称： 基于图论方法的DNA序列编码研究

项目编号： No.61672051

项目类型： 面上项目

立项/批准年度： 2017

项目学科： 计算机科学学科

项目作者： 朱恩强

作者单位： 北京大学

项目金额： 32万元

中文摘要： 在基因工程，特别是生物计算机的研制过程中，DNA编码理论和设计方法是关键。特异性杂交和解链温度，特别是链短且编码序列多这一矛盾的需求，使得DNA编码设计非常困难，并已被证明是NP-完全的问题。编码问题旨在寻找满足不与自身或其补序列互相交叉杂交的最大的DNA单链的集合，可以描述成一个组合优化问题。 因此，本项目拟有机地将DNA编码与图论方法，包括图的独立集理论，图着色理论，图的连通性理论等结合，力争建立一套完整的精准的DNA编码体系。本项目的研究内容主要分为以下4个方面： (1) 提出杂交距离的方法用来衡量DNA序列之间的相似度；(2) 将编码问题转化成图的独立集问题来寻找满足不同约束条件下的最大编码集合；(3) 设计在编码长度，GC含量，杂交距离，值和特异性杂交这五种约束条件下的DNA编码方法；(4) 研发编码相应的软件并给出应用。

中文关键词： DNA计算；码字设计；约束条件；图论；优化算法

英文摘要： DNA sequence encoding and design are critical to genetic engineering, especially to the development of bio-computer. Restricted by specific hybridization and the melting temperature, particularly by the contradiction of short length of DNA strands and simultaneously large number of encoded sequences, DNA encoding problem turns out to be NP-complete. This problem calls for finding largest sets of single DNA strands that do not crosshybridize to themselves or to their complements, which can be formulated as a combinatorial optimization problem. As a consequence, this project will combine the encoding problem with techniques in graph theory, including maximum independent set, graph coloring, graph connectivity, and so on, aiming at establishing a set of accurate DNA encoding system. Specifically, this research will be carried out from the following 4 aspects: (1) propose a new method, called hybridization distance, for measuring the similarity between two DNA sequences; (2) transform the DNA encoding problem into maximum independent set problem to find largest sets of DNA strands under various constraints; (3) design the algorithm of DNA encoding based on five DNA kinds of constraints, viz., the length of DNA strands, GC content, hybridization distance, Tm value and specific hybridization; (4) realize the encoding algorithm by designing corresponding softwares, and show the applications of the encoding designed.

英文关键词： DNA Computing;coding design;constraint ;graph theory;optimization algorithms