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

الهام مهدی­پور و محمد قاسم­زاده^*

ایران، یزد، دانشگاه یزد، دانشکده مهندسی کامپیوتر

تاریخ دریافت: 25/05/1399          تاریخ پذیرش: 07/07/1399

چکیده

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

واژه­های کلیدی: الگوریتم­های فراابتکاری، تعامل پروتئین-پروتئین، تطبیق گراف، زیرگراف ایزومورف، همترازی شبکه.

* نویسنده مسئول، تلفن: 31232359-035 ، پست الکترونیکی: m.ghasemzadeh@yazd.ac.ir

مقدمه

یکی از مشکلات جدی در مطالعات زیستی، بکارگیری داده­های زیستی در حجم­های انبوه است (3). الگوریتم‌های جستجو یکی از شاخه­های مهم در تحقیقات و بهینه­سازی هستند که بعلت بزرگتر و پچیده­تر شدن مسائل، نیاز به روش­های جستجوی کارآمدتر، بیشتر احساس می­شود. الگوریتم‌های فراابتکاری الهام‌گرفته از طبیعت هستند که در حل مسائل بهینه‌سازی دشوار بسیار کارآمد عمل می‌کنند.

هنگامی که اندازه مسئله بزرگ باشد، استفاده از روش‌های جستجوی ناآگاهانه میسر نخواهد بود. چرا که در این موارد، دامنه مسئله چنان بزرگ می‌باشد که رسیدن به جواب مسئله در مدت زمان قابل قبول با استفاده از این روش­های جستجو غیر ممکن خواهد بود. از این رو نیاز به روش­هایی داریم که بتواند در بخش­های مختلف فضای داده جستجو را انجام دهد. جستجوی فراابتکاری نام خانواده‌ای از الگوریتم­های جستجوی آگاهانه است که  از یک پدیده­ی طبیعی، بعنوان مدل برای بهینه سازی کاوش هوشمندانه فضای جستجوی داده‌های بسیار بزرگ در مسائل  پیچیده استفاده می­شود.

همترازی شبکه­های زیستی (Biological network alignment) یکی از مسائل دشواری می‌باشد که توجه محققین کامپیوتر، زیست‌شناسی و بیوانفورماتیک را به خود جلب کرده است. شبکه­ زیستی به شبکه­ای گفته می­شود که در مورد سیستم‌های زیستی مورد استفاده قرار می­گیرد. یکی از این شبکه­های زیستی، شبکه­های مبتنی بر میانکنش پروتئین-پروتئین (PPI= Protein-Protein Interaction) هستند؛ که از پروتئین­ها و ارتباط بین آن­ها تشکیل شدند.

از دیدگاه شیمی، پروتئین ترتیب خطی از اسیدآمینه­ها است که زنجیره پلی­پپتید هم نامیده می­شود (22). پروتئین­ها می­توانند باتوجه به وجود ساختارهای مکمل و ویژگی­های فیزیکی اسیدآمینه­ها به یکدیگر متصل شده و ساختارهای دسته­جمعی پیچیده­ای از پروتئین­ها را تشکیل دهند. تعاملات بسیار پروتئین‌ها داخل یک سلول با یکدیگر شبکه تعاملی پروتئین‌ها را تشکیل می‌دهد که در این شبکه گره­ها بیانگر پروتئین­ها و یال‌ها بیانگر تعاملی یا ارتباطی است که پروتئین­ها برقرار می­کنند.

تحقیقات زیادی بر روی تعیین مشترکات و انتقال حاشیه­نویسی بین شبکه­های PPI گونه­های مختلف متمرکز شده­اند که اغلب توسط همترازی شبکه انجام می‌شود (22). هدف از همترازی شبکه، شناسایی نگاشت (Mapping) بین پروتئین­ها در شبکه PPI است که می‌توانند بیانگر شباهت­های  توپولوژی، عملکردی، و نواحی حفاظت شده تکاملی در شبکه­های PPI باشند. الگوریتمی که این نگاشت را شناسایی می­کند، همترازکننده (Aligner) نامیده می‌شود. همترازی شبکه­ها باعث کشف اطلاعات ارزشمندی همچون مسیرهای حفاظت شده تکاملی و پیچیدگی‌های پروتئین شده است.

عملکرد بسیاری از پروتئین­ها بصورت کامل شناسایی نشده است (22)، که بدلیل این مسئله چالش­های شناسایی نقش آنها در فرآیند­های زیستی و بیماری­ها  مشکلاتی ایجاد می‌نماید. بنابراین، این فرآیند­ها و بیماری­ها بصورت آزمایشی در ارگانیسم‌های مدل، مانند مخمر و موش مورد بررسی قرار می­گیرند و دانش مربوطه از موجودات مدل با استفاده از شباهت‌های شبکه به انسان تعمیم داده می­شود (22). لذا همترازی با کمک به انتقال اطلاعات عملکردی بین گونه‌های مختلف، به نوبه خود برای پیش­بینی مکانیزم‌های بیماری انسان و یا پیش­بینی فرآیند پیری انسان مورد  استفاده قرار می‌گیرد(11).

