تحلیل گراف توانی

شبکه‌ها نقشی حیاتی در زیست‌شناسی محاسباتی ایفا می‌کنند؛ اما تحلیل و نمایش آن‌ها هنوز یک مسئلهٔ باز است. تحلیل گراف توانی یک تبدیل از شبکه‌های زیستی به نمایشی فشرده و با افزونگی کمتر است که از وفور خوشه‌ها و گراف‌های کامل دوبخشی به عنوان اجزای ابتدایی توپولوژیکی بهره می‌گیرد. در این تبدیل همهٔ اطلاعات شبکهٔ ابتدایی حفظ می‌شوند.

گراف توانی

نمایش گرافیکی

گراف‌ها با دایره‌ها یا نقطه‌هایی که نمایش‌دهندهٔ راس‌ها هستند و خط‌هایی که دو راس را به هم وصل می‌کنند و نمایش‌دهندهٔ یال‌ها هستند رسم می‌شوند. گراف‌های توانی این شیوهٔ نمایش را گسترش داده و از راس توانی و یال توانی استفاده می‌کنند. راس‌های توانی با دایره‌هایی نشان داده می‌شوند که تعدادی راس یا راس توانی دیگر را در بر می‌گیرد. یال‌های توانی با خط‌هایی بین راس‌های توانی نشان داده می‌شوند.

گراف کامل دوبخشی دو مجموعه از رئوس است که بین هر راس از مجموعهٔ اول و هر راس از مجموعهٔ دوم یال وجود دارد. در یک گراف توانی، یک گراف کامل دوبخشی به صورت یک یال بین دو راس توانی نشان داده می‌شود.

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

ستاره مجموعه‌ای از رئوس است که بین یک راس از آن و بقیهٔ رئوس یال وجود دارد. در واقع ستاره حالت خاصی از گراف کامل دوبخشی است که در آن اندازهٔ یکی از بخش‌ها برابر ۱ است. در یک گراف توانی، ستاره به صورت یک یال توانی بین یک راس معمولی و یک راس توانی نشان داده می‌شود.

اجزای اولیهٔ مورد استفاده در گراف توانی و نمایش نموداری متناظر با آن‌ها: گراف دوبخشی کامل، خوشه و ستاره.

تعریف رسمی

با داشتن گراف $G={\bigl (}{V,E}{\bigr )}$

که در آن

V={\bigl \{}v_{1},\dots ,v_{n}{\bigr \}}

مجموعهٔ راس‌ها و

E\subseteq V\times V

مجموعهٔ یال‌هاست، گراف توانی

G'={\bigl (}{V',E'}{\bigr )}

گرافی است که توسط مجموعه رئوس توانی

V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}

که با یال‌های توانی

E'\subseteq V'\times V'

به هم متصل شده‌اند تعریف می‌شود؛ بنابراین گراف‌های توانی روی مجموعه توانی راس‌ها و مجموعه توانی یال‌ها تعریف می‌شوند.

معنی‌شناسی گراف توانی به این صورت است: اگر دو راس توانی با یک یال توانی به هم متصل اند، به این معنی است که همهٔ رئوس درون راس توانی اول به همهٔ رئوس درون راس توانی دوم متصل اند. به‌طور مشابه، اگر یک راس توانی با یک یال توانی به خودش متصل باشد، به این معنی است که رئوس درون این راس توانی دو به دو به هم متصل اند.

دو شرط زیر برای ساده‌سازی نمایش لازم اند:

شرط سلسله‌مراتب راس‌های توانی: هر دو راس توانی یا مجزا اند یا یکی زیرمجموعهٔ دیگری است.
شرط جدایی یال‌های توانی: هر یال در گراف اصلی با یک و فقط یک یال توانی نمایش داده می‌شود. به بیان دیگر یال‌های توانی یک افراز از یال‌های گراف اصلی هستند.

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

الگوریتم گراف توانی

این الگوریتم حریصانه برای ساختن گراف توانی از روی یک گراف به کار می‌رود و هدف این است که تا جای ممکن تعداد یال‌های گراف توانی کمینه باشد. این الگوریتم از دو فاز تشکیل شده‌است:

در فاز اول، هدف پیدا کردن راس‌های توانی بالقوه است. اگر مجموعه‌ای از رئوس دارای همسایه‌های مشابه باشند، این مجموعه یک کاندیدا برای یک راس توانی است. برای تشخیص این مجموعه‌ها از یک الگوریتم خوشه‌بندی سلسله‌مراتبی بر اساس شباهت همسایگی استفاده می‌شود. معیار شباهت در این الگوریتم، اندیس ژاکار است (البته می‌توان از معیارهای دیگری نیز برای شباهت همسایگی استفاده کرد). این اندیس همیشه مقداری بین ۰ و ۱ دارد: اگر مجموعه‌های $U$ و $V$ هیچ همسایهٔ مشترکی نداشته باشند برابر ۰ است و اگر همسایه‌هایشان دقیقاً یکسان باشند برابر ۱ است. شکل ۲ نشان می‌دهد چگونه خوشه‌بندی راس‌هایی که همسایگی یکسان یا مشابه دارند، مجموعه‌های کاندیدا برای خوشه‌ها و گراف‌های کامل دوبخشی را بدست می‌دهد.
در بین راس‌های توانی بالقوه که در فاز اول بدست آمدند، هر دوتایی که متناظر با یک یال توانی باشند، یک کاندیدا برای یال توانی اند. از بین این یال‌های توانی، آن که شامل بیشترین یال از گراف اصلی است را به گراف توانی اضافه می‌کنیم. این کار را به‌طور پی در پی ادامه می‌دهیم تا زمانی که همهٔ یال‌های گراف اصلی اضافه شوند. در نهایت آن راس‌های توانی کاندیدایی که انتهای هیچ‌یک از یال‌های توانی نیستند از گراف توانی حذف می‌شوند.

