| 用于成对PPI网络比对的分治与整合算法 |
| |
| 引用本文： | 刘晓,陈璟,,王子祥.用于成对PPI网络比对的分治与整合算法[J].智能系统学报,2022,17(5):960-968. |
| |
| 作者姓名： | 刘晓 陈璟 王子祥 |
| |
| 作者单位： | 1. 江南大学 人工智能与计算机学院，江苏 无锡 214122;2. 江南大学 江苏省模式识别与计算智能工程实验室，江苏 无锡 214122 |
| |
| 摘 要： | 生物网络比对是分析不同生物间进化关系的重要手段，它可以揭示不同物种间的保守功能并为物种间的注释转移提供重要信息。网络比对与子图同构类似，是一个NP-hard问题。本文提出了一种新的分治与整合策略的生物网络比对算法。首先进行模块划分，并根据已有的比对信息计算模块相似性；然后根据模块间结点的子比对获取候选结果集，最终通过超图匹配获得比对结果。使用已有的比对信息的集体行为预估模块间的相似性，大大提高了模块匹配的效率。基于路径和结点的得分函数保证了模块内结点的相似性。对于不同网络间结点的相似性，分别从结点自身和结点间的差异进行相似性判断。与现有算法相比，本文算法在生物和拓扑指标上均表现最佳。
|
| 关 键 词： | 蛋白质相互作用网络 网络比对 分治 模块化 二分图 特征向量中心性 度中心性 复杂网络 |
A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks |
| |
| LIU Xiao,CHEN Jing,,WANG Zixiang.A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks[J].CAAL Transactions on Intelligent Systems,2022,17(5):960-968. |
| |
| Authors: | LIU Xiao CHEN Jing WANG Zixiang |
| |
| Affiliation: | 1. School of Artificial Intelligence and Computer Science, Jiangnan University, Wuxi 214122, China;2. Jiangsu Provincial Engineering Laboratory of Pattern Recognition and Computing Intelligence, Jiangnan University, Wuxi 214122, China |
| |
| Abstract: | Biological network alignment is an important means of analyzing the evolutionary relationships between different species. It can reveal the conservative function between different species and provide important information for cross-species annotation transfer. Network alignment, like subgraph isomorphism, is an NP-hard problem. In this paper, a new biological network alignment algorithm is proposed, which adopts the divide-and-conquer strategy as a whole. Firstly, module division is executed, and module similarity is calculated according to existing alignment information. The candidate result set is then obtained according to the subalignment of nodes between modules, and the alignment results are finally obtained through hypergraph matching. The collective behavior of the existing alignment information is used to estimate the similarity between modules, greatly improving module matching efficiency. The score function based on paths and nodes ensures the similarity of nodes in the same module. The similarity of nodes between different networks is judged by the nodes themselves and the difference between nodes. The algorithm in this paper performs best in both biological and topological evaluations when compared with the other existing algorithms. |
| |
| Keywords: | PPI network network alignment divide-and-conquer modularization bipartite graph eigenvector centrality degree centrality complex networks |
|
| 点击此处可从《智能系统学报》浏览原始摘要信息 |
|
点击此处可从《智能系统学报》下载全文 |