در این پژوهش، کارآمدی الگوریتم‌های فراابتکاری در حل سریع و بهینه مسئله همترازی بر شبکه­های مبتنی بر میانکنش پروتئین-پروتئین مورد بررسی قرار داده می‌شود. همچنین در این پژوهش به سوالات زیر پاسخ داده می‌شود: 1) کدام روش همترازی شبکه را دانشمندان زیست­شناسی استفاده می­کنند؟ 2) چگونه می­توان دو همترازی متفاوت را مقایسه نمود؟ 3) چگونه کیفیت همترازی را اندازه­گیری نماییم؟

همترازی شبکه: همترازی شبکه به معنای یافتن بهترین راه برای متناظر نمودن یک شبکه درون شبکه دیگر است. این امر در چندین حوزه شامل تطبیق هستی‌شناسی (Ontology)، شناسایی الگو، پردازش زبان و شبکه‌های اجتماعی کاربرد دارد (25). بنابراین هدف همترازی شبکه به میزان زیادی به محتوای شبکه بستگی دارد. روش­های گوناگونی جهت همترازی شبکه وجود دارد. این تنوع به واسطه پیچیدگی محاسبات همترازی شبکه است (13).

تعاریف اولیه: شبکه یا گراف، زوج مرتب  است که V مجموعه گره­ها و E مجموعه یال­ها است که برخی گره‌های V را به یکدیگر متصل می­کند. تعداد شبکه­های ممکن با n گره برابر می­باشد، این مقدار نمایی باعث می­شود دسته­بندی شبکه و مسئله تطبیق آن از نظر محاسباتی دشوار باشند.

مسئله تطبیق شبکه به تئوری گراف و مسئله زیرگراف ایزومورف تعمیم می­یابد، و این پرسش را مطرح می‌نماید که آیا شبکه  زیرگراف دقیقی از شبکه  هست یا خیر. ثابت شده است که این مسئله جزء «اِن پی-کامل» محسوب می شود به این معنی که راه­حل کارآمد و چندجمله­ای ندارد. همچنین ثابت شده است که مسئله تطبیق شبکه مسئله «اِن پی-سخت» است (22،16). بنابراین همترازی شبکه، کلی­تر از یافتن مناسب­ترین زیرشبکه N₁ درون N₂ است حتی اگر N₁ زیرگرافی دقیقی از N₂  نباشد (22).

همترازی شبکه دربرگیرنده دو بحث اصلی است: همترازی موضعی (Local alignment) و همترازی سراسری (Global alignment).

هدف اصلی همترازی موضعی این است که نواحی کوچک دقیقاً همتراز شوند (13). در مقابل هدف همترازی شبکه سراسری تولید نگاشت یک به یک بین گره­های دو شبکه است. اکثر تحقیقات اخیر بر روی همترازی شبکه سراسری متمرکز شده­اند (13). هدف همترازی سراسری این است که نگاشتی از پروتئین‌های شبکه کوچکتر به پروتئین­های شبکه بزرگتر پیدا شود. بطور مرسوم، بین دو شبکه PPI،  و  با فرض ، همترازی f، نگاشت بین گره­های V₁ و گره­های V₂ است:

(1)                                                

بطوریکه  و .

در همترازی موضعی،  و  زیرمجموعه­های کوچک متناظر با مشابه‌ترین گره­ها در شبکه­ها هستند (شکل1، قسمت الف)؛ در حالی که هدف همترازی سراسری، همترازی همه گره­های V₁ است (شکل 1، قسمت ب). از این رو، همترازی موضعی نگاشت‌های چند-به-چند تولید می­کند یعنی یک گره از  می‌تواند به چندین گره در  نگاشت ­شود و برعکس؛ همترازی سراسری نگاشت‌های یک-به-یک تولید می­کند یعنی همترازی دوطرفه بین  و (22). شکل1 تفاوت بین همترازی موضعی و سراسری را نشان می‌دهد. همان­­گونه که در شکل1 قسمت الف مشاهده می­شود در همترازی موضعی، یک بخش از شبکه اول می­تواند به چندین بخش از شبکه دوم نگاشت شود؛ اما در همترازی سراسری همانند شکل 1 قسمت ب، کل یا بخشی از شبکه اول، فقط به یک بخش از شبکه دوم نگاشت می‌شود.

شکل 1- همترازی شبکه، الف: شبکه همترازی موضعی ، ب: شبکه همترازی سراسری

بدلیل «اِن پی-کامل» بودن مسئله زیرگراف ایزومورف، همترازکننده­های شبکه از توابع مکاشفه­ای (راه­حل­های تقریبی) استفاده می­کنند که برای تقریب راه­حل مسئله همترازی شبکه، تابع هدف و الگوریتم­های بهینه‌سازی متفاوتی دارند. برای کشف همترازی­هایی که تابع هدفشان ماکزیمم­سازی است، اغلب همترازکننده­ها یا به گراف‌های همترازی اعتماد می­کنند یا از تطبیق دوبخشی استفاده می‌کنند (22).

