تشخیص موتیف یا زیر گراف های پرتکرار با برنامه Cytoscape

معرفی موتیف

در مطالب قبلی به آموزش Cytoscape پرداختیم در آموزش امروز به نحوه تشخیص موتیف ها در این ابزار می پردازیم. امروزه کشف و تشخیص موتیف در گراف ها بسیار دارای اهمیت هستند. گراف ­ها ساختمان داده­ هاي جهاني هستند. يك گراف مي­تواند يك شبكه از ارتباطات بين اشياء را در حالت كلي مدل كند. مي­توان گفت كه تمام اشيايي كه در جهان حقيقي وجود دارند يا يك شبكه از ارتباطات ميان اجزايشان هستند و يا خود اجزاي يك شبكه بزرگتر مي­ باشند. هر يك از اين دو حالت را مي­توان بوسيله گراف تشريح كرد. “موتیفِ شبکه” یک الگوی زیرگرافِ تکرار شونده یکتا می باشد. کاوش زیرگراف‌های پرتکرار (Frequent Subgraph Mining) یکی از مسائل مهم در حوزه گراف‌کاوی است. هدف از انجام این کار استخراج زیرگراف‌هایی با فراوانی بالا در یک مجموعه داده است به طوری که تعداد آن‌ها از آستانه مشخصی بیشتر باشد. یگانگیِ موتیف را به صورتی مرسوم با p-value و z-score تعیین می­کنند.

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

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

الگوریتم های تشخیص موتیف از جمله mFinder، Fanmod ، Kavosh، Mavisto ، LaMoFinder  and  NeMoFinder، Grochow and Kellis ،  MODA  و …. هستند. همه الگوريتم‌ها از نظر محاسباتي پيچيده‌اند و ممکن است با افزايش اندازه‌ي شبكه‌ي مورد ارزيابي، دچار مشكل ‌شوند. هم‌چنين، اين الگوريتم‌ها از نظر اندازه‌ي موتيف بسيار محدود هستند و در عمل قادر به پيدا كردن موتيف‌هاي با تعداد رأس­ های زیاد نيستند. از این رو، پژوهش­گران برای تشخیص موتیف، به محاسبات موازی و ابری روی آوردند. تعداد کاندیدا‌ها برای زیرگراف پرتکرار با بزرگ شدن اندازه زیرگراف به سرعت نمایی افزایش می‌یابد.  برای نمونه زیرگراف جهت‌دار با سه راس ۱۳ حالت ممکن خواهد داشت.

 الگوریتم ها و ابزارهای کشف موتیف

امروزه دیدگاه شبکه­ای امکان دستیابی به محتوای معنی­دار برای داده­های حاصل از فناوری­های جدید با توان بالا را به منظور تحلیل، تفسیر و تولید فرضیات مختلف فراهم ساخته است. تعداد و اندازه پایگاه داده­ها به سرعت در حال افزایش هستند و مدل­های توسعه یافته داده­کاوی می­توانند برای پژوهش­گران و دانشمندان برای کمک در تصمیم­ گیری موثر و کاربردی باشند. برای مثال، نرم­افزار Cytoscape یک ابزار رایگان متن باز، به یکی از محبوب­ترین ابزار ترسیم و تحلیل شبکه تبدیل شده است. به این برنامه سالانه در بیش از 500 مقاله استناد می­شود و ماهیانه بیش از 800 بار دانلود می­شود. در این بسته نرم­افزاری ترسیم و تحلیل شبکه­های مختلف مخصوصا شبکه­های برهم­کنش مولکولی و مسیرهای زیستی و هم­چنین ادغام چنین شبکه­ هایی با حاشیه­ نویسی­ها و پروفایل­ه ای بیانی امکان­پذیر است. ویژگی­های کاربردی دیگری نیز از طریق 200 افزونه به این بستر نرم­افزاری اضافه شده­اند.

برخی از افزونه ­های این برنامه، تنها به اجرای الگوریتم­های تشخیص موتیف اختصاص دارند. ازجمله
افزونه ­های معروف اجرای الگوریتم­های تشخیص موتیف برای این نرم­افزار iRegulon، SLiMScape، cytoHubba، NetMatchStar، Rene، ISMAGS، Motif-Discovery، PTMOracle، NetMatch، GraphletCounter، APID2NET و CytoKavosh هستند.

