Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment

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-ti...

Full description

Saved in:
Bibliographic Details
Main Authors: Vu, Thi Ngoc Anh, Nguyen, Trong Dong, Nguyen, Vu Hoang Vuong, Dang, Thanh Hai, Do, Duc Dong
Format: Article
Language:English
Published: H. : ĐHQGHN 2019
Subjects:
Online Access:http://repository.vnu.edu.vn/handle/VNU_123/64780
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Vietnam National University, Hanoi
Language: English
id oai:112.137.131.14:VNU_123-64780
record_format dspace
spelling oai:112.137.131.14:VNU_123-647802019-07-01T09:37:23Z Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment Vu, Thi Ngoc Anh Nguyen, Trong Dong Nguyen, Vu Hoang Vuong Dang, Thanh Hai Do, Duc Dong Heuristic Protein-protein interaction networks network alignment neighborhood search 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 2019-07-01T09:37:23Z 2019-07-01T09:37:23Z 2019 Article Vu, T. N. A., et al. (2019). Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment. Journal of Science: Comp. Science & Com. Eng., Vol. 35, No. 1 (2019) 46-55. http://repository.vnu.edu.vn/handle/VNU_123/64780 en Journal of Science: Comp. Science & Com. Eng.; application/pdf H. : ĐHQGHN
institution Vietnam National University, Hanoi
building VNU Library & Information Center
country Vietnam
collection VNU Digital Repository
language English
topic Heuristic
Protein-protein interaction networks
network alignment
neighborhood search
spellingShingle Heuristic
Protein-protein interaction networks
network alignment
neighborhood search
Vu, Thi Ngoc Anh
Nguyen, Trong Dong
Nguyen, Vu Hoang Vuong
Dang, Thanh Hai
Do, Duc Dong
Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
description 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
format Article
author Vu, Thi Ngoc Anh
Nguyen, Trong Dong
Nguyen, Vu Hoang Vuong
Dang, Thanh Hai
Do, Duc Dong
author_facet Vu, Thi Ngoc Anh
Nguyen, Trong Dong
Nguyen, Vu Hoang Vuong
Dang, Thanh Hai
Do, Duc Dong
author_sort Vu, Thi Ngoc Anh
title Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
title_short Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
title_full Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
title_fullStr Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
title_full_unstemmed Adaptive Large Neighborhood Search Enhances Global Protein-Protein Network Alignment
title_sort adaptive large neighborhood search enhances global protein-protein network alignment
publisher H. : ĐHQGHN
publishDate 2019
url http://repository.vnu.edu.vn/handle/VNU_123/64780
_version_ 1680964050013388800