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
الوسوم: إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
الوصف
الملخص: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