در ادامه، به ارائه گزارش یک پروژه با اجرای یکی از الگوریتم تشخیص موتیف بر روی یکی از پایگاه داده­ های مهم شبکه­ های زیستی (E. Coli)، با استفاده از افزونه Motif-Discovery در برنامه Cytoscape می­پردازیم. در این پژوهش از نرم ­افزار Cytoscpae استفاده شده است که فایل­ های نوشته شده با فرمتهای زیر را می­خواند:

• Simple interaction file (SIF or .sif format)
• Nested network format (NNF or .nnf format)
• Graph Markup Language (GML or .gml format)
• XGMML (extensible graph markup and modelling language)
• SBML
• BioPAX
• PSI-MI Level 1 and 2.5
• Delimited text
• Excel Workbook (.xls)

به عنوان مثال برای رسم گرافِ شکل زیر با وزنِ راس­ها و یال­های نوشته شده در آن، کد زیر را وارد می­کنیم.

// Create Sally

CREATE (sally:Person { name: ‘Sally’, age: 32 })

// Create John

CREATE (john:Person { name: ‘John’, age: 27 })

// Create Graph Databases book

CREATE (gdb:Book { title: ‘Graph Databases’,

    authors: [‘Ian Robinson’, ‘Jim Webber’] })

// Connect Sally and John as friends

CREATE (sally)-[:FRIEND_OF { since: 1357718400 }]->(john)

// Connect Sally to Graph Databases book

CREATE (sally)-[:HAS_READ { rating: 4, on: 1360396800 }]->(gdb)

// Connect John to Graph Databases book

CREATE (john)-[:HAS_READ { rating: 5, on: 1359878400 }]->(gdb)

معرفی افزونهMotif-Discovery  

افزونهMotif-Discovery  افزونه­ای آسان و سریع برای پاسخ­گویی به نیازهای کاربران در تشخیص موتیف شبکه (جستجوی زیرگراف) و استفاده از نرم­افزار Cytoscape است. این افزونه از سریع­ترین الگوریتم تشخیص موتیف، که G-Tries است، استفاده می­کند. الگوریتم G-Tries با استفاده از الگوریتم­های موازی به کشف موتیف در شبکه می­پردازد.

در این نسخه از افزونه Motif-Discovery کاربر می­تواند تنظیمات زیر را برای تشخیص موتیف انجام دهد:

• اندازه موتیف را مشخص کند.
• نوع موتیف را مشخص کند.
• برای اندازه­گیری مقدار آماری شبکه (z-score)، تعداد شبکه­های تصادفی را تعیین کند.
• پیشرفت کار را مشاهده کند.
• نتایج را به صورت جدول با جزییات مشاهده کند.
• هر یک از نتایج زیرگراف­ها را انتخاب (ردیف جدول) و افزونه زیرگراف بدست آمده را رسم و شبکه را با توجه به وقایع این زیرگراف رنگ ­کند.

 برنامه های لازم برای اجرای افزونه Motif-Discovery در نرم­افزار Cytoscpape

• Java: برای اجرای این برنامه باید Java8 روی ویندوز نصب باشد. (توجه: این برنامه تنها بر روی ویندوز 64 بیت قابل اجراست).
• Motif-Discovery: افزونه مورد نظر در این پژوهش که از مسیر زیر قابل دانلود است:

http://apps.cytoscape.org/apps/motifdiscovery

این­جا نمونه مورد نیاز Cytoscpape برای اجرای این افزونه نوشته شده است.

• Cytoscpape: برای اجرای افزونه Motif-Discovery نیاز به نمونه 3.2 از برنامه Cytoscape است که این برنامه را می­توان از مسیر زیر دانلود کرد:

http://www.cytoscape.org/download_old_versions.html

شکل­های زیر نمونه ­هایی از اجرای برنامه Cytoscape را نشان می­دهند. برای مثال، در تصویر شکل 3، افزونه Motif-Discovery برای جستجوی موتیف ­های جهت ­دار با 4 رأس و بدون شبکه تصادفی بر روی یک شبکه اجرا شده است که در نتیجه آن، 13نوع گراف جهت­دار بدست آمده­اند و زمان اجرای آن 236 میلی ثانیه بوده است. در ادامه، در جدول نتایج، رشته ماتریس مجاورت، فراوانی هر موتیف نشان داده می­شوند.

 

نتیجه اجرای افزونه Motif-Discovery  بر پایگاه داده E. Coli  در برنامه Cytoscpape

