基于蛋白质相互作用网络的聚类和稀疏点检测算法研究

摘要

随着人类基因组测序的完成，对蛋白质结构和功能的研究成为基因组学研究的一大热点。研究证明，蛋白质在其功能组中很少以单个个体而存在，一般与功能相似的蛋白质之间存在相互作用。因此，我们可以通过对蛋白质相互作用(Protein-Protein interaction,PPI)网络的研究来预测其功能。本文将在基于PPI网络的聚类及稀疏点检测算法两方面进行研究： 提出一种蛋白质功能预测算法——基于算术平均最小值(the ArithmeticAverage Minimum Value，AAMV)的K-means聚类算法。首先，根据蛋白质之间的相互作用，通过人类AD(Alzheimer's Disease)相关PPI网络图，得出蛋白质之间的关联矩阵；然后，利用AAMV法求得相似度矩阵；接着，鉴于误差平方和准则不能较好的对聚类进行收敛，提出了加权的误差平方和准则；最后，在相似度矩阵的基础上，利用加权的误差平方和准则进行有效收敛，利用K-means聚类方法对PPI网络中的蛋白质进行聚类与功能预测。 提出PPI网络中的稀疏点检测算法——基于加权的相似系数和算法。首先，根据蛋白质之间的相互作用，通过人类AD(Alzheimer's Disease)相关PPI网络图，得出蛋白质之间的关联矩阵；然后，利用最大最小值法求得相似系数矩阵；接着，由于相似系数和不能对PPI网络中的稀疏点进行更好的检测，因此，在相似系数的基础上提出加权的相似系数和方法。最后，根据输入的阈值，利用相似系数和算法得出PPI网络中的稀疏蛋白质。 基于人类AD相关PPI网络图，利用基于AAMV的K-means算法对图中蛋白质进行聚类，其结果与Maryland Bridge法和Korbel法所得结果非常相似；利用聚类结果，对四个孤立蛋白质的功能进行预测。同时，利用加权的相似系数和算法对图中的稀疏蛋白质进行检测，实验结果表明：输入的阈值取值在0.01-0.16之间时，其精确度比较高。

目录

文摘

英文文摘

论文说明:图表目录

声明

第1章绪论

1.1本文的研究目的

1.2项目来源

1.3选题背景和意义

1.3.1生物信息学概念

1.3.2生物信息学的主要研究内容

1.3.3生物信息学的研究目标和任务

1.3.4生物信息学的研究意义

1.4蛋白质组学研究

1.5本文的主要工作及结构安排

1.5.1本文的主要研究内容

1.5.2本文的组织结构

第2章生物数据挖掘PPI网络概述

2.1生物数据挖掘

2.2聚类分析算法

2.2.1基于划分的方法

2.2.2基于层次的方法

2.2.3基于密度的方法

2.2.4基于网格的方法

2.2.5基于模型的方法

2.3 PPI及其网络

2.3.1大规模PPI研究的目的及意义

2.3.2大规模PPI的研究策略及方法

2.3.3大规模PPI的研究现状

2.3.4 PPI网络

2.4孤立点挖掘方法

2.4.1基于统计的方法

2.4.2基于距离的方法

2.4.3基于偏离的方法

2.4.4基于密度的方法

2.5孤立点检测方法研究现状概述

2.6 小结

第3章基于PPI网络的聚类算法

3.1引言

3.2相似性度量——AAMV法

3.3聚类准则函数

3.4基于AAMV的K-means聚类算法

3.4.1算法的处理流程

3.4.2算法描述

3.5实验及比较分析

3.5.1利用基于AAMV的K-means聚类算法进行聚类的结果

3.5.2利用Maryland Bridge方法进行聚类的结果

3.5.3利用Korbel方法进行聚类的结果

3.5.4实验结果的分析比较

3.6 小结

第4章基于PPI网络的稀疏点检测

4.1引言

4.2相似度定义

4.3相似系数和

4.3.1相似系数和

4.3.2加权的相似系数和

4.4基于PPI网络的稀疏点检测算法

4.4.1算法的处理流程

4.4.2算法描述

4.5实验及其分析

4.5.1实验结果

4.5.2实验结果的分析

4.5.3算法时间复杂度分析

4.6小结

结论

参考文献

致谢

附录A 攻读硕士期间发表的论文和参加的项目