基于层次聚类的生物网络全局比对算法

摘要：

生物网络比对是研究生物进化过程的重要手段,不同物种间的比对不仅有助于理解物种的知识转移,同时也有助于进行功能预测和检测保守功能成分.然而,现有比对算法很难实现拓扑度量和生物度量同时最优.设计JAlign算法,将拓扑相似性与归一化序列相似性相结合构成目标函数,基于种子-扩展算法和模块检测进行全局比对.在种子筛选阶段,利用Jerarca聚类算法划分功能模块,借助目标函数计算模块间的相似性进行最优模块匹配,并从匹配结果中提取部分节点对作为种子节点.在扩展阶段,将比对从种子节点扩展至其邻居节点,在选择节点对进行扩展比对时综合考虑节点之间的连接关系、度差值、节点相似性等因素.在此基础上,为避免遗漏分散节点,找到剩余未匹配的节点构建二分图,以贪心方式进行最大加权二分图匹配,并将匹配结果合并到比对集合中,完成最终匹配.实验结果表明,JAlign算法能够实现拓扑度量和生物度量的良好平衡,其边正确性指标、诱导保守子结构得分、对称子结构得分和生物质量使用功能一致性指标均优于L-GRAAL、SPINAL和ModuleAlign算法,在时间效率上也具有优势.

关键词：蛋白质相互作用网络;网络比对;层次聚类;功能模块检测;种子-扩展算法

所属期刊栏目：48

分类号：TP393(计算技术、计算机技术)

资助基金：江苏省青年科学基金BK20150159

在线出版日期：2022-02-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：65-71,78