داده کاوی برای تشخیص فعالیت باکتری­ها با استفاده از داده­ های ثبت شده در پایگاه داده E. Coli، به فراهم کردن اطلاعات ضروری و دانش مورد نیاز پزشکان در تصمیم­ گیری بهتر کمک می­کند. این­جا، جستجو بر این پایگاه داده را با تعداد رأس­ های 3-4-5-6-7 (به دو صورت جهت­دار تا 6 راس و بدون جهت تا 7 راس) با افزونهMotif-Discovery  در برنامه Cytoscape اجرا و نتایج را در جدول زیر ارائه می­کنیم.

نحوه اجرا

ابتدا برنامه­های java8 و Cytoscape و افزونه Motif-Discovery را در ویندوز نصب، و سپس برنامه Cytoscape را اجرا می­کنیم. از تبِ Apps، App Manager را انتخاب و افزونه Motif-Discovery را از مسیر نصب شده انتخاب و به افزونه­ های موجود در برنامه اضافه می­کنیم. خواهیم دید که تبِ افزونه­ ی نصب شده، به قسمت Control Panel در برنامه اضافه می­شود.

در منوی بالای برنامه چند دکمه وجود دارند، که 4 دکمه از آن­ها برای وارد کردنِ داده در برنامه هستند. در ادامه، به توضیح آن­ها می­پردازیم.

• Import Network From File: اگر فایلِ شبکه مورد نظر در حافظه موجود باشد، آن­گاه می­توان از این قسمت، فایل را بارگذاری و تشخیص موتیف را روی آن اجرا کرد.
• Import Network From URL: در این قسمت دو انتخاب وجود دارند. هم می­توان از پایگاه داده­هایی که در برنامه هستند استفاده کرد، و هم می­توان آدرس لینک شبکه مورد نظر را از مرورگر کشید یا کپی کرد.
• Import Table From File: در این قسمت، می­توان فایل با فرمت جدول را از حافظه بارگذاری و تشخیص موتیف را روی آن اجرا کرد.
• Import Table From URL: اگر فایل با فرمت جدول در وب باشد، آن­گاه می­توان آدرس لینک­ جدول مورد نظر را از مرورگر کشید یا کپی کرد.

ما در این بحث، از گزینه دوم استفاده و پایگاه داده E. Coli را از منو انتخاب کردیم. پس از بارگذاری پایگاه داده بر روی برنامه، نام فایلِ شبکه در پنجره Control Panle، در تبِ Netwoks ظاهر می­شود که تعداد یال­ها و گره­های شبکه را نشان می­دهد. نکته قابل توجه این­ است که با این برنامه می­توان به طور هم­زمان چندین شبکه را بارگذاری کرد و بر روی آنها عملیات تشخیص موتیف را انجام داد.

تنظیمات اصلیِ عملیات تشخیص موتیف در تبِMotif-Discovery ، انجام می­شوند. در این تب، اندازه موتیف (3 تا 7 رأس)، نوع موتیف (جهت­دار و بدون جهت)، و تعداد شبکه تصادفی را انتخاب می­کنیم و دکمه Run را کلیک می­کنیم و محاسبه شروع می­شود. باید توجه داشت که فرایند محاسبه می­تواند در یک چشم به­هم زدن اتفاق بیفتد یا مدتی طول بکشد. این مدت زمان به تعداد رأس­های موتیف، نوع موتیف و تعداد شبکه تصادفی بستگی دارد.

برنامه پس از محاسبه، نتایج را در پنجره Control Panle نشان می­دهد. این خروجی حاوی اطلاعات زیر است:

• تعداد انواع موتیف کشف شده،
• تعداد کل موتیف­ها،
• مدت زمان محاسبه فرایند تشخیص موتیف،
• رشته­ی مربوط به هر موتیف،
• فراوانیِ هر موتیف،
• مقدار z-score.

اگر بر روی هر موتیف در جدول کلیک کنید، شکل موتیف مورد نظر نشان داده خواهد شد.

به همین ترتیب، از طریق افزونه Motif-Discovery می­توان محاسبات مورد نظر را بر روی پایگاه داده­های مختلف با الگوریتم­های مختلف انجام داد و نتایج را بررسی کرد.

برخی از منایع:

متن ارسالی توسط خانم فاطمی

• https://neo4j.com/
• http://cytoscape.org/

آدرس کانال تلگرام ما:

t.me/bigdata_channel
برای ورود به کانال بر روی اینجا کلیک کنید.

Visits: 2757