• گراف همترازی: بطور کلی، جستجو برای همترازی با امتیاز بالا متناظر با جستجو در گراف همترازی برای یافتن زیرگرافی با بزرگترین مجموع گره و وزن یال­ها است.
• گراف دوبخشی: گراف دوبخشی است اگر مجموعه گره­های آن به دو مجموعه V₁ و V₂ تقسیم شود، بطوریکه یال­ها (در E) فقط از گره‌های V₁ به گره‌های V₂ متصل باشند. وزن­ها می‌توانند متناظر با هزینه­های نگاشت گره به یال­ها نسبت داده شوند. بسیاری از همترازکننده‌های سراسری رویکردی دو مرحله‌ای را استفاده می­کنند: آن­ها ابتدا امتیاز نگاشت بین گره­های شبکه­های همترازشده را محاسبه نموده (شکل2-الف دو شبکه کاندید برای همترازی را نشان می­دهد)، سپس مدل همترازی‌شان را همانند وزن تطبیق دوبخشی ماکزیمم می‌نمایند (شکل2-ب).

شکل 2- تطبیق گراف دوبخشی، الف: شبکه­های ورودی، ب: محاسبه امتیاز نگاشت و ماکزیمم وزن تطبیق دوبخشی

همترازی چندگانه شبکه­ها: در همترازی چندگانه شبکه‌ها، چندین شبکه (مثلا k شبکه) بعنوان ورودی داده می­شود، و همترازی آن­ها به شکل گروه­بندی پروتئین­هایی که تکامل یافتند، یا بطور عملکردی در همه شبکه­ها حفاظت می‌شوند، اعمال می­گردد.

یکی از  راهکارهای پیشنهادی، همترازی شبکه چندگانه را مانند مسئله خوشه­بندی در گراف­های k-بخشی می‌بیند، بطوریکه خوشه­ها پروتئین­های مرتبط از نظر عملکرد یا تکامل را با یکدیگر در یک گروه قرار می­دهند (شکل 3) (22).

فرض کنید مجموعه k شبکه ورودی PPI بصورت  باشد. تطبیق­های ممکن بین پروتئین­های k شبکه ورودی در گراف k-بخشی  نمایش داده می­شود، بطوریکه یال­ها در E گره­های شبکه‌های متفاوت را به یکدیگر متصل می­کنند و وزن مرتبط با آن­ها بیانگر هزینه تطبیق دو گره است (22).

همان­طور که در شکل 3 مشاهده می­شود همترازی چندگانه شبکه­ها، همانند مسئله یافتن مجموعه­ای از خوشه­های در گراف G است که هر دو معیار شباهت عملکردی بین پروتئین­های همتراز شده و تعامل حفاظت ­شده را ماکزیمم نماید. بطوریکه شباهت عملکردی، شباهت درون خوشه­ای (ICS= Intra-Cluster Similarity) است که مجموع یال­های وزن­دار بین پروتئین‌های یک خوشه را بدست می‌آورد؛ و منظور از حفاظت تعامل، حفاظت بین خوشه­ای (ICC= Inter-Cluster Conservation) است که بیانگر تعداد تعامل­های حفاظت شده بین پروتئین‌های هر دو خوشه است.

شکل 3- شبکه چندگانه و خوشه­بندی گره­های همتراز شده

بنابراین همترازی چندگانه شبکه­ها، گراف G را برای ماکزیمم‌سازی خوشه­بندی C جستجو می­کند (22):

(2)                      α پارامتری است بین صفر و یک که تأثیر شباهت درون خوشه‌ای و بین خوشه­ای را بر روی فرایند همترازی گره متعادل می­سازد. همترازی سراسری است اگر خوشه­ها همپوشانی نداشته باشند و مجموعه خوشه­ها ماکزیمم باشد (یعنی هیچ خوشه اضافی را نتوان به C افزود)؛ در غیر این صورت همترازی موضعی است. همچنین اگر خوشه­ها در C شامل حداکثر یک پروتئین از هر شبکه باشند نگاشت یک به یک است، در غیر این صورت چند به چند است. هنگامی که α=1 است مسئله همترازی چندگانه شبکه‌ها به تطبیق k-بخشی کاهش می­یابد و نمی­تواند راه­حل بهینه داشته باشد، به همین دلیل تطبیق k-بخشی برای ، اِن پی- سخت است (22).

مواد و روشها

با توجه به وجود روش­های متفاوت همترازی شبکه، مسئله ارزیابی کیفیت همترازی تولید شده از اهمیت ویژه­ای برخوردار است. جدول 1 معیار­های امتیازدهی همترازی استاندارد را در سه گروه همترازی شبکه سراسری، موضعی و چندگانه نشان می­دهد.

جدول 1- معیارهای ارزیابی استاندارد

هدف همترازکننده موضعی یافتن مجموعه ماژول‌های همتراز شده متناظر با مسیرهای زیستی یا پیچیدگی­های پروتئین است؛ لذا بر اساس ارتباط زیستی همترازی‌هایش و بدون در نظر گرفتن ارتباط توپولوژی ارزیابی می‌شود. برخلاف همترازی موضعی، کیفیت همترازی سراسری از روی ارتباط توپولوژی ارزیابی می‌شود، زیرا ایده اصلی این است که نواحی همتراز شده از شبکه­ها باید الگوهای مشابهی داشته باشند. همترازی چندگانه شبکه­ها براساس توانایی در تولید خوشه‌هایی که کل شبکه­های ورودی را پوشش دهد و گروه‌بندی پروتئین­ها بر اساس شباهت عملکردی، ارزیابی می­شود.

