群智能优化算法及其在PPI网络中的应用研究

【作者】 黄旭；

【导师】 雷秀娟；

【作者基本信息】 陕西师范大学 ， 计算机应用技术， 2011， 硕士

【摘要】 随着生物信息学的不断发展,人们发现蛋白质并不是独立地在细胞中发挥作用的,它们通常是通过与其它蛋白质之间的相互作用,形成一个功能整体才能发挥相应的功能。在一个生命体内所有蛋白质的相互作用,被称为蛋白质相互作用网络(PPI网络)。通过对PPI网络的研究,能了解生命个体的生理代谢原理、循环作用,也能对病理进入深层次的分析,揭示生命的奥义,使人类对生物界的认识迈入一个新的台阶。群智能优化算法的理论基础在于仿生学,在该类算法思想被提出至今,已经被各界学者们进行了深入的研究和广泛的应用,其已在解决TSP问题、数据挖掘、图象处理、函数优化等领域形成了成熟的应用。现阶段在不断完善现有算法的同时,也不断涌现出新的群智能优化算法。因此,群智能优化算法是智能计算领域的一大研究热点。本文首先对群智能算法进行了概述并对主流的群智能优化算法给出了相关的描述。在此基础上指出现有群智能算法的优点和不足及需改进的地方。然后对国内外PPI网络以及群智能算法的研究现状进行了分析,对PPI网络进行了简要的介绍,并对PPI网络在计算分析领域的主要分析方法——聚类算法,进行了简要的介绍。其次,针对PPI网络中的无尺度、小世界等特性,提出目前在PPI数据聚类中效果较好的功能流聚类算法中的不足之处。对PPI数据中的桥结点提出一种识别和处理的方法,将特殊结点进行单独处理,以提高功能流算法的精准度。并在此基础上,将群智能优化的思想引入到聚类算法当中,对其中的一些需要根据经验人为设定的参数进行自动寻优,以获得最佳适应值,使聚类算法的结果最优化并具有稳定性。改进后的算法命名为IQ-Flow算法。针对MIPS的PPI数据集,采用IQ-Flow算法进行仿真实验,结果表明改进后的算法在算法精度和算法的稳定性上都有了一定程度的提高。在群智能优化算法方面,对人工蜂群算法的不足进行了改进研究。在综合其它群智能算法的改进方法的基础上,引入了惯性权重、收缩因子以及随机扰动因子的概念,对人工蜂群算法中的更新公式进行改进,提出了一种改进的人工蜂群算法(IABC算法)。通过测试函数及仿真实验结果表明,IABC算法比标准人工蜂群算法及在实验中参与对比的其它几种群钾能优化算法,在精度和收敛速度上都具有较明显的优势。针对MIPS的PPI数据集,采用IABC算法进行阈值自动寻优,克服了人工给定阈值的主观性,并且蛋白质识别的准确率有一定程度的提高。另外,根据PPI网络的拓扑结构特性提出了一种基于连接强度的PPI网络聚类蚁群算法(Joint Strength Based Ant Colony Optimization Algorithm, JSACO),算法根据PPI网络数据的特性,引入了连接强度的概念对蚁群聚类算法中的拾起/放下规则加以改进,以降低对PPI网络数据聚类的时间开销以及提高结果的正确率。在仿真实验中使用了MIPS的PPI数据进行实验,将改进的蚁群算法与PPI标准结果库及PPI网络数据聚类中的其它算法进行比较,结果表明改进的蚁群算法时间开销降低且准确率有所提高。最后,文章对全文进行了总结并指出今后研究工作需要继续改进的地方和工作的重心。更多还原

【Abstract】 As the development of bioinformatics, it is found that proteins don’t work separately. They usually interact with others and gather as an entirety to function. All the interactions in a life together is called protein protein interaction network (PPI network). The research of PPI network could help know the biological metabolism and circulatory system, deeply analyze disease, and enlighten the meaning of life. This would lead to a new stage of our knowledge of living life. Swarm intelligent algorithms are based on bionics. They have been profoundly studied, and matured applications of swarm intelligence are widely seen in solving TSP problem, data mining, image process, function optimization etc. The existing algorithms are being improved and the new algorithms are being proposed. As a result, swarm intelligent algorithms are one of the headlines of computational intelligence.This paper firstly introduced the main concepts of swarm intelligence and gave some descriptions of several typical algorithms. In addition, it gave the advantages and disadvantages of these algorithms and pointed out where to be improved. This paper also did researches on bioinformatics and gave a brief introduction on PPI network. In the mean time, as main computation analyzing methods, clustering algorithms were described.According to the scale free and small world characteristics of PPI network, this paper analyzed the insufficiencies of the functional flow algorithm which performs comparatively well. The thought of recognizing and dealing with bridging nodes were proposed to improve the performance of the algorithm. At the basis of this, swarm intelligence was introduced into the functional flow algorithm to automatically optimize some parameter which is manually set by experience. This would help raise the stability of the results and the improved algorithm was named as IQ-Flow algorithm. MIPS PPI data was used to test the IQ-Flow algorithm, the simulation results showed that the precision and stability were raised.In swarm intelligence, this paper studied artificial bee colony (ABC) algorithm. On synthesizing kinds of improve strategies of other swarm intelligent algorithms, weight factor, contracted factor and random disturbance were introduced to improve the ABC algorithm. The improved algorithm was called IABC algorithm. The simulation results showed that IABC algorithm performs better than the original ABC and other participated swarm intelligent algorithms both in speed and precision. IABC was also used to automatically search the threshold in order to overcome the subjectivities and the precision was raised. In addition, an ACO algorithm based on joint strength (Joint Strength Based Ant Colony Optimization Algorithm, JSACO) was proposes. According to the characters of PPI data, joint strength was introduced to modify the pickup/drop rules in order to reduce the time consuming and raise the precision of the algorithm. In the simulation of this paper, MIPS PPI data were used to test the JSACO algorithm. Also the simulation result was compared with other PPI clustering methods. The simulation results show that the JSACO algorithm costs less in time consume and performs better in precision.Finally, this paper gave a conclusion and made a prospect of the upcoming work.更多还原