مراحل الگوریتم گراف توانی

کاربردها

شبکه‌های زیستی

نشان داده شده که تحلیل گراف توانی روشی مفید برای تحلیل انواع متنوعی از شبکه‌های زیستی از جمله شبکه‌های تعامل پروتئین-پروتئین، شبکه تنظیم‌کننده ژن و شبکه‌های همولوژی/پارالوژی است. همچنین به وسیلهٔ گراف توانی می‌توان یک نرخ فشرده‌سازی برای گراف‌ها تعریف کرد که معیاری مناسب برای سنجش کیفیت یک شبکهٔ تعاملی پروتئین است. اگر گراف اولیه $|E|$

یال و گراف توانی

|E'|

یال داشته باشد، نرخ فشرده‌سازی به این صورت محاسبه می‌شود:

c={\frac {|E|-|E'|}{|E|}}

.

نرخ فشرده‌سازی عددی بین ۰ و ۱ است. اگر تعداد یال‌های گراف توانی و گراف اولیه برابر باشند، نرخ فشرده‌سازی برابر ۰ است. بیشترین نرخ فشرده‌سازی مربوط به شبکه‌ای است که همهٔ رئوس آن به هم متصل اند؛ که این شبکه به یک یال توانی کاهش می‌یابد. گراف‌های توانی تا ۸۵ درصد یال‌ها را در شبکه‌های برهم‌کنش پروتئینی فشرده می‌کنند.

شبکه‌های اجتماعی

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

جستارهای وابسته

منابع

↑ Daminelli, Simone; Haupt, Joachim V.; Reimann, Matthias; Schroeder, Michael (26 Apr 2012). "Drug repositioning through incomplete bi-cliques in an integrated drug–target–disease network". Integrative Biology. 4 (7): 778–88. doi:10.1039/C2IB00154C. PMID 22538435.
↑ Royer, Loïc; Reimann, Matthias; Stewart, Francis A.; Schroeder, Michael (18 Jun 2012). "Network compression as a quality measure for protein interaction networks". PLOS One. 7 (6): e35729. Bibcode:2012PLoSO...735729R. doi:10.1371/journal.pone.0035729. PMC 3377704. PMID 22719828.
↑ George Tsatsaronis; Iraklis Varlamis; Sunna Torge; Matthias Reimann; Kjetil Nørvåg; Michael Schroeder; Matthias Zschunke (2011). "How to Become a Group Leader? or Modeling Author Types Based on Graph Mining". Research and Advanced Technology for Digital Libraries: International Conference on Theory and Practice of Digital Libraries, TPDL. Lecture Notes in Computer Science. Vol. 6966. SpringerLink. pp. 15–26. CiteSeerX 10.1.1.299.714. doi:10.1007/978-3-642-24469-8_4. ISBN 978-3-642-24468-1.
↑ Li, Li; Ruau, David J.; Patel, Chirag J.; Weber, Susan C.; Chen, Rong; Tatonetti, Nicholas P.; Dudley, Joel T.; Butte, Atul J. (30 April 2014). "Disease Risk Factors Identified Through Shared Genetic Architecture and Electronic Medical Records". Sci. Transl. Med. 6 (234): 234ra57. doi:10.1126/scitranslmed.3007191. PMC 4323098. PMID 24786325.

[inc_bicliques-1] Daminelli, Simone; Haupt, Joachim V.; Reimann, Matthias; Schroeder, Michael (26 Apr 2012). "Drug repositioning through incomplete bi-cliques in an integrated drug–target–disease network". Integrative Biology. 4 (7): 778–88. doi:10.1039/C2IB00154C. PMID 22538435.

[net_comp-2] Royer, Loïc; Reimann, Matthias; Stewart, Francis A.; Schroeder, Michael (18 Jun 2012). "Network compression as a quality measure for protein interaction networks". PLOS One. 7 (6): e35729. Bibcode:2012PLoSO...735729R. doi:10.1371/journal.pone.0035729. PMC 3377704. PMID 22719828.

[lncs-3] George Tsatsaronis; Iraklis Varlamis; Sunna Torge; Matthias Reimann; Kjetil Nørvåg; Michael Schroeder; Matthias Zschunke (2011). "How to Become a Group Leader? or Modeling Author Types Based on Graph Mining". Research and Advanced Technology for Digital Libraries: International Conference on Theory and Practice of Digital Libraries, TPDL. Lecture Notes in Computer Science. Vol. 6966. SpringerLink. pp. 15–26. CiteSeerX 10.1.1.299.714. doi:10.1007/978-3-642-24469-8_4. ISBN 978-3-642-24468-1.

[Li2014-4] Li, Li; Ruau, David J.; Patel, Chirag J.; Weber, Susan C.; Chen, Rong; Tatonetti, Nicholas P.; Dudley, Joel T.; Butte, Atul J. (30 April 2014). "Disease Risk Factors Identified Through Shared Genetic Architecture and Electronic Medical Records". Sci. Transl. Med. 6 (234): 234ra57. doi:10.1126/scitranslmed.3007191. PMC 4323098. PMID 24786325.