اغلب تحقیقات در زمینه همترازی شبکه سراسری از معیارهای ارزیابی EC،S³ و FC استفاده نمودند. لذا در این پژوهش جهت مقایسه کارایی الگوریتم­های همترازی از معیارهای EC، FC و S³ استفاده شده است؛ زیرا معیارهای EC و S³ برای ارزیابی شباهت توپولوژی همترازی، و معیار FC برای ارزیابی شباهت عملکردی همترازی بکار می­رود. همچنین در حالی که EC بزرگ اجازه می­دهد یک شبکه کوچک خلوت به یک ناحیه چگال از شبکه بزرگتر نگاشت شود، یک ICS بزرگ اجازه می­دهد یک ناحیه خلوت از شبکه بزرگتر به یک ناحیه چگال از شبکه کوچکتر نگاشت شود.

امتیاز زیرساختار متقارن (S³) با مقایسه تعداد یال­های همتراز شده به تعداد یال­های شبکه کوچکتر و به تعداد یال­های ناحیه همتراز شده از شبکه بزرگتر، هر دو شبکه را بررسی می­کند (22).

پایگاه داده­­های زیادی برای مقایسه کارایی روش­های همترازی و تجزیه و تحلیل شبکه وجود دارد. پرکاربردترین مجموعه داده، شامل میانکنش­های پروتئین- پروتئین در گونه­های مختلف زیستی است؛ و عمومی­ترین جنبه تحقیقات در این زمینه بر روی تعامل شبکه­های پروتئین- پروتئین تمرکز دارد. جدول 2 فهرستی از پرکاربردترین پایگاه داده­های استفاده شده در تعامل شبکه­های پروتئین-پروتئین را شرح می‌دهد. در این تحقیق از پایگاه داده بیوگرید استفاده شده است.

اغلب تحقیقات در زمینه همترازی شبکه، همانند (16)، (25) و (32) نتایج تجربی خود را بر روی پایگاه داده بیوگرید و پنج گونه زیستی انسان، موش، کرم، مخمر و مگس میوه تست و بررسی نمودند. برخی تحقیقات نیز همانند (12) و (17) این پنج گونه زیستی را از پایگاه داده InAct و Isobase دریافت نمودند. علت انتخاب این گونه­های زیستی وجود تنوع در میزان پیچیدگی شبکه تعاملی پروتئین­های این موجودات است.

اعمال و اجرای الگوریتم­های همترازی شبکه، نیازمند پاکسازی و آماده­سازی مجموعه داده است. به عنوان مثال مجموعه داده بیوگرید شامل اطلاعات زیادی است. هر سطر بیانگر تعامل بین دو پروتئین است. از میان این اطلاعات، برای همترازی شبکه صرفا به پارامترهای شناسه گره­ها یا پروتئین­های موجود در هر سطر نیاز است. امتیاز BLAST یا شباهت توالی موجود بین پروتئین­ها را باید از روی هستی­شناسی ژن (Gene Ontology) دریافت نمود (27). سپس مجموعه داده­ای با سه ستون بدست می­آید که ستون اول بیانگر شناسه پروتئین اول، ستون دوم بیانگر شناسه پروتئین دوم و ستون سوم بیانگر امتیاز BLAST بین دو پروتئین است. در این بین برخی از محققین، ستون سوم را حذف می‌کنند و در میان کدنویسی امتیاز BLAST را محاسبه می­نمایند. پایگاه داده Isobase مجموعه داده‌های بیوگرید را آماده استفاده کاربر نموده و امتیاز BLAST را نیز درج نموده است؛ مزیت این پایگاه داده استفاده آسان جهت انجام تست­های اولیه است و ضعف آن عدم بروزرسانی پس از سال 2014 است، در حالی که دیگر پایگاه داده­های موجود در جدول 2 بروزرسانی می­شوند.

تأثیر الگوریتم­های فراابتکاری در همترازی شبکه: برای دو شبکه ورودی G₁ و G₂، مسئله یافتن همترازی بین دو شبکه متناظر با جستجو برای یک نگاشت بین گره‌های G₁ و گره‌های G₂ است که تابع هزینه داده شده (کیفیت همترازی) را ماکزیمم می­سازد.

جدول 2- فهرست مجموعه داده­های استاندارد

برای تولید همترازی، همترازکننده­ها از یک تابع هدف برای محاسبه امتیاز همترازی استفاده می­کنند. در حالی که این تابع در همترازکننده­ها متفاوت است اما می­توان آن را به شکل کلی زیر نوشت (22):

(3)                      

بطوریکه  امتیاز نگاشت یک گره از V₁ به یک گره در V₂ است، و  امتیاز نگاشت یک یال از E₁ به یک یال از E₂ است.

در مسئله همترازی اندازه فضای جستجو بزرگ است، زیرا همه نگاشت‌های بین گره‌های شبکه­های مورد مقایسه را در برمی­گیرد. عدم سازگاری محاسباتی مسئله که ناشی از «اِن پی-کامل» بودن مسئله زیرگراف­های ایزومورف است، باعث می‌شود برای حل آن نیاز به توسعه روش‌های فراابتکاری (نظریه­های تقریبی) داشته باشیم.

