دانلود مقاله روشی کارامد جهت بهبود عملکرد کشف موتیف شبکه با استفاده از الگوریتم تکاملی

بخشی از مقاله

چکیده

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

کلمات کلیدی: شبکههای پیچیده، موتیفهای شبکه، فراوانی زیرشبکه، الگوریتم تکاملی
1. مقدمه

شبکههای زیست شناسی عموما شبکههایی پیچیده و وسیع هستند که مطالعه تجربی ارتباطات درون سلولی و بین سلولی، تکنولوژیهای پیچیدهای را برای به دستآوردن داده های لازم نیاز دارد. به دلیل وجود چنین پیچیدگیای، استفاده از روشهای بیوانفورماتیک به عنوان یک ابزار قوی به منظور استخراج اطلاعات فراتر از مشخصه های کلی در شبکهها، ملزم به دست آوردن شناختی از اجزای ساختاری اصلی مربوط به کلاسهای مختلف شبکهها میباشد. خصوصیات یک شبکه عموما براساس دو نوع معیار عمومی و محلی مورد بررسی قرار میگیرند. خصوصیات عمومی شبکه به کسب یک نگرشِ کلی در مورد شبکه کمک میکنند و وابسته به ساختار شبکه میباشند. از مهمترین معیارهای عمومی شبکهها میتوان تابع توزیعِ درجات، کوتاهترین مسیر و ضریب دسته-بندی را نامبرد[1]، خصوصیات محلی، به بررسی خصوصیات شبکه در سطح جزییتری میپردازد. معیارهای محلی عموما زیرساختارهای کوچک و محلی را میسنجد که به آنها موتیف1 گفته میشود.

