Photo Photo Photo Photo Photo Photo
Print
E-mail
Computer science: AHeuristic Strategy for Improving the Performance of Evolutionary Based Complex Detection in Protein-Protein Interaction Networks

 

AHeuristic Strategy for Improving the Performance of Evolutionary Based Complex Detection in Protein-Protein Interaction Networks

Qusay Z. Abdullah*, Bara'a Ali Attea

Department of Computer Science, College of Science, University of Baghdad, Baghdad, Iraq.

Abstract

     One of the most interested problems that recently attracts many research investigations in Protein-protein interactions (PPI) networks is complex detection problem. Detecting natural divisions in such complex networks is proved to be extremely NP-hard problem wherein, recently, the field of Evolutionary Algorithms (EAs) reveals positive results. The contribution of this work is to introduce a heuristic operator, called protein-complex attraction and repulsion, which is especially tailored for the complex detection problem and to enable the EA to improve its detection ability. The proposed heuristic operator is designed to fine-grain the structure of a complex by dividing it into two more complexes, each being distinguished with a core protein.  Then, it is possible for each of the remaining proteins associated with the original coarse-grained complex to repulse from one of the new generated complexes while attracted by the core protein of the second complex. The topology-based complex detection models presented in the literature are adopted to inter-play with the proposed heuristic operator inside the EA general framework. To assess the performance of the EA when coupled with the proposed heuristic operator, the well known Saccaromycaes Cerevisiae yeast PPI network and one reference set of benchmark complexes created from MIPS are used in the experiments. The results prove the positive impact of the heuristic operator to harness the strength of almost all adopted EA models.

Keywords: Complex detection, evolutionary algorithm, heuristic operator, PPI networks.

أستراتيجية أرشادية لتحسين كشف المركبات في الشبكات البروتينية التفاعلية والمعتمد على الخوارزمية التطورية

قصي زهير عبدالله*، براء علي عطية

قسم الحاسوب ، كلية العلوم ، جامعة بغداد ، بغداد ، العراق

الخلاصة

     واحدة من أهم المشاكل والتي جذبت حديثا العديد من الابحاث في مجال الشبكات البروتينية التفاعلية (PPI) هي مشكلة كشف المركبات. ثبت هذه المشكلة بأنها صعبة للغاية, وحديثا تم أثبات بأن مجال الخوارزميات التطورية (EAs) له نتائج ايجابية. في هذا البحث تم أستحداث عامل ارشادي, يدعى تجاذب وتنافر البروتين الى المركب البروتيني  وقد صممت خصيصا لمشكلة اكتشاف المركبات البروتينية ولأجل تمكين خوارزمية ال EA لتحسين قدرته الاكتشافية. صمم العامل الارشادي المقترح لغرض تصفية أو صقل هيكلية المركب البروتيني وذلك بمحاولة شطره الى اثنين من المركبات البروتينية، يميز كل واحد منها عن طريق بروتين جوهري. وعلى هذا الأساس يتم أعادة توزيع بقية بروتينات المركب الأصلي غير المصقول، كل بروتين حسب تجاذبه مع أحدى من البروتينات الجوهرية المستخلصة وتنافره من الآخر. تم في هذا البحث أيضا أعتماد النماذج الرياضية للخوارزمية التطورية والخاصة باكتشاف المركبات البروتينية والموجودة في الادبيات وتوضيف التعاون المتبادل بينها وبين العامل الارشادي المقترح بداخل الاطار العام التابع الى (EA). وعلى هذا الأساس تم تقييم اداء الخوارزمية التطورية عندما أرتباطها بالعامل الارشادي المقترح, مع استخدام شبكة البروتين التفاعلية  (Saccaromycaes Cerevisiae yeast) ومصدر واحد للمركبات تم اناشاؤه من قبل (MIPS) في التجارب. النتائج اثبتت التاثير الايجابي للعامل الارشادي لاضهار قوة أغلب النماذج الرياضية للخوارزمية التطورية.




alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.