بین همترازی موضعی و سراسری ارتباط واضحی وجود دارد. برای مثال، هدف هر دو یافتن شباهت­های توپولوژی و عملکردی بین شبکه­های مورد مقایسه است تا دانش زیستی گونه­های مورد مطالعه را به گونه­هایی که کمتر مطالعه شده­اند تعمیم دهند (13). با این حال، محققان در این دو زیرمجموعه الگوریتم‌های مستقلی ارائه نمودند. در این راستا می­توان به الگوریتم­های همترازی موضعی PathBLAST (19) و AlignMCL (28)؛ الگوریتم­های همترازی سراسری مانند IsoRank (33)، MAGNA (32) و SANA (16، 25) اشاره نمود. الگوریتم PathBLAST به کشف مسیرهای سلولی بر اساس امتیاز BLAST یا شباهت توالی می­پردازد و شباهت توپولوژی را نیز در نظر می­گیرد. الگوریتم AlignMCL با استفاده از خوشه­بندی مارکوف سعی در یافتن همترازی­های موضعی دارد. الگوریتم IsoRank بر پایه شباهت توپولوژی و محاسبه امتیاز PageRank عمل می­کند. به همین ترتیب هر یک از روش متفاوتی بهره می­برند؛ در نتیجه، بسیاری از الگوریتم­های همترازی موضعی و بسیاری از الگوریتم­های همترازی سراسری وجود دارد که بر فرضیه­های متفاوت تکیه می­کنند و از نظریه­های متفاوت استفاده می­کنند تا توابع هزینه­های متفاوتی را به حداکثر برسانند.

بعنوان مثال، بسیاری از الگوریتم­ها سعی می­کنند برخی از توابع هزینه را بطور عمده بر اساس توپولوژی، بهینه‌سازی کنند، در حالی که بسیاری دیگر به منظور افزایش ارتباطات کاربردی همترازی­ها طراحی شده­اند. بنابراین، مقایسه مستقیم یک روش همترازی موضعی و یک روش همترازی سراسری، بی­اهمیت است؛ بلکه هر یک با روش‌های دسته خود مقایسه می­شوند. بنابراین پرسش این است که کدام یک از آن­ها را استفاده کنیم: همترازی موضعی، همترازی سراسری یا نظریه ترکیبی که با هر دو سازگار باشد. سازگاری ممکن بین این دو جنبه همترازی شبکه یک مسئله باز برای تحقیق است که باید در آینده بطور عمیق بررسی شود (13).

اهمیت روش­های تطبیق گراف، تطبیق شبکه و همترازی شبکه بیانگر این حقیقت است که این پدیده می­تواند مفاهیم ریاضی را به شکلی که امروزه علم شبکه نامیده می­شود نمایش دهد. با بیان تفاوت­های کمی در شبکه­ها بکارگیری بسیاری از استانداردهای روش­های آماری و یادگیری ماشین امکان­پذیر است (10).

در این پژوهش الگوریتم­های همترازی شبکه­های زیستی را بر اساس نوع همترازی  به چهار دسته کلی همترازی سراسری، همترازی موضعی، همترازی چندگانه شبکه­ها، و یکپارچه‌سازی همترازی تقسیم شده­اند.

در میان الگوریتم­های همترازی سراسری، MAGNA (32)، MAGNA++ (35) و الگوریتم برنامه­سازی پویای DynaMAGNA++ (36) برای همترازی شبکه از الگوریتم ژنتیک استفاده می­کنند.

همچنین روش MeAlign (12) و OptnetAlign (8) از الگوریتم میمتیک استفاده می‌کنند که ترکیبی از الگوریتم ژنتیک با یک پالایش جستجوی محلی است. الگوریتم جستجوی SANA همترازی شبکه را با استفاده از الگوریتم تبرید شبیه­سازی شده انجام می­دهد (25)، (16). همترازکننده PSONA مبتنی بر الگوریتم فراابتکاری بهینه­سازی توده ذرات است (17).  

الگوریتم­های همترازی موضعی شبکه، برای همترازی از استراتژی انتخاب و توسعه (4)، (31)؛ فاصله ویرایشی گراف (20)، روش­های فراابتکاری بهمراه روش­های حریصانه (Greedy methods) (7)، (9)، (14)، (23)، (30)، (34) استفاده می­کنند.

روش همترازی سراسری GEDEVO-M (18) بر پایه فاصله ویرایشی گراف (Graph Edit Distance (GED)) عمل می­کند. این روش با استفاده از الگوریتم ژنتیک بدنبال همترازی با کمترین مجموع GED از بین همه جفت همترازی­های شبکه است.

روش MultiMAGNA++ (37) برای همترازی شبکه چندگانه سراسری ارائه شده و توسعه‌یافته‌ی روش MAGNA++ است. این روش از الگوریتم ژنتیک برای تولید همترازی‌های شبکه چندگانه یک به یک استفاده می‌کند که یال حفاظت شده بین شبکه­های همتراز شده را ماکزیمم می­سازد.

الگوریتم ACOTS-MGA برای تطبیق سایت­های پیوند پروتئینی ارائه شده است که بر اساس الگوی میمتیک و با استفاده از روش بهینه­سازی کلونی مورچگان (ACO) مجموعه­ای راه­حل را ایجاد می­کند، سپس بهترین راه‌حل برای پیاده­سازی را با جستجوی ممنوعه انتخاب می‌کند تا کیفیت راه­حل را بهبود دهد (15).

