صفحه نخست --> تحلیل شبکه های اجتماعی --> تشخیص موتیف در گراف با برنامه Cytoscape

تشخیص موتیف در گراف با برنامه Cytoscape

معرفی موتیف

امروزه کشف و تشخیص موتیف در گراف ها بسیار دارای اهمیت هستند. گراف ­ها ساختمان داده­ های جهانی هستند. یک گراف می­تواند یک شبکه از ارتباطات بین اشیاء را در حالت کلی مدل کند. می­توان گفت که تمام اشیایی که در جهان حقیقی وجود دارند یا یک شبکه از ارتباطات میان اجزایشان هستند و یا خود اجزای یک شبکه بزرگتر می­ باشند. هر یک از این دو حالت را می­توان بوسیله گراف تشریح کرد. “موتیفِ شبکه” یک الگوی زیرگرافِ تکرار شونده یکتا می باشد. یگانگیِ موتیف را به صورتی مرسوم با p-value و z-score تعیین می­کنند. از موتیف­های شبکه برای تشخیص خصوصیات شبکه­ها مانند اندازه فراوانی گراف یا به عنوان معیاری برای طبقه­بندی، اندازه گیری و تشخیص نوع شبکه­ها استفاده می­شود. همچنین موتیف­ های شبکه در کاربردهای بیولوژیکی مختلف استفاده می­شوند. کاربردهای بیولوژیکی موتیف شبکه شامل پیش­بینی ژن ایجاد کننده سرطان و … هستند.

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

نمونه ای از موتیف های سه تایی
نمونه ای از موتیف های سه تایی

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

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

برخی از افزونه ­های این برنامه، تنها به اجرای الگوریتم­های تشخیص موتیف اختصاص دارند. ازجمله
افزونه ­های معروف اجرای الگوریتم­های تشخیص موتیف برای این نرم­افزار 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 روی ویندوز نصب باشد. (توجه: این برنامه تنها بر روی ویندوز ۶۴ بیت قابل اجراست).
  • Motif-Discovery: افزونه مورد نظر در این پژوهش که از مسیر زیر قابل دانلود است:

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

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

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

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

شکل­های زیر نمونه ­هایی از اجرای برنامه Cytoscape را نشان می­دهند. برای مثال، در تصویر شکل ۳، افزونه Motif-Discovery برای جستجوی موتیف ­های جهت ­دار با ۴ رأس و بدون شبکه تصادفی بر روی یک شبکه اجرا شده است که در نتیجه آن، ۱۳نوع گراف جهت­دار بدست آمده­اند و زمان اجرای آن ۲۳۶ میلی ثانیه بوده است. در ادامه، در جدول نتایج، رشته ماتریس مجاورت، فراوانی هر موتیف نشان داده می­شوند.

برنامه Cytoscape
برنامه Cytoscape

 

برنامه Cytoscape
برنامه Cytoscape

برنامه Cytoscape
برنامه Cytoscape

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

داده کاوی برای تشخیص فعالیت باکتری­ها با استفاده از داده­ های ثبت شده در پایگاه داده E. Coli، به فراهم کردن اطلاعات ضروری و دانش مورد نیاز پزشکان در تصمیم­ گیری بهتر کمک می­کند. این­جا، جستجو بر این پایگاه داده را با تعداد رأس­ های ۳-۴-۵-۶-۷ (به دو صورت جهت­دار تا ۶ راس و بدون جهت تا ۷ راس) با افزونهMotif-Discovery  در برنامه Cytoscape اجرا و نتایج را در جدول زیر ارائه می­کنیم.

نحوه اجرا

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

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

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

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

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

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

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

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

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

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

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

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

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

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

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *