Document Type : Research Paper
Authors
Computer Engineering Department, Yazd University, Yazd, Iran.
Abstract
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.
Keywords
Main Subjects
تأثیر الگوریتمهای فراابتکاری در همترازی شبکههای مبتنی بر میانکنش پروتئین-پروتئین در پنج گونه زیستی
الهام مهدیپور و محمد قاسمزاده*
ایران، یزد، دانشگاه یزد، دانشکده مهندسی کامپیوتر
تاریخ دریافت: 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). بنابراین همترازی شبکه، کلیتر از یافتن مناسبترین زیرشبکه N1 درون N2 است حتی اگر N1 زیرگرافی دقیقی از N2 نباشد (22).
همترازی شبکه دربرگیرنده دو بحث اصلی است: همترازی موضعی (Local alignment) و همترازی سراسری (Global alignment).
هدف اصلی همترازی موضعی این است که نواحی کوچک دقیقاً همتراز شوند (13). در مقابل هدف همترازی شبکه سراسری تولید نگاشت یک به یک بین گرههای دو شبکه است. اکثر تحقیقات اخیر بر روی همترازی شبکه سراسری متمرکز شدهاند (13). هدف همترازی سراسری این است که نگاشتی از پروتئینهای شبکه کوچکتر به پروتئینهای شبکه بزرگتر پیدا شود. بطور مرسوم، بین دو شبکه PPI، و با فرض ، همترازی f، نگاشت بین گرههای V1 و گرههای V2 است:
(1)
بطوریکه و .
در همترازی موضعی، و زیرمجموعههای کوچک متناظر با مشابهترین گرهها در شبکهها هستند (شکل1، قسمت الف)؛ در حالی که هدف همترازی سراسری، همترازی همه گرههای V1 است (شکل 1، قسمت ب). از این رو، همترازی موضعی نگاشتهای چند-به-چند تولید میکند یعنی یک گره از میتواند به چندین گره در نگاشت شود و برعکس؛ همترازی سراسری نگاشتهای یک-به-یک تولید میکند یعنی همترازی دوطرفه بین و (22). شکل1 تفاوت بین همترازی موضعی و سراسری را نشان میدهد. همانگونه که در شکل1 قسمت الف مشاهده میشود در همترازی موضعی، یک بخش از شبکه اول میتواند به چندین بخش از شبکه دوم نگاشت شود؛ اما در همترازی سراسری همانند شکل 1 قسمت ب، کل یا بخشی از شبکه اول، فقط به یک بخش از شبکه دوم نگاشت میشود.
شکل 1- همترازی شبکه، الف: شبکه همترازی موضعی ، ب: شبکه همترازی سراسری
بدلیل «اِن پی-کامل» بودن مسئله زیرگراف ایزومورف، همترازکنندههای شبکه از توابع مکاشفهای (راهحلهای تقریبی) استفاده میکنند که برای تقریب راهحل مسئله همترازی شبکه، تابع هدف و الگوریتمهای بهینهسازی متفاوتی دارند. برای کشف همترازیهایی که تابع هدفشان ماکزیممسازی است، اغلب همترازکنندهها یا به گرافهای همترازی اعتماد میکنند یا از تطبیق دوبخشی استفاده میکنند (22).
شکل 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- معیارهای ارزیابی استاندارد
نوع همترازی |
نام معیار امتیازدهی |
شرح |
فرمول محاسبه |
موضعی |
k-correctness (22) |
وجود حداقل k حاشیهنویسی مشترک بین دو پروتئین p1 و p2 با حاشیهنویسی s1 و s2 |
|
Functional consistency (22) |
درصد حاشیهنویسیهای مشترک بین دو پروتئین |
||
Agreement with reference modules |
امتیازدهی بر پایه صحت و فراخوانی مجدد که با استفاده از F-score یکپارچه میشود (22). |
||
سراسری |
Node correctness |
درصد گرههای همتراز شدهای است که بدرستی مطابق با همترازی مرجع نگاشت شدند (20). |
|
Node coverage (22) |
اندازهگیری تعداد گرههای نرمال شده در بازه [0, 1] نگاشت شده به تعداد گرههای شبکه کوچکتر |
||
Edge correctness |
درصد تعاملهایی از شبکه کوچکتر که همتراز با یالهای شبکه بزرگتر هستند (20). |
||
Induced conserved sub-structure score |
درصد تعاملهایی از ناحیه همتراز شده شبکه بزرگتر که با تعاملهای شبکه کوچکتر همتراز شدند (31). |
||
Symmetric sub-structure score |
تعداد یالهای همتراز شده به تعداد یالهای شبکه کوچکتر و بزرگتر (22) |
||
Size of the largest common connected component |
اندازه بزرگترین مؤلفه متصل مشترک (LCC)، LCC بزرگتر یعنی همترازی شامل میزان بزرگتری از ساختار متصل مشترک بین دو شبکه است (31). |
||
چندگانه |
K-coverage |
تعداد خوشههای همترازی است که شامل پروتئینهایی از شبکه هستند (22). |
|
Exact cluster ratio |
درصد همه پروتئینهایی که در خوشههای واقعی قرار دارند، بیان شود (22). |
||
Mean normalized entropy (22) |
میانگین آنتروپی نرمال شده (میانگین NE)، pi کسری از پروتئینهایی که در c با عبارت ti حاشیهنویسی شدند و d تعداد عبارات متفاوتی که پروتئینها را در c حاشیهنویسی میکنند. |
هدف همترازکننده موضعی یافتن مجموعه ماژولهای همتراز شده متناظر با مسیرهای زیستی یا پیچیدگیهای پروتئین است؛ لذا بر اساس ارتباط زیستی همترازیهایش و بدون در نظر گرفتن ارتباط توپولوژی ارزیابی میشود. برخلاف همترازی موضعی، کیفیت همترازی سراسری از روی ارتباط توپولوژی ارزیابی میشود، زیرا ایده اصلی این است که نواحی همتراز شده از شبکهها باید الگوهای مشابهی داشته باشند. همترازی چندگانه شبکهها براساس توانایی در تولید خوشههایی که کل شبکههای ورودی را پوشش دهد و گروهبندی پروتئینها بر اساس شباهت عملکردی، ارزیابی میشود.
اغلب تحقیقات در زمینه همترازی شبکه سراسری از معیارهای ارزیابی EC،S3 و FC استفاده نمودند. لذا در این پژوهش جهت مقایسه کارایی الگوریتمهای همترازی از معیارهای EC، FC و S3 استفاده شده است؛ زیرا معیارهای EC و S3 برای ارزیابی شباهت توپولوژی همترازی، و معیار FC برای ارزیابی شباهت عملکردی همترازی بکار میرود. همچنین در حالی که EC بزرگ اجازه میدهد یک شبکه کوچک خلوت به یک ناحیه چگال از شبکه بزرگتر نگاشت شود، یک ICS بزرگ اجازه میدهد یک ناحیه خلوت از شبکه بزرگتر به یک ناحیه چگال از شبکه کوچکتر نگاشت شود.
امتیاز زیرساختار متقارن (S3) با مقایسه تعداد یالهای همتراز شده به تعداد یالهای شبکه کوچکتر و به تعداد یالهای ناحیه همتراز شده از شبکه بزرگتر، هر دو شبکه را بررسی میکند (22).
پایگاه دادههای زیادی برای مقایسه کارایی روشهای همترازی و تجزیه و تحلیل شبکه وجود دارد. پرکاربردترین مجموعه داده، شامل میانکنشهای پروتئین- پروتئین در گونههای مختلف زیستی است؛ و عمومیترین جنبه تحقیقات در این زمینه بر روی تعامل شبکههای پروتئین- پروتئین تمرکز دارد. جدول 2 فهرستی از پرکاربردترین پایگاه دادههای استفاده شده در تعامل شبکههای پروتئین-پروتئین را شرح میدهد. در این تحقیق از پایگاه داده بیوگرید استفاده شده است.
اغلب تحقیقات در زمینه همترازی شبکه، همانند (16)، (25) و (32) نتایج تجربی خود را بر روی پایگاه داده بیوگرید و پنج گونه زیستی انسان، موش، کرم، مخمر و مگس میوه تست و بررسی نمودند. برخی تحقیقات نیز همانند (12) و (17) این پنج گونه زیستی را از پایگاه داده InAct و Isobase دریافت نمودند. علت انتخاب این گونههای زیستی وجود تنوع در میزان پیچیدگی شبکه تعاملی پروتئینهای این موجودات است.
اعمال و اجرای الگوریتمهای همترازی شبکه، نیازمند پاکسازی و آمادهسازی مجموعه داده است. به عنوان مثال مجموعه داده بیوگرید شامل اطلاعات زیادی است. هر سطر بیانگر تعامل بین دو پروتئین است. از میان این اطلاعات، برای همترازی شبکه صرفا به پارامترهای شناسه گرهها یا پروتئینهای موجود در هر سطر نیاز است. امتیاز BLAST یا شباهت توالی موجود بین پروتئینها را باید از روی هستیشناسی ژن (Gene Ontology) دریافت نمود (27). سپس مجموعه دادهای با سه ستون بدست میآید که ستون اول بیانگر شناسه پروتئین اول، ستون دوم بیانگر شناسه پروتئین دوم و ستون سوم بیانگر امتیاز BLAST بین دو پروتئین است. در این بین برخی از محققین، ستون سوم را حذف میکنند و در میان کدنویسی امتیاز BLAST را محاسبه مینمایند. پایگاه داده Isobase مجموعه دادههای بیوگرید را آماده استفاده کاربر نموده و امتیاز BLAST را نیز درج نموده است؛ مزیت این پایگاه داده استفاده آسان جهت انجام تستهای اولیه است و ضعف آن عدم بروزرسانی پس از سال 2014 است، در حالی که دیگر پایگاه دادههای موجود در جدول 2 بروزرسانی میشوند.
تأثیر الگوریتمهای فراابتکاری در همترازی شبکه: برای دو شبکه ورودی G1 و G2، مسئله یافتن همترازی بین دو شبکه متناظر با جستجو برای یک نگاشت بین گرههای G1 و گرههای G2 است که تابع هزینه داده شده (کیفیت همترازی) را ماکزیمم میسازد.
جدول 2- فهرست مجموعه دادههای استاندارد
لینک دسترسی |
دامنه |
قابلیت |
نام مجموعه داده |
کلیه موجودات |
توصیف کاملی از پیچیدگیهای مولکولی، تعاملها و مسیرهای سلولی |
پایگاه داده شبکه تعامل مولکولی زیستی (BIND) |
|
مخمر |
فهرست تعاملهای آزمایشگاهی |
پایگاه داده تعامل پروتئینها (DIP) |
|
کلیه موجودات |
ذخیره، نمایش، و تحلیل تعاملهای پروتئین |
چارچوب InAct |
|
کلیه موجودات |
تعاملهای پروتئین-پروتئین و ژنتیکی همه اندامهای اصلی |
پایگاه داده BioGRID |
|
انسان، موش، مگس میوه، مخمر |
ذخیره و بازیابی اطلاعات تجربی |
پایگاه داده تعامل مولکولی (MINT) |
|
مخمر |
تعاملهای پروتئین-پروتئین برای مخمر |
مجموعه داده MPact |
|
انسان، موش، مگس میوه، کرم، مخمر |
مجموعهای از شبکههای PPI یوکاریوتها و مقادیر BLAST |
پایگاه داده Isobase |
|
http://www.wwpdb.org/ |
انسان |
بانک پروتئین |
مجموعه داده PDB |
برای تولید همترازی، همترازکنندهها از یک تابع هدف برای محاسبه امتیاز همترازی استفاده میکنند. در حالی که این تابع در همترازکنندهها متفاوت است اما میتوان آن را به شکل کلی زیر نوشت (22):
(3)
بطوریکه امتیاز نگاشت یک گره از V1 به یک گره در V2 است، و امتیاز نگاشت یک یال از E1 به یک یال از E2 است.
در مسئله همترازی اندازه فضای جستجو بزرگ است، زیرا همه نگاشتهای بین گرههای شبکههای مورد مقایسه را در برمیگیرد. عدم سازگاری محاسباتی مسئله که ناشی از «اِن پی-کامل» بودن مسئله زیرگرافهای ایزومورف است، باعث میشود برای حل آن نیاز به توسعه روشهای فراابتکاری (نظریههای تقریبی) داشته باشیم.
بین همترازی موضعی و سراسری ارتباط واضحی وجود دارد. برای مثال، هدف هر دو یافتن شباهتهای توپولوژی و عملکردی بین شبکههای مورد مقایسه است تا دانش زیستی گونههای مورد مطالعه را به گونههایی که کمتر مطالعه شدهاند تعمیم دهند (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 از پنج گونه
نام گونه |
نام مجموعه داده |
تعداد گرهها |
تعداد یالها |
انسان |
Hsapi(HS) |
9633 |
34327 |
موش |
Mmusc(MM) |
290 |
242 |
کرم |
Celeg(CE) |
2805 |
4495 |
مگس میوه |
Dmela(DM) |
7518 |
25635 |
مخمر |
Scere(SC) |
5499 |
31261 |
دلیل انتخاب این پنج گونه، کاربرد بسیار زیاد آنها در اثبات کارایی الگوریتمهای همترازی شبکه است. شکلهای 4 تا 6 متناظراً معیارهای ارزیابی EC، FC و S3 الگوریتمهای مختلف را بر روی این پنج گونه نشان میدهند.
در شکل 4 مشاهده میشود که تقریبا در تمام الگوریتمها میزان درستی تشخیص یال یا صحت یال (EC) با بزرگ شدن شبکهها و افزایش پیچیدگی آنها کاهش مییابد.
شکل 4- مقایسه معیار EC الگوریتمهای همترازی
بدیهی است تشخیص صحیح یال در گراف همترازی بمنزله تشخیص همترازی درست بین دو پروتئین یا گره متناظر در گراف است؛ لذا هر چقدر مقدار EC بیشتر باشد الگوریتم بهتر عمل کرده است.
بنابر شکل 4، الگوریتم GHOST که از استراتژی انتخاب و توسعه بهره میبرد دارای ثبات رفتاری بهتری نسبت به سایر الگوریتمها است. الگوریتم NETAL که از روش مکاشفهای استفاده میکند در رتبه دوم قرار دارد؛ و پس از آن میتوان به الگوریتمهای PSONA و SANA که جزء روشهای فراابتکاری هستند اشاره نمود.
همانطور که در شکل 5 مشاهده میشود میزان تشخیص صحیح پروتئینهایی با عملکرد مشابه یعنی معیار FC یا شباهت عملکردی الگوریتمهای مختلف با یکدیگر متفاوت است. در این میان، الگوریتمهای MeAlign، PSONA و SANA از بهترین قدرت تشخیص شباهت عملکردی بهره میبرند که همگی جزء روشهای فراابتکاری هستند.
شکل 5- مقایسه معیار FC الگوریتمهای همترازی
شکل 6 معیار S3 الگوریتمهای همترازی را مقایسه میکند. همانگونه که ملاحظه میشود در میان الگوریتمهای مختلف، روش SANA از بیشترین پایداری و ثبات مقدار بهره میبرد. پس از آن میتوان به الگوریتم NETAL اشاره کرد که در برخی جفت گونهها مانند MM-CE و MM-DM بسیار خوب عمل کرده است. لازم به ذکر است که هر دو الگوریتم SANA و NETAL از روش فراابتکاری و مکاشفهای استفاده میکنند.
همانطور که در شکلهای 4 تا 6 مشاهده میشود هر یک از الگوریتمها بر روی یک یا چند مجموعه داده بهتر عمل میکنند. الگوریتمهای فراابتکاری از جمله روشهای همترازی هستند که در اغلب موارد هر سه معیار EC، FC و S3 را ماکزیمم نمودند و این نشان از کارایی روشهای فراابتکاری است.
شکل 6- مقایسه معیار S3 الگوریتمهای همترازی
بحث
همانطور که ذکر شد یکی از چالشها در تحقیقات زیستی، بکارگیری دادههای زیستی در حجم بالاست که نیازمند استفاده از روشهای محاسباتی و الگوریتمهای هوشمند است (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- مقایسه مرتبه اجرای الگوریتمهای همترازی
نام الگوریتم |
مرتبه اجرایی |
PSONA |
O(NMV log(|V |)) |
DynaMAGNA++ |
O(N(p|V| + p|E| log(|E|) + plog(p))) |
MAGNA++ |
O(|E1| + |E2|) |
MAGNA |
O(N(M|E|+log(|E|)+ M|V|) + Mlog(M)) |
HubAlign |
O(|V|2log|V|) |
MI-GRAAL |
O(|V|2log|V|) |
NETAL |
O(|V|2log2|V|) |
IsoRank |
O(|V|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) بهره ببرد؛ میتواند جزء کارهای آتی محققین قرار گیرد.
نتیجهگیری
بطور کلی نتایج آزمایشی و تحلیلهای نظری نشان میدهند که استفاده از الگوریتمهای فراابتکاری از جمله الگوریتمهای ژنتیک، میمتیک، بهینهسازی توده ذرات، تبرید شبیهسازی شده و کلونی مورچگان نقش مؤثری در بهینهسازی معیارهای ارزیابی همترازی شبکه، کاهش زمان اجرا و مصرف حافظه دارد. در این رابطه، ایجاد روشهایی برای یکپارچهسازی همترازی سراسری و محلی، و ایجاد معیارهای استاندارد برای مقایسه عملکرد و کیفیت همترازی روشهای یکپارچهسازی، همچنان از زمینههای تحقیقاتی باز و فعالی در حوزه همترازی شبکه به حساب میآیند.
1- پورشیخ ع، اصغری م، عبدالمالکی پ. (1394). پیشگویی عملکرد اتّصال پروتئینها به ریبونوکلئیک اسید بر اساس خواص فیزیکوشیمیایی آنها به کمک روش لوژستیک رگرسیون، مجله پژوهشهای سلولی و مولکولی 28(1)، 45-53.
2- رضواننژاد ا، لطفی ص، بوستان آ. (1398). مدلسازی پروتئین استرس گرمایی 70 (HSP70) زنبور عسل به روش همولوژی مدلینگ و شبیهسازی ملکولی و اتصال آن به HSP40. مجله پژوهشهای سلولی و مولکولی 32(4)، 482-491.
3- مشیری م، قادریزفرهای م، قانع گلمحمدی ف. (1394). مقایسه الگوریتمهای برپایه یادگیری ماشین بر دقت تخمین دادههای گمشده حاصل از آزمایشهای ریزآرایه. مجله پژوهشهای سلولی و مولکولی 28(4)، 612-622.