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

摘要

生物网络比对旨在通过比较分析的方法来识别不同分子相互作用网络中的相似模块。生物网络比对对理解网络之间的进化关系、预测未知节点的功能、分析人类疾病的机理等具有重要的意义。生物网络比对问题是一个NP-hard问题，因而近似优化算法，例如粒子群优化算法，是用来有效求解网络比对问题的很好选择。粒子群优化（Particle Swarm Optimization）是一种模拟鸟群协作觅食行为的群智能方法。粒子群优化有实现简单、收敛速度快、不需要问题领域知识等特点。本文利用生物网络的特性和粒子群优化的优点，来优化生物网络比对。本文的主要工作可归纳如下：
　　（1）研究了粒子群优化方法的基本理论，提出了基于3-Opt的离散粒子群优化算法用来优化生物网络比对。在这个算法中，针对网络比对问题，设计了一种基于排列的粒子群状态离散方法；利用了生物网络中的枢纽节点在保持网络结构和功能具有重要作用这一特性，提出了一种基于节点度的初始化方法；分析了生物网络比对中每对匹配的可交换特性，设计了基于3-Opt的局部搜索方法，用来加快算法的收敛速度。该算法所得的网络比对具有较好的拓扑质量，能够识别出较大的最大公共连接子图。
　　（2）根据生物不同网络中存在一定的具有同源关系的节点，以及对于网络比对匹配网络的边能够弥补节点低相似度匹配的不足。提出了一种的基于播种-扩展（seed-and-extend）的网络相似度分步优化策略。应用其于粒子群优化，设计了一种基于播种-扩展的离散粒子群优化算法用来优化生物网络比对。在该算法中提出了一种基于序列相似性的初始化方法和基于扰动的局部搜索方法。该算法获得的网络比对具有很高的功能一致性，并且能在拓扑质量和生物质量上保持平衡。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1课题的研究背景

1.2课题的研究现状和意义

1.3本文的内容安排

第二章 生物网络全局比对的相关理论

2.1生物网络全局比对的模型

2.2生物网络全局比对的几类算法

第三章 基于3-Opt的粒子群算法用于优化网络全局比对

3.1粒子群优化算法

3.2用于优化网络全局比对问题的粒子群离散方法

3.3实验分析

第四章 基于播种-扩展的粒子群算法用于优化网络全局比对

4.1播种-扩展（seed-and-extend）策略

4.2 SAENA算法

4.3实验分析

第五章 总结和展望

5.1总结

5.2展望

参考文献

致谢

作者简介