论文部分内容阅读
随着生物技术的发展,产生了大量的生物网络数据。研究者发现,此类网络中除了具有一些固有的全局属性,如“小世界”和“无标度”等之外,还具有一些能够表征特定功能的拓扑频繁结构,即模体。所谓模体,是指在某个网络的多个不同部分出现的某一相互连接的子结构,其表达程度明显高于在随机网络中的表达。如何从这些生物网络数据中发现此类具有特定生物功能的拓扑结构已成为生物信息学的一个研究热点。实验表明,生物模体的识别有助于研究生物网络的功能模块结构和生物体的进化过程。目前针对生物模体研究,已经取得一定进展,不过主要是针对确定图数据,即边或顶点存在与否是确定的。但在实践中,研究得到的生物网络数据往往带有不可避免的实验误差或者噪声数据,另外,生物进化过程本身也是一个动态变化的过程。因此,概率模体更能体现生物体进化的动态过程和生物网络功能模块的特殊意义。 概率频繁模式的识别是生物网络模体识别中的关键一步,在目前已有的研究工作中,主要采用可能世界模型,即将每个概率子图映射成2n(设n为概率子图的边数)个可能的图实例。这样随着概率模体规模增大,其枚举的可能世界图实例空间规模将急剧增加,算法复杂度指数级增长。 因此,本论文的主要工作如下: 提出一种基于电路模拟法的概率同构判断方法。该方法简化了概率子图转化成其蕴含的确定图的过程,避免使用传统算法采用的可能世界模型,创新性地将子图同构的拓扑比对转化成节点电压序列的比较,进而判定两图的概率同构; 采用星形比对和聚类算法解决概率多图同构计算。概率同构判定问题涉及较多矩阵运算,且概率同构有别于确定图同构,其概率同构与否受阈值限定。为解决任意子图两两判定方法复杂度高过高的问题,本文提出基于聚类的概率多图同构算法有效地降低了计算复杂度。 在上述研究的基础上,设计并实现了概率频繁子图识别算法,并通过实验总结得到概率同构阈值的有效取值范围。实验结果证明,概率频繁模式识别在确定图数据集上能够得到与确定图同构算法一致的结果,并且能在概率图集上识别得到相应规模的概率模体。