[1]刘晓,陈璟,王子祥.用于成对PPI网络比对的分治与整合算法[J].智能系统学报,2022,17(5):960-968.[doi:10.11992/tis.202106001]
LIU Xiao,CHEN Jing,WANG Zixiang.A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks[J].CAAI Transactions on Intelligent Systems,2022,17(5):960-968.[doi:10.11992/tis.202106001]
点击复制
LIU Xiao,CHEN Jing,WANG Zixiang.A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks[J].CAAI Transactions on Intelligent Systems,2022,17(5):960-968.[doi:10.11992/tis.202106001]
用于成对PPI网络比对的分治与整合算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
17
期数:
2022年第5期
页码:
960-968
栏目:
学术论文—智能系统
出版日期:
2022-09-05
- Title:
- A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks
- Keywords:
- PPI network; network alignment; divide-and-conquer; modularization; bipartite graph; eigenvector centrality; degree centrality; complex networks
- 分类号:
- TP393
- 文献标志码:
- 2022-05-19
- 摘要:
- 生物网络比对是分析不同生物间进化关系的重要手段，它可以揭示不同物种间的保守功能并为物种间的注释转移提供重要信息。网络比对与子图同构类似，是一个NP-hard问题。本文提出了一种新的分治与整合策略的生物网络比对算法。首先进行模块划分，并根据已有的比对信息计算模块相似性；然后根据模块间结点的子比对获取候选结果集，最终通过超图匹配获得比对结果。使用已有的比对信息的集体行为预估模块间的相似性，大大提高了模块匹配的效率。基于路径和结点的得分函数保证了模块内结点的相似性。对于不同网络间结点的相似性，分别从结点自身和结点间的差异进行相似性判断。与现有算法相比，本文算法在生物和拓扑指标上均表现最佳。
- 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.
- 参考文献/References:
-
[1] HASHEMIFAR S, XU Jinbo. HubAlign: an accurate and efficient method for global alignment of protein-protein interaction networks[J]. Bioinformatics (Oxford, England), 2014, 30(17): i438–i444.
[2] MASKEY S, CHO Y R. LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules[J]. BMC genomics, 2019, 20(Suppl 9): 964.
[3] 苗孟君, 丁彦蕊. PPI网络比对用于植物乳杆菌的糖代谢研究[J]. 计算机工程与应用, 2018, 54(6): 49–54
MIAO mengjun, DING yanrui. PPI network alignment for study on carbohydrate metabolism of Lactobacillus Plantarum[J]. Computer engineering and applications, 2018, 54(6): 49–54
[4] GAO Jianliang, TIAN Ling, LYU Tengfei, et al. Protein2Vec: aligning multiple PPI networks with representation learning[J]. IEEE/ACM transactions on computational biology and bioinformatics, 2021, 18(1): 240–249.
[5] WOO H M, YOON B J. MONACO: accurate biological network alignment through optimal neighborhood matching between focal nodes[J]. Bioinformatics, 2020, 37(10): 1401–1410.
[6] MA Lijia, WANG Shiqiang, LIN Qiuzhen, et al. Multi-neighborhood learning for global alignment in biological networks[J]. IEEE/ACM transactions on computational biology and bioinformatics, 2021, 18(6): 2598–2611.
[7] KUCHAIEV O, MILENKOVIC T, MEMISEVIC V, et al. Topological network alignment uncovers biological function and phylogeny[J]. Journal of the royal society, interface, 2010, 7(50): 1341–1354.
[8] APARíCIO D, RIBEIRO P, MILENKOVI? T, et al. Temporal network alignment via GoT-WAVE[J]. Bioinformatics (Oxford, England), 2019, 35(18): 3527–3529.
[9] LLABRéS M, RIERA G, ROSSELLó F, et al. Alignment of biological networks by integer linear programming: virus-host protein-protein interaction networks[J]. BMC bioinformatics, 2020, 21(Suppl 6): 434.
[10] AYUB U, HAIDER I, NAVEED H. SAlign-a structure aware method for global PPI network alignment[J]. BMC bioinformatics, 2020, 21(1): 500.
[11] MAMANO N, HAYES W B. SANA: simulated annealing far outperforms many other search algorithms for biological network alignment[J]. Bioinformatics, 2017, 33(14): 2156–2164.
[12] WANG Shiqiang, MA Lijia, ZHANG Xiao. Adaptive artificial immune system for biological network alignment[M]//Intelligent Computing Theories and Application. Cham: Springer International Publishing, 2020: 560?570.
[13] VIJAYAN V, SARAPH V, MILENKOVI? T. MAGNA++: Maximizing Accuracy in Global Network Alignment via both node and edge conservation[J]. Bioinformatics, 2015, 31(14): 2409–2411.
[14] 陶斯涵, 丁彦蕊. 引入序列信息的残基相互作用网络比对算法[J]. 软件学报, 2019, 30(11): 3413–3426
DING yanrui, TAO sihan. Algorithm introduced sequence information for residue interaction network alignment[J]. Journal of software, 2019, 30(11): 3413–3426
[15] KAZEMI E, HASSANI H, GROSSGLAUSER M, et al. PROPER: global protein interaction network alignment through percolation matching[J]. BMC bioinformatics, 2016, 17(1): 1–16.
[16] HASHEMIFAR S, MA Jianzhu, NAVEED H, et al. ModuleAlign: module-based global alignment of protein-protein interaction networks[J]. Bioinformatics, 2016, 32(17): i658–i664.
[17] ZHU Lijuan, ZHANG Ju, ZHANG Yi, et al. NAIGO: an improved method to align PPI networks based on gene ontology and graphlets[J]. Frontiers in bioengineering and biotechnology, 2020, 8: 547.
[18] ALCALá A, ALBERICH R, LLABRéS M, et al. AligNet: alignment of protein-protein interaction networks[J]. BMC bioinformatics, 2020, 21(6): 1–22.
[19] GUZZI P H, MILENKOVIC T. Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin[J]. Briefings in bioinformatics, 2018, 19(3): 472–481.
[20] ERTEN C. Global alignment of PPI networks[M]//Recent Advances in Biological Network Analysis. Cham: Springer International Publishing, 2020: 3-25.
[21] KALECKY K, CHO Y R. PrimAlign: PageRank-inspired Markovian alignment for large biological networks[J]. Bioinformatics (Oxford, England), 2018, 34(13): i537–i546.
[22] ASHBURNER M, BALL C A, BLAKE J A, et al. Gene ontology: tool for the unification of biology. The gene ontology consortium[J]. Nature genetics, 2000, 25(1): 25–29.
[23] KUHN H W. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly, 1955, 2(1-2): 83–97.
[24] LEI Xiujuan, YANG Xiaoqin, FUJITA H. Random walk based method to identify essential proteins by integrating network topology and biological characteristics[J]. Knowledge-based systems, 2019, 167: 53–67.
[25] BORND?RFER R, HEISMANN O. The hypergraph assignment problem[J]. Discrete optimization, 2015, 15: 15–25.
[26] PARK D, SINGH R, BAYM M, et al. IsoBase: a database of functionally related proteins across PPI networks[J]. Nucleic acids research, 2011, 39: D295-D300.
[27] SAHRAEIAN S M E, YOON B J. A network synthesis model for generating protein interaction network families[J]. PLoS one, 2012, 7(8): e41474.
- 相似文献/References:
-
[1]刘光明,杨柳,高盼盼,等.融合蛋白质复合体的人类蛋白互作网络功能模块发现[J].智能系统学报,2016,11(5):703.[doi:10.11992/tis.201603034]
LIU Guangming,YANG Liu,GAO Panpan,et al.The functional module detection of PPI network by incorporating protein complex data[J].CAAI Transactions on Intelligent Systems,2016,11():703.[doi:10.11992/tis.201603034]
备注/Memo
收稿日期:2021-06-01。
基金项目:江苏省青年科学基金项目（BK20150159）；江苏省研究生科研创新计划（KYCX20_1939）.
作者简介:刘晓，硕士研究生，主要研究方向为生物信息学;陈璟，副教授，博士，主要研究方向为复杂网络、室内定位。主持江苏省青年基金1项，参与国家自然科学基金3项，申请发明专利13项，授权发明专利4项，获得省部级奖4项，发表学术论文20余篇;王子祥，硕士研究生，主要研究方向为生物信息学
通讯作者:陈璟. E-mail: chenjing@jiangnan.edu.cn
更新日期/Last Update:
1900-01-01