TAILIEUCHUNG - Adaptive large neighborhood search enhances global protein protein network alignment

In this paper, we present a novel global protein-protein interaction network alignment algorithm, which is enhanced with an extended large neighborhood search heuristics. Evaluated on benchmark datasets of yeast, fly, human and worm, the proposed algorithm outperforms state-of-the-art algorithms. Furthermore, the complexity of ours is polynomial, thus being scalable to large biological networks in practice. | VNU Journal of Science Comp. Science amp Com. Eng. Vol. 35 No. 1 2019 46-55 Original Article Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment Vu Thi Ngoc Anh1 2 Nguyen Trong Dong2 Nguyen Vu Hoang Vuong2 Dang Thanh Hai3 Do Duc Dong3 1 The Hanoi college of Industrial Economics 2 VNU University of Engineering and Technology 144 Xuan Thuy Cau Giay Hanoi Vietnam 3 Bingo Biomedical Informatics Laboratory Bingo Lab Faculty of Information Technology VNU University of Engineering and Technology Received 05 March 2018 Revised 19 May 2019 Accepted 27 May 2019 Abstract Aligning protein-protein interaction networks from different species is a useful mechanism for figuring out orthologous proteins predicting verifying protein unknown functions or constructing evolutionary relationships. The network alignment problem is proved to be NP-hard requiring exponential-time algorithms which is not feasible for the fast growth of biological data. In this paper we present a novel global protein-protein interaction network alignment algorithm which is enhanced with an extended large neighborhood search heuristics. Evaluated on benchmark datasets of yeast fly human and worm the proposed algorithm outperforms state-of-the-art algorithms. Furthermore the complexity of ours is polynomial thus being scalable to large biological networks in practice. Keywords Heuristic Protein-protein interaction networks network alignment neighborhood search. 1. Introduction From biological perspectives a good alignment between protein-protein networks Advanced high-throughput biotechnologies PPI in different species could provide a strong have been revealing numerous interactions evidence for i predicting unknown functions between proteins at large-scales for various of orthologous proteins in a less-well studied species. Analyzing those networks is thus species or ii verifying those with known becoming emerged such as network topology functions 5 or iii detecting common .

• Địa Lý
• Protein protein interaction networks
• Network alignment
• Neighborhood search
• The network alignment problem
• Constructing evolutionary relationships
• BMC Bioinformatics
• Protein complexes
• Biological networks
• Network clustering
• Functional networks