基于群智能机理的PPI网络功能模块聚类

发布时间：2018-04-18 22:11

本文选题：蛋白质相互作用网络 + 人工鱼群算法　；参考：《陕西师范大学》2012年硕士论文

【摘要】：随着人类基因组计划的完成和蛋白质组学的研究进展,由生物体动态产生并执行遗传程序的蛋白质逐渐进入人们的视线。众所周知,蛋白质是是构成一切细胞组织的必不可少的成分,是生理功能的执行者。但是研究表明细胞中的大部分蛋白质并不是孤立存在的,而是与其它蛋白质一起进行相互作用来行使其功能的。在一个生命体内,所有蛋白质之间的相互作用组成的网络称为蛋白质相互作用(Protein-Protein Interaction, PPI)网络。通过对PPI网络的模块化研究可以从分子水平上预测未知蛋白质的功能,从而进一步揭示生长发育、新陈代谢等细胞活动的规律以及生命过程中的许多本质问题,并有利于疾病的诊断和病理的深入研究,同时推动生物学、医学以及生物信息学等多种学科的研究和发展。群智能优化算法是模拟自然界生物系统通过无意识的寻优行为来优化其生存状态并适应环境的一类新型的最优化方法,具有自组织性、可扩展性和较强的鲁棒性,目前已经成功地解决了数据挖掘、图像处理、函数优化、TSP等领域的许多问题。本文对群智能算法的特点和优势进行了简单概述,并详细介绍了几种主流的智能优化算法的原理以及算法步骤。针对传统的聚类算法和功能流聚类算法在解决PPI网络聚类问题上存在的缺陷,如正确率和查全率较低、时间复杂度较高以及预先设置聚类数目等问题,本文结合PPI网络的小世界和无尺度的拓扑结构特征,分别采用了蚁群算法、人工鱼群算法以及细菌觅食优化算法解决PPI网络的聚类问题。本文首先在基本功能流聚类算法的基础上融入了蚁群优化算法的机理,提出了一种基于信息素更新的蚁群优化(Variable Pheromone based Ant Colony Optimization. VPACO)PPI网络聚类算法。该算法将食物源看作聚类中心,将蚂蚁看作除了聚类中心之外的蛋白质结点。在PPI网络聚类过程中,蛋白质结点根据它们距离聚类中心的路径上的信息素的浓度以及对应的状态转移概率判断是否归并到该聚类中心所在的聚类模块中。PPI数据上的仿真结果表明该算法可以有效地提高聚类结果的正确率以及查全率。采用智能优化算法机理优化基本功能流的方法可以有效地预测未知蛋白质的功能,但是时间复杂度比较高。为此本文直接将人工鱼群算法的机理应用到PPI网络聚类问题上,将人工鱼看作是一组聚类中心,在人工鱼执行觅食行为的过程中,算法从聚类中心开始向它的邻接结点搜索生成聚类模块。接下来执行追尾行为,将适应度值最大的人工鱼对应的一组聚类模块看作初始的聚类结果,剩下的人工鱼开始执行聚群行为,判断对应的聚类模块与初始的聚类结果之间的相似度,如果低于给定的阈值,则添加到初始的聚类结果中。仿真结果表明该算法可以自动确定聚类数目,而且聚类结果的正确率和算法的运行效率都优于功能流聚类算法。另外考虑到PPI网络中的蛋白质结点可能具有一种或者多种功能,本文提出了一种基于直觉模糊集的改进细菌觅食优化算法,简称为IFBFO(Intuitionistic Fuzzy set based Bacteria Foraging Optimization)算法。该算法在细菌执行复制行为操作的过程中,采用直觉模糊集中的隶属度和犹豫度对PP1网络中的蛋白质结点进行聚类,犹豫度较高的蛋白质结点可以归并到一个或者多个功能模块中,因此会产生重叠的聚类模块。仿真实验结果表明该算法可以有效地提高聚类结果的查全率,并能更准确地检测出功能相同的蛋白质聚类模块。
[Abstract]:With the progress of human genome project and complete proteome study, produced by organisms and perform dynamic genetic program of protein gradually into people's sight. As everyone knows, is a protein which all the tissue essential ingredient is the executor of the physiological function. But the research shows that most of the protein in the cell is not isolated but, together with other proteins interact to perform their functions. In an organism consisting of all interactions between proteins known as protein interaction network (Protein-Protein Interaction PPI) network. To predict unknown protein functions at the molecular level can be studied by means of modularization on the PPI network, thus further to reveal the growth of many cell activities of the nature of the problem The new supersedes the old. law and in the course of life, It also facilitates the diagnosis and pathology of the disease, and promotes the research and development of biology, medicine and bioinformatics.
Swarm intelligence optimization algorithm is simulated through unconscious behavior optimization to optimize the survival state and adapt to a new environment optimization method of natural biological systems, with self-organization, scalability and robustness, has successfully solved the data mining, image processing, function optimization, many problems of TSP other fields. In this paper, the characteristics and advantages of swarm intelligence algorithms were introduced simply, and introduced several mainstream intelligent optimization algorithm principle and algorithm steps. Aiming at the limitation of traditional clustering methods and functional flow clustering algorithm exists in the PPI network to solve the clustering problem, such as accuracy and low recall. The time complexity is high and the preset number of clusters, this paper combines the PPI network of the small world and scale-free topology characteristics, using ant colony algorithm, artificial fish swarm algorithm The algorithm and bacterial foraging optimization algorithm solve the clustering problem of PPI network.
Based on the basic functions of the current clustering algorithm into the mechanism of ant colony optimization algorithm, this paper proposed an ant colony optimization based on pheromone update (Variable Pheromone based Ant Colony Optimization. VPACO) PPI network clustering algorithm. The algorithm of food source is regarded as the clustering center, the ants are considered to be the protein except the cluster center node. In the PPI network clustering process, the protein node according to the path their distance from the clustering center of the pheromone concentration and the corresponding state transition probability to determine whether the incorporation of.PPI data simulation results on clustering module in the clustering center that the correct rate of the algorithm can effectively improve the clustering results and recall.
The mechanism of intelligence optimization algorithm method of basic function flow can effectively predict unknown protein functions, but the time complexity is relatively high. This paper will direct the mechanism of artificial fish swarm algorithm is applied to PPI network clustering problem, artificial fish as a set of cluster centers, the artificial fish foraging behavior in the process of execution that algorithm begins its search to adjacent node clustering module from the clustering center. Then the following behavior, the fitness value of the clustering results a set of clustering modules corresponding to the largest artificial fish as the initial, the rest of the artificial fish swarm behavior started, the similarity between the clustering result and the initial judgment of the corresponding clustering module, if less than the threshold, is added to the initial clustering results. The simulation results show that the algorithm can automatically determine the number of clustering and clustering results The correctness rate and the operation efficiency of the algorithm are better than the function flow clustering algorithm.
Considering the protein node in PPI network may have one or more functions, this paper presents an improved bacterial foraging optimization algorithm based on intuitionistic fuzzy sets, referred to as IFBFO (Intuitionistic Fuzzy set based Bacteria Foraging Optimization) algorithm. The algorithm in the process of implementation of bacterial reproduction operation, using intuitionistic fuzzy sets membership and hesitancy degree of clustering protein node in PP1 network, the uncertain degree of higher protein nodes can merge into one or more functional modules, and therefore will have overlapping clustering module. Simulation results show that this algorithm can effectively improve the clustering results of the recall, and can more accurately detect protein the same clustering module.

【学位授予单位】：陕西师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：R346;TP18

【参考文献】