两类生物计算问题及其在数据挖掘中的应用研究

摘要

作为生物计算的新的研究内容，膜计算从生物体的自身运行机制和合作原理，即细胞、组织等结构中获得灵感，设计出P系统。到现在为止，主要的P系统有三大类：cell-like（细胞）P系统，tissue-like（组织）P系统，Spiking Neural（神经）P系统。这些P系统都是从生命体机制，如细胞、组织中概括提取出来的。膜计算的主要研究方向包括：膜系统的计算能力与计算效率，新型膜计算模型，膜计算的应用以及实现。得益于膜计算具有的并行性特点，膜计算已应用到经济学、语言学、生物建模、密码学、计算机图形学等多个领域，解决了许多问题。
　　DNA计算是以生物 DNA为基础的计算，通过 DNA分子的变性、复性退火等操作，在特定环境下，在试管中或表面上或芯片上进行反应，从而得出问题解集的过程。DNA计算具有三个显著优势:(1)高并行性，运算速度快。(2)DNA作为信息的载体，存储容量大。(3)DNA分子生物计算耗能低。研究DNA计算的热门所在，主要为：对于新的DNA模型的发现、分析与研究；能够解决非确定多项式问题的具体的DNA模型；构造基于DNA求解问题的装置并使之自动化等。
　　数据挖掘，是从数据中获取知识和信息的过程。在大数据背景下，针对其出现的新特点，如何对数据进行有效分析，从庞大的信息中发掘可利用的知识，提升数据的有效性和可阅读性，有待数据挖掘研究学者提出合理、可用的方法。聚类分析是一种处理数据（信息）的有用方法或技术。作为数据挖掘极其重要的一部分，聚类有着多种方法，如系统法，动态聚类法，模糊聚类方法等。这些方法各有优缺点，分别在某些特定的情况下取得了理想的聚类效果。论文从基于膜计算的聚类算法和基于DNA计算的聚类算法两个方面进行了研究，主要工作如下：
　　(1)Pǎun曾说：“设计实现新的P系统是膜计算领域的一条重要发展道路”。本文首先对三种主要的膜计算模型进行了扩展，分别提出了基于层结构的膜系统模型，带有动态促进/抑制因子的组织型膜计算模型和具有拓展规则及多输出的脉冲神经模型。在数学图形学、拓扑学中，应用较多的一个理论叫做离散 Morse理论。这一理论能够剖析一些离散图形结构的拓扑类型。将膜系统与新型数据结构(如单纯形、复形等)结合，提出基于格（偏序结构）的交流膜系统，基于单纯形的交流膜系统，并使用形式语言证明其计算完备性。
　　作为一种新型的计算方法，膜计算在聚类分析中的应用并不多。结合膜计算的强大并行能力，本文提出了基于动态促进/抑制因子的组织型膜系统的拓扑聚类算法，使用带有动态促进/抑制因子的组织型膜系统规则实现具体聚类步骤，通过一个包含十个数据点的示例说明了算法实施的可行性，与传统操作方法进行了时间复杂度的比较。将改进的脉冲神经膜计算模型与菱形网格相结合，提出基于拓展规则及多输出的脉冲神经膜系统的网格聚类，给出算法的规则，膜系统结构，通过包含多个数据点的示例说明了算法是管用的。提出基于格（偏序结构）的新型结构交流膜计算模型，设计了上确界和下确界规则，通过规则在膜系统中实现了密度聚类算法，减少了算法的时间复杂度，提供了聚类算法的新思想。本文将所提出的基于膜计算的聚类算法应用于具体问题中，给出了三个方面的应用，包括：膜计算、DNA计算在真实数据集中的应用、膜计算在文本聚类以及在空气质量评估中的应用。
　　(2）使用著名 Adleman模型、改进的粘贴模型以及 K-臂 DNA计算模型进行聚类分析。提出了基于 Adlman-Lipton计算模型的拓扑聚类算法，基于改进的粘贴DNA计算模型的拓扑方法和基于 k-臂即三维 DNA模型的划分方法。分别将 DNA计算与层次聚类，网格聚类等算法相结合。基于 Adlman-Lipton计算模型的拓扑聚类算法，用单链DNA表示顶点和各个顶点之间的边，使用DNA测试分子序列顺序的方法与凝胶电泳方法，两种方法共同作用得到最小生成树，随后，按照一个具体数值（反应之前给定的）删除大于这个数值的边，结果中可连通的顶点的子图数目即聚类的簇的个数。基于改进的粘贴DNA计算模型的拓扑聚类算法中，首先，对于粘贴模型的存储与粘贴链结构、基本操作进行了补充、改进，然后，结合Chamlon算法进行聚类。基于k-臂DNA计算模型的划分聚类算法中，将DNA计算与网格聚类思想相结合，使用网格将二维数据转换到不同的单元格上，设定核心，对每个核心及其连接的顶点进行4-臂DNA编码，在试管中并行产生DNA团，以达到聚类的目的。
　　本文对传统的膜计算模型进行了扩展，并且提出了新型结构膜系统，使用形式语言证明其计算能力，将扩展的膜系统与新型膜系统用于数据挖掘聚类分析中，并通过实验进行了比较分析。使用著名Adleman模型、改进的粘贴模型以及K-臂DNA计算模型进行聚类分析。将上述技术应用到实际问题中。由于膜计算、DNA计算的并行性，在处理数据挖掘任务方面有着极大的潜力，不论在生物信息领域，还是商务智能领域都有着重要意义。

目录

封面

声明

目录

中文摘要

英文摘要

1 绪论

1.1 研究背景和意义

1.2 研究现状及发展趋势

1.3 论文研究内容及组织

2 主要膜计算模型的扩展

2.1 膜计算基本符号、概念及模型

2.2 三种主要的膜计算模型的扩展

3 新型结构膜计算模型研究

3.1 新型结构膜计算模型

3.2 新型结构膜计算模型计算能力证明

4 基于膜计算的聚类算法研究

4.1 基于动态促进/抑制因子的组织型膜系统的拓扑聚类算法

4.2 基于拓展规则及多输出的脉冲神经膜系统的网格聚类算法

4.3 基于格结构交流膜系统的密度聚类算法

5 基于 DNA 计算的聚类算法研究

5.1 DNA 计算模型

5.2 基于 DNA 计算的聚类算法研究

6 基于膜计算、DNA 计算的数据挖掘应用

6.1 膜计算、DNA 计算在真实数据集中的聚类应用

6.2 膜计算在文本聚类中的应用

6.3 膜计算在空气质量评估中的分类应用

7 总结与展望

7.1 总结

7.2 进一步的工作

参考文献

攻博期间发表的科研成果目录

致谢