دانلود مقاله واحدهای اصلی شبکههای پیچیده : مروری بر الگوریتمهای جستجوی موتیف در شبکه

بخشی از مقاله

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

کلمات کلیدی: جستجوی موتیف، شبکههای پیچیده، فراوانی، زیرگراف
1. مقدمه
در سالهای اخیر مطالعات بسیاری بر روی شبکههای پیچیده همچون شبکههای اجتماعی، شبکههای کامپیوتری و الکترونیکی و بخصوص شبکههای بیولوژیکی شامل شبکه متابولیک، شبکه تنظیم ژنی و شبکه برهم کنش پروتئین پروتئین3، به منظور درک بهتر عملکردهای زیستی صورت گرفته است. شبکهها این امکان را فراهم میآورند که با وجود پیچیدگی روابط موجود در سیستم های زیستی، بتوان سیستم های با ماهیت های کاملا متفاوت را در قالب یک چهارچوب مورد بررسی و تحلیل قرار داد، که به درک بهتر ساختار و عملکرد سیستم کمک میکنند. خصوصیات شبکه ها غالبا بر اساس دو معیار عمومی و محلی مورد بررسی قرار میگیرند. ویژگیهای عمومی شبکه به کسب یک نگرش کلی در مورد شبکه کمک میکند و وابسته به ساختار شبکه میباشد که از مهمترین معیارهای عمومی شبکهها میتوان تابع توزیع درجات، کوتاهترین مسیر و ضریب خوشه بندی4 را نام برد. [1] در حالیکه ویژگیهای محلی به بررسی شبکه در سطح جزیی تری میپردازد و عموما زیرساختارهای کوچک و محلی را می سنجند که به آن موتیف گفته میشود. در سال 2002 میلو5 موتیف را به عنوان زیرساختارهای خاصی که احتمال تکرار در شبکه و یا حتی میان شبکههای مختلف را دارد معرفی نمود[2]، که نشان دهنده یک الگوی مشخصی از تعاملات میان راسهای شبکه هستند و دارای عملکرد ویژهای در شبکه میباشند.