همان‌طور که همترازی موضعی شبکه کیفیت عملکردی بالا و کیفیت همترازی توپولوژیکی پایینی دارد، همترازی سراسری شبکه نیز کیفیت توپولوژیکی بالا و کیفیت همترازی عملکردی پایینی دارد. نظریه‌ IGLOO (26) مؤلفه­های الگوریتمی همترازی موضعی و سراسری شبکه را با امید به ترکیب دو نوع همترازی شبکه، یکپارچه می‌سازد. ابزار Ulign (24) هشت روش همترازی را بطور همزمان برای نگاشت و انتقال در میان همه پروتئین‌های شبکه­های PPI استفاده می‌کند، تا بهترین همترازی را انتخاب کند. همترازکننده محلی سراسری GLAlign روشی است که کارایی همترازکننده­های شبکه محلی را با بهره‌گیری از همترازی سراسری بهبود می­بخشد (29).

نتایج

نتایج حاصل از اجرا نشان داد که روش­های همترازی شبکه­ای که از الگوریتم­های فراابتکاری استفاده می­کنند دارای ثبات رفتاری بیشتری نسبت به سایر روش­ها هستند. بدین معنی که با بزرگتر شدن و یا پیچیده­تر شدن ساختار شبکه میزان کیفیت همترازی کاهش چندانی ندارد. این امر با بررسی عملکرد الگوریتم­های همترازی شبکه و محاسبه معیارهای ارزیابی بدست آمد که در ادامه شرح آن و نحوه مقایسه آورده شده است.  

در این تحقیق برای مقایسه عملکرد الگوریتم­های فراابتکاری با دیگر روش­های همترازی 15 الگوریتم معروف و پرکاربرد NATALIE (9)، GHOST (31)، SPINAL (4)، NETAL (30)، PISWAP (7)، HubAlign (14)، L-GRAAL (23)، OptNetAlign (8)، CytoGEDEVO (21)، MAGNA++ (35)، WAVE (34)، MeAlign (12)، SANA (16، 25)، PSONA (17) و ACOTS-MGA (15) انتخاب شده است.

از میان مجموعه داده‌های سطح زیستی (6) نسخه BIOGRID-3.5.170 (5) برگزیده شد که مشخصات هر یک از داده‌های منتخب مربوط به انسان، موش، کرم، مگس میوه و مخمر در جدول 3 آورده شده است.

جدول 3- ویژگی­های شبکه PPI از پنج گونه

دلیل انتخاب این پنج گونه، کاربرد بسیار زیاد آن­ها در اثبات کارایی الگوریتم­های همترازی شبکه است. شکل­های 4 تا 6 متناظراً معیارهای ارزیابی EC، FC و S³ الگوریتم­های مختلف را بر روی این پنج گونه نشان می­دهند.

در شکل 4 مشاهده می­شود که تقریبا در تمام الگوریتم­ها میزان درستی تشخیص یال یا صحت یال (EC) با بزرگ شدن شبکه­ها و افزایش پیچیدگی آن­ها کاهش می­یابد.

شکل 4- مقایسه معیار EC الگوریتم­های همترازی

بدیهی است تشخیص صحیح یال در گراف همترازی بمنزله تشخیص همترازی درست بین دو پروتئین یا گره متناظر در گراف است؛ لذا هر چقدر مقدار EC بیشتر باشد الگوریتم بهتر عمل کرده است.

بنابر شکل 4، الگوریتم GHOST که از استراتژی انتخاب و توسعه بهره می­برد دارای ثبات رفتاری بهتری نسبت به سایر الگوریتم­ها است. الگوریتم NETAL که از روش مکاشفه­ای استفاده می­کند در رتبه دوم قرار دارد؛ و پس از آن می­توان به الگوریتم­های PSONA و SANA که جزء روش­های فراابتکاری هستند اشاره نمود.

همان­طور که در شکل 5 مشاهده می­شود میزان تشخیص صحیح پروتئین­هایی با عملکرد مشابه یعنی معیار FC یا شباهت عملکردی الگوریتم­های مختلف با یکدیگر متفاوت است. در این میان، الگوریتم­های MeAlign، PSONA و SANA از بهترین قدرت تشخیص شباهت عملکردی بهره می­برند که همگی جزء روش­های فراابتکاری هستند.

شکل 5- مقایسه معیار FC الگوریتم­های همترازی

شکل 6 معیار S³ الگوریتم­های همترازی را مقایسه می‌کند. همان­گونه که ملاحظه می­شود در میان الگوریتم‌های مختلف، روش SANA از بیشترین پایداری و ثبات مقدار بهره می­برد. پس از آن می­توان به الگوریتم NETAL اشاره کرد که در برخی جفت گونه­ها مانند MM-CE و MM-DM بسیار خوب عمل کرده است. لازم به ذکر است که هر دو الگوریتم SANA و NETAL از روش فراابتکاری و مکاشفه­ای استفاده می‌‌کنند.

همان­طور که در شکل­های 4 تا 6 مشاهده می­شود هر یک از الگوریتم­ها بر روی یک یا چند مجموعه داده بهتر عمل می­کنند. الگوریتم­های فراابتکاری از جمله روش­های همترازی هستند که در اغلب موارد هر سه معیار EC، FC و S³ را ماکزیمم نمودند و این نشان از کارایی روش­های فراابتکاری است.

شکل 6- مقایسه معیار S³ الگوریتم­های همترازی

بحث

