蛋白质网络模体发现算法及其在关键蛋白质识别中的应用

摘要

随着高通量蛋白质组技术的快速发展，大量的蛋白质网络数据被收集整理在多个公开的数据库中，如何从这些大规模的蛋白质网络中识别出与功能相关的子结构是当前计算生物学的研究热点之一。网络模体代表着蛋白质网络中的进化保守拓扑单元，研究网络模体有助于理解蛋白质网络的结构、功能以及进化设计原理，同时为系统认识细胞内生命活动的内在组织及其过程提供有效方法。
　　网络模体发现的过程涉及到子图搜索和图同构两大计算难题，模体的查找时间随着网络和模体规模的增大呈指数级增长，从而使其适用性受到限制。因此研究高效、可扩展性的模体发现算法具有重要的理论意义和应用价值。另一方面，从模体的生物意义角度出发，如何有效地去除生物网络中的噪声数据使查找出的模体更具有生物显著性也是当前存在的问题之一。
　　本文以真实的蛋白质网络作为研究对象，分别从计算角度和生物角度研究了两种类型的网络模体发现问题，即结构网络模体和生物网络模体。对于结构网络模体，考虑到高通量实验所得到的蛋白质网络数据存在假阴性和假阳性的特点，故以非导出子图的方式来查找，而对于生物网络模体，由于在查找子图之前原网络经过了去噪预处理，则以导出子图的方式来查找。此外，考虑到关键蛋白质与网络模体之间可能具有的内在联系，本文最后开展了以网络模体为中心的关键蛋白质的识别研究，主要研究工作如下：
　　（1）鉴于任何非树型连通子图可以通过相应的树型子图进行边的扩展而得到，将整个子图的查找过程分成树型子图查找与非树型子图查找两个步骤进行。首先对于树型子图，提出了一种基于整数组合的子树枚举和统计算法。该算法利用整数的组合操作设计一种有效的子树枚举算法，并通过在子树枚举的过程中同时搜索一个根树的方式来有效减少子树同构的判断数目，此外，通过把所查找子树的规范化标记存储在内存中的方法来简化子树的计数方式。最后，在查找出的树型子图的基础上，通过深度优先搜索扩展树的层次结构进行非树型子图的查找。实验结果表明，相比于现存算法，本文所提方法在运行时间上具有较明显的性能加速。
　　（2）为了去除模体发现过程中图同构的判断，提出了一种基于组合技术的子树统计算法。该算法采用组合技术来直接计算每种同构模式的数目，而不需要完整枚举出子树，从而避免了图同构的测试。而且，根据不同子树拥有相同子结构的特点，实现从一个子结构统计多种子树的同构模式数目的方式，可以减少子结构的重复搜索。最后，本文利用循环门排序“revolving door ordering”算法来有效地生成顶点的组合以实现子结构的枚举。实验结果表明，相比于现存算法，本文所提算法在运行时间上至少快一个数量级。
　　（3）从模体的生物显著性角度，提出了一种有效的算法用于生物网络模体的发现。该算法通过整合边聚集系数和GO短语的语义相似性来综合评估相互作用的生物显著性，然后根据该值的大小去掉生物上非显著性的边来减少查询的子图数目，以增加生物网络模体的发现比例。本文所提算法在拓扑属性和生物功能两方面得到了一个较好的融合，有效地克服了生物网络中的假阳性数据，使查找到的子图在复合物与功能模块中都具有较高的比例。同样，所提算法也适用于传统结构网络模体的发现。
　　（4）考虑到网络模体是蛋白质网络中的进化保守拓扑单元，且有研究指出，相比于非关键蛋白质，关键蛋白质在进化上是更加保守的，以此为理论基础，提出了一种新的基于网络模体扩展的子图密度的关键蛋白质识别算法。该算法依据每个蛋白质所参与的所有模体的扩展子图的密度之和作为衡量蛋白质的关键性指标。进一步，针对蛋白质网络中存在一定的假阳性信息，首先利用边聚集系数对网络进行预处理，然后再结合模体扩展的算法在预处理后的网络中识别关键蛋白质。实验结果表明，本文所提的两个方法预测的关键蛋白质数量均要高于传统拓扑特征的方法的预测结果。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 本文主要工作及贡献

1.4 论文组织结构

第2章 图论相关基础与网络模体发现基本问题

2.1 图论相关基础

2.2 网络模体的定义

2.3 本章小结

第3章 基于整数组合和模式增长的模体发现算法

3.1 引言

3.2 相关工作

3.3 基于整数组合的子树枚举和统计算法

3.4 基于模式增长的非树型子图的查找

3.5 实验及结果分析

3.6 本章小结

第4章 基于组合技术的子树枚举和统计算法

4.1 引言

4.2 相关工作

4.3 基于组合技术的子树枚举和统计算法

4.4 实验及结果分析

4.5 本章小结

第5章 整合拓扑属性和功能信息的生物模体识别算法

5.1 引言

5.2 相关工作

5.3 整合拓扑属性和功能信息的生物网络模体识别算法

5.4 实验及结果分析

5.5 本章小结

第6章 基于模体扩展和边聚集系数的关键蛋白质识别算法

6.1 引言

6.2 相关工作

6.3 模体扩展模型

6.4 关键蛋白质识别算法ME

6.5 关键蛋白质识别算法ME-ECC

6.6 实验及结果分析

6.7 本章小结

结论

参考文献

附录A 攻读学位期间所发表的科研成果

附录B 攻读学位期间所参加的科研项目

致谢