基于PPI的蛋白质复合物发现算法的研究

摘要

蛋白质复合物是由多个蛋白质相互结合在一起的组织。生命活动由这些复合物来推动，因此研究蛋白质复合物的具体作用在生物领域具有非常重要的意义。然而，目前的生命科学领域在对这些复合物的识别需要相当大的时间成本和机器成本。由于现在拥有丰富的蛋白质相互作用网络，复合物可以看成是该网络上的社区。在相互作用网络上使用数据挖掘中社区发现的一些算法能够辅助识别这些复合物，以达到减少成本的目的。因此，基于蛋白质相互作用网络的复合物识别是一项有意义的研究课题。
　　现有的蛋白质复合物识别算法一般基于图的网络拓扑结构，结合子图挖掘或者特征学习等数据挖掘方法来识别这些复合物。但是这些算法往往很难完全考虑到蛋白质复合物的复杂性。有些算法只能考虑图密集区域的复合物而忽视稀疏区域的复合物，有些算法容易遗失部分复合物中的蛋白质或者产生冗余的蛋白质。因此，本文基于前人研究的这些缺陷，提出了两个更有效识别蛋白质复合物的算法:
　　第一个算法基于基本的寻找初始聚类再向外扩张的思想。为了得到有效的初始聚类，基于重启型随机游走能够得到一个网络图中所有节点之间的相关联程度，本算法将那些与某个节点联系紧密的节点组合成一个初始聚类，并对这些初始聚类进行去冗余操作形成真正的初始聚类。然后从这些初始聚类出发向外扩张成最后的复合物。在这个过程中，为了解决蛋白质复合物中的某些特殊边缘蛋白质，本文结合其他扩张公式的优缺点，提出新的容易控制聚类大小的有益密度扩张公式比较方法。同时在扩张后的复合物基础上，过于相似的会合并在一起，但是会保留某些特殊的复合物。
　　第二个算法同样基于初始聚类扩张的思想，基于重启型随机游走的结果，通过特定阈值的设计形成有一定规模的初始聚类，本算法认为某些区域内的最大的初始聚类一定程度上可视为这一部分的中心区域，将其他有相似节点的初始聚类都删去作为去冗余操作。最终得到一些互相正交的有代表性的真正初始聚类。在此过程中会产生很多剩余节点。由于重启型随机游走的结果节点之间的关联程度是一定的，因此可以根据这些剩余节点到真正初始聚类内所有节点的平均关联程度的大小来分配这些剩余节点以得到最终的复合物结果。
　　实验在几个著名的酵母细菌蛋白质相互作用网络上进行，本文提出的两个算法都表现出了较好的复合物识别能力。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 蛋白质相互作用网络和蛋白质复合物

1．3 研究现状

1．3．1 小团簇渗透方法

1．3．2 寻找seed再扩张方法

1．3．3 基于模糊聚类的算法

1．3．4 基于图的随机游走的方法

1．3．5 基于有监督的聚类方法

1．3．6 研究现状小结

1．4 论文主要研究内容

1．5 本文组织结构

2．1 相关定义

2．2 研究思路介绍

2．2．1 seed聚类的寻找思路

2．2．2 扩张方法的思路介绍

2．3 本章小结

第三章 基于重启型随机游走的一般seed扩张算法

3．1 引言

3．2 算法描述

3．2．1 基于重启型随机游走的重复seed选取方法

3．2．2 基于可收缩的密度公式比较方法的扩张过程

3．2．3 后续合并处理

3．3 本章小结

4．1 引言

4．2 算法描述

4．2．1 基于重启型随机游走的互不相交的seed生成

4．2．2 剩余节点分配方法

4．2．3 整体框架

4．3 本章小结

5．1 实验数据

5．2 实验工具和方法

5．3 比较方法介绍和评测方法

5．3．1 比较方法介绍

5．3．2 评价方法

5．4 GRWC算法的实验结果和分析

5．4．1 整体表现

5．4．2 参数分析

5．5 CASRW算法的实验结果和分析

5．5．1 整体表现

5．5．2 参数分析

5．6 生物学意义

5．7 本章小结

第六章 总结与展望

6．1 全文总结

6．2 未来展望

参考文献

致谢

攻读学位期间发表论文情况