همان­طور که ذکر شد یکی از چالش­ها در تحقیقات زیستی، بکارگیری داده­های زیستی در حجم بالاست که نیازمند استفاده از روش­های محاسباتی و الگوریتم‌های هوشمند است (3). یکی از مجموعه داده­های حجیم، داده‌های حاصل از میانکنش­ پروتئین­ها است که نقش اساسی در فرآیندهای سلولی دارند (1). می­دانیم که روش­های محاسباتی جهت بررسی میانکنش دو پروتئین نیازمند استفاده از ساختار سه بعدی دو پروتئین هستند (2). اما در بخش قبل نشان داده شد که الگوریتم­های فراابتکاری با استفاده از ساختار شبکه­های زیستی، می­توانند نقش مؤثری در کشف همترازی­های موجود بین دو شبکه PPI داشته باشند. در این بخش جهت مقایسه بهتر، زمان اجرا و میزان مصرف حافظه الگوریتم­ها نیز با یکدیگر مقایسه شده است. شکل 7 زمان اجرای الگوریتم­های همترازی را برحسب ثانیه، دقیقه، ساعت، روز و سال نشان می‌دهد. بر اساس این مقایسه می­توان مشاهده کرد که الگوریتم­های NETAL، HubAlign و WAVE از کمترین زمان اجرا بهره می‌برند که از روش­های مکاشفه­ای استفاده نمودند و GHOST از بیشترین زمان اجرا بهره می­برد.

شکل 7- مقایسه زمان اجرای الگوریتم­های همترازی

لیکن این نتیجه به میزان پیچیدگی و تعداد تعامل پروتئین­ها در شبکه­های مورد بررسی وابسته است؛ لذا در شکل 7 میزان پیچیدگی شبکه­های هر الگوریتم بر اساس حداقل (بهترین حالت) و حداکثر (بدترین حالت) تعداد یال­ها و گره­ها آورده شده است. آنچه در شکل 7 حائز اهمیت می‌باشد این است که بدترین زمان اجرای الگوریتم­های همترازی سراسری MeAlign، SANA، PSONA و ACOTS-MGA که همگی جزء روش‌های فراابتکاری هستند برحسب دقیقه است؛ در حالی که بدترین زمان اجرای سایر الگوریتم­ها بر حسب ساعت و روز هستند؛ این یعنی الگوریتم­های فراابتکاری از نظر زمان اجرا نیز بهتر و سریع­تر از سایر الگوریتم­ها عمل می‌کنند. شکل 8 میزان مصرف حافظه RAM هر الگوریتم را نشان می‌دهد.

شکل 8- مقایسه مصرف حافظه الگوریتم­های همترازی

با توجه به شکل 8 کمترین میزان مصرف حافظه به الگوریتم‌های NETAL، HubAlign، MAGNA++، WAVE، MeAlign، SANA، PSONA و ACOTS-MGA برمی‌گردد که اغلب آن­ها از الگوریتم‌های فراابتکاری بهره می­برند. در شکل 8 بیشترین میزان مصرف حافظه مربوط به الگوریتم­های NATALIE، GHOST و PI-SWAP است که از روش­های ریاضی­ و حریصانه استفاده می­کنند.

در شکل 9 حداقل و حداکثر تعداد یال­ها و گره­هایی که محققین در الگوریتم­های همترازی خود استفاده کردند، نمایش داده شده است.

شکل 9- مقایسه حداقل و حداکثر تعداد گره­ها و یال­ها

بر اساس شکل 9 می­توان نتیجه گرفت که الگوریتم‌هایی مانند OptNetAlign و PI-SWAP بیشترین تعداد گره (24855 گره) و الگوریتم‌های MeAlign و PSONA شبکه‌هایی با حداقل تعداد گره (290 گره) و حداقل تعداد یال (242 یال) را بررسی می‌نمایند.

جدول 4- مقایسه مرتبه اجرای الگوریتم­های همترازی

الگوریتم‌های SANA و L-GRAAL نیز شبکه­هایی با بیشترین تعداد یال (110528 یال) را بررسی می­کنند. در این میان الگوریتم ACOTS-MGA حداقل 4 گراف و حداکثر 32 گراف را همزمان در نظر می‌گیرد.

مرتبه اجرایی برخی از الگوریتم­های همترازی در  جدول4 نشان داده شده است. در جدول 4، p اندازه جمعیت، N تعداد نسل­ها، V مجموعه رئوس، E مجموعه یال­ها، و M تعداد تکرار می­باشد.

بنابر مطالعات انجام شده می­توان الگوریتم­های موجود در شبکه همترازی سراسری (GNA= Global Network Alignment) و شبکه همترازی موضعی(LNA= Local Network Alignment)  را از دیدگاه سیستماتیک بررسی نمود. اگرچه هدف LNA یافتن ماژول­های حفاظت شده با عملکرد بالاست، ماژول‌های روش­های LNA موجود می‌توانند بخش کوچکی را پیدا کنند. به عبارت دیگر در حالی که هدف GNA یافتن کل نواحی شباهت توپولوژیکی بین شبکه‌های مورد مقایسه است، نواحی که روش‌های GNA موجود می‌توانند پیدا کنند معمولاً از نظر عملکرد حفاظتی ضعیف هستند (13).