به عنوان مثال، شکل 1 موتیف مثلثی به نام حلقه پیش رو6 را نشان میدهد. این موتیف از معمولی ترین موتیفها است که در بسیاری از شبکههای الکترونیکی و شبکههای زیستی از جمله شبکههای تنظیم ژن و شبکه های عصبی که عملیات مربوط به کنترل و انتقال اطلاعات را انجام میدهند یافت میشود 3]،.[2

Motif Computational Protein-Protein interaction Clustering coefficient Milo Feedforward Loop

1

2

3

4

5

6

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

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 حلقه پیش رو به عنوان موتیف جهت داری که دینامیک آن از نظر تئوری و تجربی بررسی شده است.

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

در ادامه اهدافی که در این مقاله دنبال می کنیم شامل: بررسی الگوریتم های مختلف و جنبه های اصلی کشف موتیف که در ابزارهای جستجوی موتیف مورد استفاده قرار می گیرد و همچنین بیان رویکرد های جدیدی که در مقالات مروری گذشته به آنها پرداخته نشده است. ارائه یک چهارچوبی جهت طبقه بندی الگوریتم های کشف موتیف مبنی بر روش های مورد استفاده در آنها. همچنین بررسی عملکرد ها و مقایسه انها با یکدیگر با توجه به نتایجی که در مطالعات مختلف منتشر شده است.
2. ابعاد اصلی کشف موتیف
هر الگوریتم جستجوی موتیف در شبکه نیازمند استفاده از ابزارها و روش هایی است که حل این مسئله را تسهیل نماید، بطور معمول شامل، روش های تعیین فراوانی موتیفها، تصمیم برای همریختی زیرگرافها، راهی برای تولید شبکه های تصادفی و تعیین اهمیت آماری زیرگراف مورد نظر میباشد. تمامی این فاکتورها در زمان طراحی و پیاده سازی یک ابزار کشف موتیف باید مورد توجه قرار بگیرد و هر ابزار از تنوع و ترکیب مختلفی از این فاکتورها بوجود میآید. در ادامه به بررسی هریک از مهمترین آنها خواهیم پرداخت.
2,1 محاسبه فراوانی8 زیرگراف
یکی از جنبه های مهم هر ابزار و الگوریتمی روش تعیین فراوانی موتیف میباشد. فراوانی یک زیرگراف در شبکه، بیشترین تعداد تطابق های مختلف از آن زیرگراف است[4] همچنین فراوانی موتیف ها در شبکه، بر اساس نحوه ی همپوشانی و اشتراک گره و یال و آنکه چه عناصری از گراف در دو تطابق مشترک باشند کاملا تغییر می کند 5]،. [6 سه تعریف مختلف برای مفهوم فراوانی موتیف را شرایبر9 و همکارانش در مقالاتشان 6]،[5 مورد بررسی قرار داده اند که تاثیر قابل توجهی در نتایج نهایی و پیچیدگی شمارش خواهد گذاشت. از این رو در فراوانی نوع اول F1، زیرگراف ها اجازه همپوشانی در یال و گره بطور دلخواه را دارند. در فراوانی نوع دوم F2 ، فقط نودها اجازه همپوشانی دارند و یالها باید کاملا مجزا باشند و در فراوانی نوع سوم F3 ، هیچ نود و یالی اجازه همپوشانی را نخواهد داشت. مفهوم فراوانی F2 و F3، استفاده مجدد از عناصر گراف را در تطابق های مختلف محدود میکند و تمامی تطابق ها در فراوانی شمرده نخواهند شد. هر نوع فراوانی محدودیت های متفاوتی دارد به همین خاطر فراوانی های مختلف محاسبه شده توسط مفاهیم متفاوت از اهمیت گوناگونی برخوردار می باشد.[8] بسیار مهم است که توجه داشته باشیم کدام مفهوم فراوانی توسط کدام ابزار مورد استفاده قرار میگیرد (شکل .(2

7 isomorphism 8 frequency 9 Schreiber

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

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

(الف) (ب)

شکل.2 (الف) نمونهای از گراف جهتدار و موتیف کاندید (ب) نمونههای موتیف کاندید در شبکه داده شده در قسمت الف با استفاده از مفهوم فراوانی نوع .F1 [27]

2,2 همریختی گرافها
از ابزارهای مهمی که در هر روش جستجوی موتیف به کار گرفته میشود، تشخیص همریختی گرافها است. بنابراین استفاده از روشی مناسب برای حل این مسئله در بهبود حل مسئلهی اصلی کمک بسزایی خواهد کرد . برای بررسی همریختی دو گراف G و G’ ، باید هر جایگشتی از رئوس گراف G با تمام جایگشتهای رئوس گراف G’ مقایسه شود که یکسان هستند یا نه که این امری بسیار زمان بر و پیچیده میباشد. در واقع مسئله همریختی دو گراف یک مسئله NP می باشد و هیچ الگوریتمی که قابل اجرا در زمان چند جملهای باشد برای آن ارائه نشده است. برای اثبات اینکه دو گراف غیر همریخت هستند گاهی تنها کافی است یک سری آزمون ساده مانند بررسی اندازهی گراف ها، تعداد یال ها، دنباله درجه رئوس و یا طول کوتاهترین مسیر در گراف انجام شود. هرچه دو گراف به هم شبیهتر باشند این آزمون ها ناکارآمدتر میشوند و محاسبات نسبت به اندازه گراف ها بطور نمایی پیچیده تر میشود. سریعترین روشی که امروزه برای تشخیص همریختی گراف ها وجوددارد، الگوریتم ناتی است که توسط مَک کِی10 ارایه شده است.[9] دراین الگوریتم ابتدا تعدادی آزمون از پیش تعریف شده برای رد کردن همریختی دو گراف امتحان میشود. اگر تمام این آزمون ها رد شوند، آنگاه جایگشتهای ممکن تمام رئوس بررسی می-شوند. به این ترتیب متوسط زمان اجرا به میزان قابل قبولی کاسته میشود.