DNA分子生物特征与生化反应过程的模型化研究

DNA computing is a new computing method, which based on biochemical reaction progresses and some enzymes as basic materials.At the same time, Compting DNA is just a mathematic method forecasting the undiscovered biological infomations through establishing a new mathematic models,and this progress will be bring into effect by using the biological characteristics and its biochemical reaction progresses. At the present time,Watson-Crick automaton is only a simple transmutation of classical automata,which can't explain or solve some special biology problems,neither the complementariness of DNA nor the characteristics of parallel operation also can be represented.Accordingly,in order to solve those problems mentioned of above,it is neccerry to reconstruct some new optimazer mathematic models of DNA computing and realize them through molecular biogical experiments.Bsed on the disciplinarian of biological reaction processes and analyze its molecular characteristics and the rules in the biochemical processes,this project will study the mathematical roperty,computability and computational cmplexity through mathematic models;propose the definition of Watson-Crick complementary automaton,study its mathematical characteristics,forecast its unknown biological characters of DNA and check up these results by the molecular experiments of DNA.The results will provide some theoretical suggestions and support of mathematical models for the rapid computing of NP problem and faster intelligent recognition of specific information in DNA molecular chains.

DNA计算是一种以DNA分子与相关酶作为基本材料、以生化反应过程为基础的新型计算方法，计算DNA则是利用DNA分子生物特征与生化反应过程，通过建立模型预测DNA分子所蕴含的未知生物学信息的数学方法。目前的Watson-Crick自动机只是经典自动机的简单变形，没有体现DNA分子互补性，不具备并行运算特征，不能解释和解决一些特定生物学问题，因此有必要重建一种优化的DNA计算模型，并用DNA分子实验加以实现。本项目通过分析DNA分子特征以及生化反应过程所蕴含的规律，利用数学语言建立表征规律的模型，研究相关模型的数学性质、可计算性与计算复杂性；给出具有Watson-Crick互补性质的自动机定义，研究其数学性质，预测DNA分子所蕴含的未知生物学特征，并通过DNA分子实验加以检验。项目的研究结果将为解决NP问题的快速计算，及DNA分子链中特定信息的快速读取提供理论与数学模型支持。

该项目的研究包括DNA计算和计算DNA两部分内容。DNA 计算是一种以 DNA 分子与一些相关的生物酶作为基本材料、以一些生化反应过程为基础建立新的计算模型，将数学问题的求解与并行DNA操作有效结合，如粘贴模型、插入删除模型、剪接模型等。在项目执行过程中，我们得出8类NP完全问题的DNA快速算法，包括图的最小顶点覆盖问题、图的最小连接问题、旅行商问题、最小权生成树问题、无向图最短路径问题、可满足性问题、求解最大完全子图和最大匹配问题。计算DNA则是用数学理论和方法作为工具来探索DNA分子特征以及DNA分子生化反应所蕴含的规律，并且建立表征DNA规律的新的动力系统模型。研究了基于粘贴系统的 Watson-Crick 正则文法及自动机，DNA正则语言与DNA正则文法的对应关系。