از این رو محققین بررسی کردند که آیا ممکن است هر دو روش، نواحی حفاظت شده با توپولوژی بزرگ و عملکرد بالا از شباهت شبکه را پیدا کنند، که نه تنها اهداف کاربردی/ طراحی هر یک از روش­های LNA و GNA را برآورده کند بلکه بر معایب آن­ها نیز چیره شود (13)، (26).

آن­ها شواهدی ارائه کردند که: 1) ماژول­های کوچک حفاظت شده با عملکرد بالا از نواحی LNA موجود می‌توانند گسترش یابند تا کیفیت توپولوژیکی خود را بدون کاهش کیفیت عملکردی­شان بهبود بخشند. 2) نواحی بزرگ شباهت توپولوژیکی از روش­های GNA موجود بطور معمول کارایی معناداری ندارند اما می‌توانند به نواحی معنادار کاربردی معطوف شوند، که بدون کاهش کیفیت توپولوژیکی کیفیت عملکردی را بهبود می­بخشند.

چنین یکپارچه­سازی کارآمدی از LNA و GNA که هدف اصلی هر یک از آن­ها را همزمان حفظ می­کند، هر دو همترازی موضعی و سراسری را بهبود می­بخشد. از دیدگاه محققین هدف برد-برد به این صورت تعریف می‌شود که نواحی شبکه موضعی حفاظت شده عملکردی را پیدا نمایند و هدف آن‌ها یافتن نواحی شبکه سراسری حفاظت شده با امتیاز توپولوژیکی بالا است (13). تعادل بین اندازه ناحیه شبکه همتراز شده (کیفیت توپولوژیکی) مهم است و این کیفیت عملکردی ممکن است نیاز به تنظیم پارامترهای داده شده روش یکپارچه­سازی LNA-GNA داشته باشد.

علاوه بر ایده فوق چندین سؤال دیگر از دیدگاه عملی باقی می­ماند که بصورت زیر است: کدام روش را دانشمندان زیست­شناسی استفاده می­کنند؟ طبق ادبیات تحقیق می­توان گفت در حالی که LNA بطور کلی نمی‌تواند نواحی بزرگ مشابه را پوشش دهد، GNA قادر به بازیابی مسیرهای معنادار زیستی یا نمونه­های پروتئینی حفاظت شده تکاملی است. لذا اغلب دانشمندان همترازی سراسری را استفاده می­کنند. علاوه بر این، پاسخ سؤال فوق با ایده­های دیگر نیز مرتبط است: چگونه می‌توان دو همترازی متفاوت را مقایسه نمود؟ و چگونه کیفیت همترازی را اندازه­گیری نماییم؟ بر اساس تحقیقات، بخشی از این مسئله حل شده است و تا کنون معیارهای ارزیابی مختلفی تعریف شده است (جدول 1). بنابراین برای اندازه­گیـری کیفیت همتـرازی می­توان با توجـه به نوع

همترازی از معیارهای موجود در جدول 1 بهره برد.

برخی محققین روش­های GNA را بررسی کردند و معیار جدیدی برای کیفیت همترازی ارائه دادند. برخی از آن­ها روش­های LNA را بررسی نمودند و چارچوبی برای بهبود پایداری همترازی­های موضعی ایجاد کردند. اخیراً برخی تحقیقات در مورد یکپارچه‌سازی LNA و GNA بررسی کردند و روشی برای مقایسه بین آن­ها پیشنهاد دادند، همانند (24)، (26) و (29). لازم به ذکر است که مقایسه حتی در میان همترازی­های با نوع یکسان (یعنی LNA یا GNA) نیز پیچیده است، و بطور خاص مقایسه همترازی­هایی از کلاس­های متفاوت (یعنی LNA و GNA) سخت­تر است. بنابراین محققین معیارهای جدیدی از کیفیت همترازی ارائه دادند که بر روی هر دو GNA و LNA کار می­کند. لذا می­توان گفت جهت مقایسه دو همترازی با انواع متفاوت بهتر است از روش‌های یکپارچه­سازی (24)، (26)، و (29) بهره برد؛ و در صورت عدم امکان یکپارچه­سازی برای مقایسه کیفیت از معیارهای ارزیابی که در هر دو نوع همترازی، قابل محاسبه باشند، استفاده نمود.

 با گسترش تحقیقات و رشد روزافزون داده‌های زیستی، توسعه همترازکننده­ای مبتنی بر محاسبات ابری (Cloud Computing) که از فناوری­­ داده­های حجیم (Big Data) بهره ببرد؛ می‌تواند جزء کارهای آتی محققین قرار گیرد.

نتیجه‌گیری

بطور کلی نتایج آزمایشی و تحلیل­های نظری نشان می‌دهند که  استفاده از الگوریتم­های فراابتکاری از جمله الگوریتم­های ژنتیک، میمتیک، بهینه­سازی توده ذرات، تبرید شبیه­سازی شده و کلونی مورچگان نقش مؤثری در بهینه­سازی معیارهای ارزیابی همترازی شبکه، کاهش زمان اجرا و مصرف حافظه دارد. در این رابطه،  ایجاد روش­هایی برای یکپارچه­سازی همترازی سراسری و محلی، و ایجاد معیارهای استاندارد برای مقایسه عملکرد و کیفیت همترازی روش­های یکپارچه‌سازی، همچنان از زمینه­های تحقیقاتی باز و فعالی در حوزه همترازی شبکه به حساب می­آیند.