基于Memetic计算的生物网络全局比对研究

《基于Memetic计算的生物网络全局比对研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于Memetic计算的生物网络全局比对研究作者姓名彭正林学校导师姓名、职称企业导师姓名、职称申请学位类别张青富教授刘文学高工工程硕士学校代码分类号10701TP18学密号级1302121508公开西安电子科技大学硕士学位论文基于Memetic计算的生物网络全局比对研究作者姓名：彭正林领域：电子与通信工程学位类别：工程硕士学校导师姓名、职称：张青富教授企业导师姓名、职称：刘文学高工学院：电子工程学院提交日期：2015年12月GlobalBiologicalNetworkAlignmentbyUs

2、ingMemeticAlgorithmAthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinElectronicsandCommunicationsEngineeringByPengZhenglinSupervisor:ZhangQingfuProfessorLiuWenxueSeniorEngineerDecember2015西安电子科技大学学位论文独创性（或创新

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

4、保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，结合学位论文研究成果完成的论文、发明专利等成果，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要随着高通量筛选技术和计算机技术的飞速发展，现在已经能够获得越来越多的生物数据，其中很重要的一类数据就是蛋白质间的相

5、互作用数据。有了这些数据，就可以从系统的角度来分析生命的活动过程。通常将蛋白质间相互作用数据抽象成网络模型进行分析，而网络比对方法是一种在研究生物网络数据时常用的系统分析方法。对蛋白质网络数据的比对分析能够帮助我们发现未知生物网络中的保守功能子图并且加深对不同物种进化轨迹的认识。一些进化算法已经被提出来解决蛋白质网络的比对问题，但是这些被提出的算法往往因为没有加入先验知识而搜索效率非常低下。本文提出了一种Memetic算法，表示为MeAlign，用来解决生物网络的比对问题。MeAlign算法吸取

6、了二步算法的思想，先利用已有的先验知识构造一个粗糙的得分矩阵，再用这个得分矩阵来指导初始化；而在局部搜索算子的设计部分，吸取该领域经典算法中的种子加扩展方法思想，设计了一种高效的基于特定邻域的局部搜索算子。该算子首先定义了单个网络节点的邻域空间，然后在邻域空间中寻找对优化模型有贡献的匹配结点。为了更全面的分析说明蛋白质网络的比对问题和MeAlign算法解决比对问题的效果，本文通过两条主线加以说明：1)通过优化不同的网络模型来说明网络模型的选取对比对结果的影响。先通过只优化网络的拓扑相似性模型来得

7、到比对结果，再通过分析比对结果指出这种模型的不足之处；然后在此基础上提出优化加权模型，就是同时优化网络的拓扑相似性和网络结点的序列相似性。通过分析加权模型优化的比对结果，得出加权模型更适合用来求解生物网络的比对问题。2)在优化两种不同网络模型时，将MeAlign算法与该领域的经典算法进行详细对比分析，来说明MeAlign算法的效果；然后再单独和代表遗传算法的MAGNA和MAGNA++进行详细对比，证明MeAlign算法设计的局部搜索算子的有效性。关键词：Memetic算法，遗传算法，生物网络比对

8、，局部搜索，特定邻域空间I西安电子科技大学硕士学位论文IIABSTRACTABSTRACTHigh-throughputexperimentalscreeningtechniquesandcomputertechnologyhaveresultedinalargenumberofbiologicaldata,amongwhichprotein-proteininteractions(PPI)dataisoneofthemostimportantparts.Thesedatamakeitpossi