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

摘要

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