基于离散粒子群优化的生物网络全局比对-研究

《基于离散粒子群优化的生物网络全局比对-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学

2、位期间论文工作的知识产权属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，结合学位论文研究成果完成的论文、发明专利等成果，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：万方数据万方数据摘要摘要生物网络比对旨在通过比较分析的方法来识别不同分子相互作用网络中的相似模块。生物网络比对对理解网络之间的进化关系、预测未知节点的功能、分析人类疾病的机理等具有重要的意义。生物网络比对问题是一个NP-hard问题，因而近似优化算法，例如粒子

3、群优化算法，是用来有效求解网络比对问题的很好选择。粒子群优化（ParticleSwarmOptimization）是一种模拟鸟群协作觅食行为的群智能方法。粒子群优化有实现简单、收敛速度快、不需要问题领域知识等特点。本文利用生物网络的特性和粒子群优化的优点，来优化生物网络比对。本文的主要工作可归纳如下：（1）研究了粒子群优化方法的基本理论，提出了基于3-Opt的离散粒子群优化算法用来优化生物网络比对。在这个算法中，针对网络比对问题，设计了一种基于排列的粒子群状态离散方法；利用了生物网络中的枢纽节点在保持网络结构和功能具有重要作用这一特性，提出了一种基于节点度的初始化方法；分析了生物网络比

4、对中每对匹配的可交换特性，设计了基于3-Opt的局部搜索方法，用来加快算法的收敛速度。该算法所得的网络比对具有较好的拓扑质量，能够识别出较大的最大公共连接子图。（2）根据生物不同网络中存在一定的具有同源关系的节点，以及对于网络比对匹配网络的边能够弥补节点低相似度匹配的不足。提出了一种的基于播种-扩展（seed-and-extend）的网络相似度分步优化策略。应用其于粒子群优化，设计了一种基于播种-扩展的离散粒子群优化算法用来优化生物网络比对。在该算法中提出了一种基于序列相似性的初始化方法和基于扰动的局部搜索方法。该算法获得的网络比对具有很高的功能一致性，并且能在拓扑质量和生物质量上保持

5、平衡。关键词：复杂网络，生物网络比对，粒子群优化，3-Opt，seed-and-extendI万方数据西安电子科技大学硕士学位论文II万方数据ABSTRACTABSTRACTBiologicalnetworkalignmentaimsatidentifyingthesimilarregionofdifferentmolecularinteractionnetworksbycomparativeanalysis.Biologicalnetworkalignmentisofgreatsignificancetounderstandtherelationshipofnetworks,iden

6、tifythepoorlycharacterizednodewiththehelpofthewell-studiedoneandgetinsightintothemechanismofhumandisease.ThenetworkalignmentproblemisknowntobeNP-hard.Forthisreason,theapproximateoptimizationmethod,suchasparticleswarmoptimization,isasuitableoptiontoaddressthenetworkalignmentproblem.ParticleSwarmO

7、ptimization(PSO)isaswarmintelligencemethodsimulatingthecollaborationbehaviorofbirdflocking.PSOhastheadvantageofsimpleimplementation,fastconvergenceandnorequirementofproblem-specificinformation.Ourmainworkinthisthesisisthatad