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

وصف كامل

محفوظ في:
التفاصيل البيبلوغرافية
المؤلفون الرئيسيون: Vu, Thi Ngoc Anh, Nguyen, Trong Dong, Nguyen, Vu Hoang Vuong, Dang, Thanh Hai, Do, Duc Dong
التنسيق: مقال
اللغة:English
منشور في: H. : ĐHQGHN 2019
الموضوعات:
الوصول للمادة أونلاين:http://repository.vnu.edu.vn/handle/VNU_123/64780
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
المؤسسة: Vietnam National University, Hanoi
اللغة: 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