بر اساس این نظریه که "تکامل، مدلهایی را حفظ میکند که نمایان گر عملکردهای خاصی هستند" [10]، در سال 2002 میلو ادعا کرد که احتمال تکرار زیرساختارهای خاصی در یک شبکه و یا حتی در میان شبکههای مختلف وجود دارد.[3] این زیرساختارها که نشاندهنده یک الگوی مشخص از تعاملات میان راس های شبکه هستند، دارای عملکرد ویژه ای درشبکه میباشند. این زیرساختارهای تکرار شونده و معنیدار موتیف نامیده میشوند. این طور به نظر میرسد که چنین الگوهای تکرارشوندهای حاوی اطلاعات بوده و احتمالا دارای عملکردهای وایژه باشند. همچنین شایان ذکر است که ساختارِ توپولوژیکیِ شبکه در تعریف موتیف حایز اهمیت است و نه نوع پروئینِت هر گره. برای مثال در شکل1، سه نمونه از الگوهای برهمکنش که از نظر زیستی معنادار هستند، نمایش داده شده است. ممکن است الگوهای معنادار زیستی دیگری نیز موجود باشند که تعریف فعلی موتیف شبکه آن ها را در برنمیگیرد. در مقابل،ممکن است الگوهایی که با تعریف فعلی موتیف شبکه مهم فرض شدند، از نظر زیستی معنادار و مهم نباشند. 11]،.[2

1 Motif

×اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر

First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering×
. . . W W W . T D E C O N F . I R . . .

(الف) (ب) (ج) شکل .1 سه موتیف جهتداری که دینامیک آنها از نظر تئوری و همچنین از نظر تجربی بررسی شده است: (الف) حلقهپیشرو (ب) واحد تکورودی (ج)

بوتی در سالهای اخیر، به منظور درک اصول کلی طراحی ساختار شبکههای پیچیده، موتیفها توجه زیادی را به خود جلب کردهاند. مطالعه بر روی موتیفها،

همچنین برای درک بهتر عملکرد شبکهها مفید میباشد. تحقیقات نشان داده است در شبکههایی که فرآیندهای مشابهی انجام میدهند، موتیفهای مشابهی مشاهده شده است، هرچند این شبکهها مربوط به سیستمهای مختلف زیست شناسی باشند .[10] به همین دلیل میتوان از موتیفها به عنوان یک مولفهی اصلی برای کلاسبندی شبکه استفاده نمود. عمل تشخیص موتیفهای شبکه، در حقیقت مسئله پیدا کردن زیر ساختارهایی از شبکه است که دارای اهمیت آماری هستند. از اینرو، پیدا کردن پاسخ بهینه برای این مسئله در زمان چندجملهای امکانپذیر نبوده و روشهای ارائه شده برای حل مسئله بصورت ابتکاری و یا تقریبی هستند در واقع هدف این روشها، یافتن جوابی نزدیک به جواب بهینه است. الگوریتمهای جستجوی موتیفهای شبکه شامل دو مرحلهی اصلی هستند: اول، محاسبهی تعداد رخداد یک زیرگراف در شبکه اصلی یعنی تعیین این که از یک اندازه مشخص، چه تعداد زیرگرافهایی در شبکه موجود است و دوم، ارزیابی اهمیت آن زیرگراف است. عمده روشهای پیشنهاد شده در این زمینه در گامِ شمارش زیرگرافهای شبکه اختلاف دارند، که میتوان آنها را به دو دسته کلی تقسیم نمود:(1 روشهایی که تعداد رخداد زیرگرافها را دقیقا شمارش2 میکنند.(2 روشهایی که با استفاده از نمونه برداری3 و تقریب آماری عمل شمارش را انجام میدهند.

در هردو دسته الگوریتمهای ارئه شده نیاز به کلاسبندی زیرگرافهای شناسایی شده در شبکه اصلی را دارند به عبارت دیگر کلاسهای همریختی زیرگراف-های شناسایی شده باید مشخص گردد که این کار به دو طریق صورت میگیرد: اول اینکه، ابتدا تمام کلاسهای مختلف غیرهمریخت4 ممکن با اندازه داده شده را تولید سپس فراوانی هرکدام را در شبکه اصلی محاسبه کنیم (به عنوان مثال، شمارش تعداد نگاشتهای هر کلاس در شبکه اصلی) ، مشکل این روش رشد نمایی تعداد کلاسهای غیرهمریخت با اندازه زیرگراف داده شده است که تولید همه آنها زمانبر بوده. الگوریتمهای [6] GK و [14] MODA در این دسته قرار دارند که به آن روش موتیف محور نیز میگویند. همچنین الگوریتم ارائه شده در این مقاله را می توان در این دسته گنجاند البته قابل توجه است که مشکل فعلی این الگوریتم ها را نداشته که در ادامه به تفصیل شرح داده خواهد شد. روش دوم، از ابتدا به جستجوی در شبکه اصلی پرداخته و نیازی به تولید کلاسهای غیرهمریخت نیست، بعد از مشخص کردن زیرگرافهای شبکه اصلی آنها را بطور مستقیم و با استفاده از الگوریتم ناتی که سریعترین الگوریتم در این زمینه است کلاس بندی میکنیم که این مرحله نیز زمان زیادی را صرف میکند (به عنوان مثال، در هر بار شمارش زیرگرافها کلاس همریختی آن را بطور جداگانه مشخص کنیم). الگوریتم هایی چون [4] FANMOD، [5] Kavosh و [7] G-Tries در این طبقه بندی قرار میگیرند که به آن روش شبکه محور نیز میگویند. با توجه به این حقیقت که الگوریتم های موجود برای شناسایی موتیف های شبکه به اندازه کافی مقیاس پذیر نبوده، طراحی ابزاری کاراتر برای این منظور ارزشمند است.

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

2 Exact Counting 3 Sampling 4 Non-isomorphism

×اولین همایش ملی پیشرفت های تکنولوژی در مهندسی برق، الکترونیک و کامپیوتر

First National Conference of Technology Developments on Electronical, Electronics and Computer Engineering×
. . . W W W . T D E C O N F . I R . . .

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

.1,1 تعریف مسئله

در این مقاله، شبکهی تعاملات پروتئین-پروتئین یا هر شبکه اصلی دیگری با گراف بدون جهت G = (V, E) نشان داده میشود که مجموعه رئوس V = { 1, 2, … , }، مجموعهای متناهی از گرهها است و برابر با | ( )| = میباشد که اندازهی شبکه یا گراف را نشان میدهد. همچنین گراف بدون جهت ( , ) زیرگراف مورد بررسی در شبکه است که | ( )| = بیانگر اندازه زیرگراف مورد نظر است. در الگوریتم مورد بحث، هدف یافتن زیرگرافهای غیرهمریخت بهینه از میان تمام زیرگرافهای ممکن با اندازه مشخص میباشد. برای این منظور تمام نگاشتهای ممکن از زیرگراف مذکور در شبکه اصلی و مجموعه شبکههای تصادفی را بدست میآوریم و بنابه تابع برازندگی تعریف شده در الگوریتم زیرگرافهای مطلوب را به عنوان موتیف بر می-گردانیم.در ادامه، ساختمان دادههای مورد استفاده و عملگرهای ژنتیکی و تابع برازندگی مورد استفاده در الگوریتم ژنتیک ارائه شده در این مقاله، توضیح داده میشوند.