[1]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]
Copy

A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 17 Number of periods: 2022 5 Page number: 960-968 Column: 学术论文—智能系统 Public date: 2022-09-05
Title:
A divide-and-conquer and integration algorithm for pairwise alignment of PPI networks
Author(s):
LIU Xiao1;  CHEN Jing1; 2;  WANG Zixiang1
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
Keywords:
PPI network; network alignment; divide-and-conquer; modularization; bipartite graph; eigenvector centrality; degree centrality; complex networks
CLC:
TP393
DOI:
10.11992/tis.202106001
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems