تاثیر الگوریتم‌های فراابتکاری در همترازی شبکه‌های مبتنی بر میانکنش پروتئین-پروتئین در پنج گونه زیستی

از طریق همترازی توالی ژنوم می‌توان دانش زیستی گونه‌های مختلف را به نواحی حفاظت شده‌ی توالی انتقال داد. به‌طور مشابه، از طریق همترازی شبکه زیستی، می‌توان دانش نواحی حفاظت شده‌ی شبکه‌های مولکولی را به نواحی مختلف حفاظت شده‌ی گونه‌های متفاوت انتقال داد. لذا با تکیه بر همترازی شبکه‌های زیستی می‌توان «همسانی مبتنی بر توالی» را به «همسانی مبتنی بر شبکه» تعمیم داد. کشف همترازی شبکه‌ها به جهت کاربردهای آن، مانند کشف داروهای جدید، ردیابی روند پیشرفت بیماری‌ها و یا پیش‌بینی رفتار کاربران در شبکه‌های اجتماعی، از اهمیت ویژه‌ای برخوردار است. در این رابطه، چالش اصلی این است که یافتن همترازی‌های موجود در دو شبکه، یک مسئله‌ی از مرتبه‌ی «اِن پی-سخت» است. در چنین وضعیتی از راه‌حل‌های تقریبی مانند الگوریتم‌های فراابتکاری که نسبتاً سریع هستند، بهره می‌گیریم. بخش اصلی این پژوهش، مقایسه الگوریتم‌های همترازی شبکه از دیدگاه معیارهای ارزیابی مربوطه، زمان اجرا، میزان مصرف حافظه و میزان پیچیدگی شبکه‌های مورد تست می‌باشد. نتایج آزمایشی از اجرای جدیدترین و مشهورترین الگوریتم‌های مرتبط بر روی مجموعه داده‌ی شبکه‌های زیستی بیوگرید به‌دست‌آمده‌اند. نتایج پیاده‌سازی و ارزیابی حاکی از آن است که با بهره‌گیری از الگوریتم‌های فراابتکاری ژنتیک، میمتیک، بهینه‌سازی توده ذرات، تبرید شبیه‌سازی شده و کلونی مورچگان می‌توان به نتایج ارزشمندی دست یافت. روش‌های یادشده با به‌کارگیری توابع مکاشفه‌ای مناسب، تنها بخش‌های کوچکی از داده‌های قابل جستجو را مورد بررسی قرار می‌دهند، لذا غالباً موفق به کشف پاسخ بهینه و یا قابل‌قبول در زمان کوتاهی می‌شوند.

effects of meta-heuristic algorithms in protein-protein interaction networks alignment in five biological species

the biological knowledge of different species can be transferred to the conserved sequence regions via genomic sequence alignment. similarly, through biological network alignment, knowledge of the conserved regions of molecular networks can be transferred to different conserved regions of different species. therefore, relying on biological network alignment, we can extend the traditional &sequence-based homology& concept to the new concept of &network-based homology&. discovery of networks alignment is especially important because of its applications, such as discovering new drugs, tracking disease progression, or predicting users’ behavior on social networks. in this regard, the main challenge is that the problem of finding the alignments in two graphs is np-hard. in situations like this, we can use the relatively fast meta-heuristic algorithms to find some acceptable approximate solutions. the main contribution of this research consists of conducting a comparison over the network alignment algorithms, based on the respective evaluation criteria, execution time, memory consumption and complexity of the testing networks. the experimental results are obtained from running the relevant algorithms on the well-known biogrid dataset. evaluations indicate that among other methods, using genetic algorithm, memetic, particle swarm optimization, simulated annealing and the ant colony, could yield more valuable results. the named methods apply appropriate heuristics to generate and investigate only a very small subset of the whole search space with the highest probability of holding a solution; therefore, they often can find the optimal solution or some acceptable solutions in a relatively short time.