مقاله —d1253

دکتر منصور ذوالقدری جهرمی، استاد بخش مهندسی و علوم کامپیوتر و فناوری اطلاعات (رئیس کمیته). . . . .
دکتر ستار هاشمی، استادیار بخش مهندسی و علوم کامپیوتر و فناوری اطلاعات . . . . . . . . . .
دکتر اقبال منصوری، استادیار بخش مهندسی و علوم کامپیوترو فناوری اطلاعات. . . . . . . . . .
29756104361180
اسفند ماه 1391
تقدیم به خانواده عزیزم.

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

چکیده
استنتاج شبکه های تنظیمات ژنی از روی داده های سری زمانی Microarray به وسیله شبکه های بیزین دینامیک
به کوشش
علی مشهوری
شبکه های تنظیم کننده ژنتیکی مجموعه ای از ارتباطات ژن-ژن هستند که رابطه علت و معلولی را در فعالیت های ژنی ایجاد می کنند. دانش ما در مورد این شبکه ها نقش بسیار موثری در شناخت فرآیندهای زیستی ایفا می کند و می تواند باعث کشف روش های جدید برای درمان بیماری های پیچیده و تولید داروهای اثر گذار گردد.
روش های زیادی برای تشخیص شبکه های تنظیم کننده ژنتیکی پیشنهاد شده است. در این میان، شبکه های بیزین دینامیک مزایای ویژه ای دارا می باشند که باعث شده تا توجه زیادی را به خود جلب کنند.
با وجود تحقیقات انجام شده در این زمینه، مهندسی معکوس شبکه های تنظیم کننده ژن به وسیله شبکه های بیزین دینامیک به هیچ عنوان امری بدیهی نیست. غالباً تعداد نمونه های موجود برای آموزش مدل از تعداد مجهولات مسئله بسیار کمتر است. همچنین میزان پیچیدگی زیاد این مدل ها و دقت آنها از مهم ترین نواقص آن ها می باشند.
یکی از عمده ترین روش هایی که برای بالا بردن دقت شبکه های استنتاج شده به کار گرفته می شود استفاده از دانش اولیه در مورد شبکه های تنظیم کننده ژنی است. یکی از منابع عمده این دانش اولیه اطلاعات ما در مورد ساختار کلی شبکه های تنظیم کننده ژنی است. تحقیقات انجام شده نشان می دهند که تعداد یال های موجود در این شبکه ها کم است. همچنین شواهد بسیاری بدست آمده اند که نشان می دهند توزیع درجه خروجی در شبکه های تنظیم ژنی از قانون توانی پیروی می کنند. در واقع این شبکه ها در درجه خروجی scale-free هستند.
علیرغم این شواهد، روش های یادگیری شبکه های بیزین دینامیک این گونه شبکه ها را شبکه هایی با ساختار تصادفی در نظر می گیرند و یا تنها پیچیدگی شبکه را کنترل می کنند.
در این تحقیق روشی برای یاد گیری شبکه های بیزین دینامیک ارائه می شود که به طور مشخص بر این فرض شکل گرفته که شبکه واقعی ساختاری scale-free در توزیع درجه خروجی دارد. روش ارائه شده پیچیدگی زمانی چند جمله ای دارد و می تواند برای استنتاج شبکه هایی با تعداد گره های زیاد مورد استفاده قرار گیرد.
آزمایش هایی که برای مقایسه توانایی الگوریتم ارائه شده با متدهای قبلی یادگیری شبکه انجام شده اند نشان می دهند که الگوریتم ارائه شده، زمانی که برای استنتاج شبکه هایی استفاده می شود که scale-free هستند، قادر است کیفیت شبکه استنتاج شده را به خصوص زمانی که داده های آموزشی ناکافی هستند به صورت قابل توجهی افزایش دهد.
واژگان کلیدی: شبکه های بیزین دینامیک، شبکه های تنظیمات ژنی، ساختار Scale-Free

فهرست مطالب
عنوانصفحه
فصل اول: مقدمه1
ضرورت انجام کار6
نگاه کلی به فصول رساله6
فصل دوم: پیشینه تحقیق8
2-1- مقدمه 9
2-2- مقدمات زیستی9
2-2-1- ژن9
2-2-2- بیان ژن10
2-2-3- شبکه های تنظیم کننده ژنی11
2-3- روش های یاد گیری شبکه های تنظیم کننده ژنی12
2-3-1- روش های مبتنی بر خوشه بندی12
2-3-2- روش های مبتنی بر رگرسیون13
2-3-3- روش های مبتنی بر اطلاعات متقابل14
2-3-4- روش های تابعی14
2-3-5- روش های مبتنی بر تئوری سیستم14
2-3-6- روش های بیزین15
فصل سوم: روش پیشنهادی18
3-1- مقدمه19
3-2- شبکه های بیزین دینامیک20
3-3- یادگیری شبکه های بیزین دینامیک22
3-3-1- روش های امتیازدهی بیزین23
3-3-1-1- امتیازدهی به روش K225
3-3-1-2- امتیازدهی به روش BDe26
3-3-2- روش های امتیازدهی بر اساس تئوری اطلاعات26
3-3-2-1- امتیازدهی به روش log-likelihood (LL)27
3-3-2-2- امتیازدهی به روش BIC27
3-3-2-3- امتیازدهی به روش AIC28
3-3-2-4- امتیازدهی به روش MIT28
3-3-3- پیچیدگی زمانی یادگیری شبکه های بیزین دینامیک29
3-4- شبکه های تصادفی و شبکه های Scale-free31
3-5- روش پیشنهادی35
فصل چهارم: نتایج تجربی44
4-1- مقدمه45
4-2- روش های تولید شبکه های Scale-free46
4-3- روش های سنجش دقت برای شبکه های استنتاج شده50
4-4- آزمایش اول: استفاده از روش جستجوی کامل52
4-5- آزمایش دوم: نگاهی دقیق تر به عملکرد روش ارائه شده54
4-6- آزمایش سوم: استفاده از جستجوی حریصانه57
4-7- آزمایش چهارم: بازیابی قسمتی از شبکه تنظیمات ژنی در Yeast60
4-8- آزمایش پنجم: : عملکرد روش ارائه شده در بازیابی شبکه های تصادفی63
فصل پنجم: جمع بندی67
5-1- نتیجه گیری68
5-2- پیشنهاد برای کارهای آتی69
منابع تحقیق70
چکیده به زبان انگلیسی74
فهرست جدول ها
عنوان
صفحه
جدول 4-1- نتایج بدست آمده به وسیله روش های مختلف برای استنتاج شبکه های scale-freeبا استفاده از داده های آموزشی به طول 50
جدول 4-2- نتایج بدست آمده به وسیله روش های مختلف برای استنتاج شبکه های scale-free با استفاده از داده های آموزشی به طول 100 54
54

فهرست شکل ها
عنوان
صفحه
شکل 3-1- مثالی از دو شبکه های بیزین تشکیل دهنده یک شبکه بیزین دینامیک
شکل 3-2- قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک
شکل 3-3- شمای کلی توزیع دو جمله ای
شکل 3-4- شمای کلی توزیع قانون توانی
شکل 3-5- شبه کد الگوریتم ارائه شده برای یاد گیری شبکه های بیزین دینامیک با ساختار scale-free
شکل 3-6- شبه کد الگوریتم ارائه شده برای یاد گیری شبکه های بیزین دینامیک با ساختار scale-free با استفاده از روش جستجوی حریصانه
شکل 4-1- توزیع احتمالی درجه خروجی برای 1000 شبکه شامل 1000 گره تولید شده به وسیله الگوریتم شبیه سازی برای تولید شبکه های scale-free
شکل 4-2- توزیع احتمالی درجه ورودی برای 1000 شبکه شامل 1000 گره تولید شده به وسیله الگوریتم شبیه سازی برای تولید شبکه های scale-free
شکل 4-3- نمونه ای از شبکه جهت دار با ساختار scale-free
شکل 4-4- مقایسه بین نمونه های مختلف از الگوریتم پیشنهادی
شکل 4-5- نتایج بدست آمده به وسیله روش های مختلف برای استنتاج شبکه هایی با ساختار scale-free
شکل 4-6- قسمتی از زیر شبکه تنظیمات ژنی در Yeast
شکل 4-7- نتایج بدست آمده به وسیله روش های مختلف برای استنتاج قسمتی از زیر شبکه تنظیمات ژنی در Yeast
شکل 4-8- نتایج بدست آمده به وسیله روش های مختلف برای استنتاج شبکه های تصادفی 21
31
32
33
39
42
49
49
50
56
59
61
62
65
فصل اول

مقدمه
در هر سلول یک ارگانیزم زنده، هر لحظه، هزاران ژن با هم در ارتباط هستند تا فرآیندهای پیچیده زیستی را انجام پذیر سازند. شبکه های تنظیم کننده ژنتیکی مجموعه ای از قسمت های DNA در سلول می باشد که به طور غیر مستقیم (به وسیله RNA یا پروتئین های تولیدی) با یکدیگر و مواد دیگر درون سلول ارتباط دارند و بدین طریق سرعت رونویسی از روی ژن ها را برای تشکیل mRNA کنترل می کنند. هر مولکول mRNA یک پروتئین خاص با کارایی خاصی را تولید می کند. بعضی از پروتئین ها فقط برای فعال یا غیر فعال کردن ژن ها استفاده می شوند. این گونه پروتئین ها فاکتورهای رونویسی نامیده می شوند و اصلی ترین نقش را در شبکه تنظیم ژنی ایفا می کنند. به بیان دیگر شبکه تنظیم کننده ژنتیکی مجموعه ای از ارتباطات ژن-ژن است که رابطه علت و معلولی را در فعالیت های ژنی ایجاد می کند. دانش ما در مورد این شبکه ها نقش بسیار موثری در شناخت فرآیندهای زیستی ایفا می کند و می تواند باعث کشف روش های جدید برای درمان بیماری های پیچیده و تولید داروهای اثر گذار گردد. از این رو تشخیص و مهندسی معکوس شبکه های تنظیم کننده ژنتیکی به یکی از مهم ترین زمینه های تحقیقاتی تبدیل شده است [1].
عموماً برای تشکیل شبکه های تنظیم کننده ژنتیکی از داده های Microarray استفاده می کنند. Microarray یک تکنولوژی است که قابلیت اندازه گیری هم زمان میزان بیان mRNA مربوط به هزاران ژن را بوجود آورده است و می تواند اطلاعات مربوط به ارتباط ژن ها را در سطح ژنوم در اختیار ما قرار دهد [2]. اما راه حل ساده ای برای تشخیص شبکه های تنظیم کننده ژنتیکی از روی داده های Microarray وجود ندارد. در بیشتر موارد تعداد مجهولات مسئله بسیار زیاد است. این در حالی است که تعداد کمی داده در اختیار داریم. همچنین در بسیاری از موارد میزان خطا در اندازه گیری های موجود بالاست و یا با مشکل عدم وجود اندازه گیری برای بعضی از متغیرها مواجه هستیم.
داده های Microarray را می توان به دو نوع ایستا و سری زمانی تقسیم نمود. حالت اول تصویری است از بیان ژن ها در یک لحظه و شرایطی خاص. در حالت دوم بیان ژن ها در یک فرآیند درون سلولی در طول زمان اندازه گیری می شود. این سری های زمانی منعکس کننده فرآیندهای دینامیک درون سلولی هستند. اکثر روش های اولیه ای که برای آنالیز داده های سری زمانی Microarray استفاده می شدند در واقع روش هایی بودند که برای داده های ایستا طراحی شده بودند. در چند سال اخیر روش هایی برای کار با داده های سری زمانی به طور خاص مطرح شده اند که قادرند علاوه بر حل مشکلاتی که مخصوص داده های سری زمانی هستند، از ویژگی های منحصر به فرد این گونه داده ها نیز استفاده کنند. با این حال کار کردن با داده های سری زمانی نیازمند ظرافت و دقت بیشتری نسبت به داده های ایستا است و عمل مهندسی معکوس شبکه های تنظیم کننده ژنتیکی در این موارد مشکل تر است.
روش های زیادی برای تشخیص شبکه های تنظیم کننده ژنتیکی پیشنهاد شده اند که مهمترین آن ها عبارتند از: شبکه های بولین [3]، شبکه های بولین تصادفی [4]، معادلات دیفرانسیل [5] و شبکه های بیزین [6]. در این میان، شبکه های بیزین که قادرند رابطه علت و معلولی بین متغیر ها را بر اساس روابط احتمالاتی بیان کنند توجه زیادی را به خود معطوف کرده اند. به علت نویزی بودن داده های Microarray، استفاده از مدل های احتمالاتی به میزان زیادی می تواند کارایی مدل را افزایش دهد. علیرغم موفقیت نسبی شبکه های بیزین، عدم امکان وجود حلقه در این شبکه ها کارایی آنها را در بسیاری از موارد محدود می کند چون در شبکه های تنظیم کننده ژنتیکی واقعی حلقه های بازخورد متداول هستند. از این رو زمانی که با داده های سری زمانی مواجه هستیم شبکه های بیزین دینامیک به گزینه ای مناسب برای مدل کردن تبدیل می شود [7،8،9]. شبکه های بیزین دینامیک فرم عمومی تری از شبکه های بیزین هستند که می توانند داده های با تاخیرهای زمانی را مدل کنند.
شبکه های بیزین دینامیک مزایای ویژه ای دارا می باشند که باعث شده تا این مدل توجه زیادی را به خود جلب کند. اول اینکه در این نوع مدل قادر هستیم تا روابط علت و معلولی بین متغیر ها را مستقیماً نشان داده و از اطلاعات موجود در این مورد استفاده کنیم. دومین امتیاز این مدل ماهیت تصادفی آن است. فرآیند های مربوط به تنظیمات ژنی فرآیند های تصادفی هستند و حتی اگر خود این فرآیندها ذاتاً قطعی باشند، میزان زیاد خطا در اندازه گیری های انجام شده باعث می شوند تا فرآیند ها از دید ما تصادفی باشند. سومین موردی که باعث برتری این مدل می شود قابلیت این شبکه ها برای دنبال کردن تغییر متغیرها در طول زمان است.
علیرغم این ویژگی ها مهندسی معکوس شبکه های تنظیم ژن از روی داده های سری زمانی به وسیله شبکه های بیزین دینامیک به هیچ عنوان امری بدیهی نیست. غالباً تعداد نمونه های موجود برای آموزش مدل از تعداد مجهولات مسئله بسیار کمتر است [10]. همچنین در مقادیر اندازه گیری شده خطای زیادی وجود دارد و در مواردی برای بعضی از متغیرها اندازه گیری صورت نگرفته است. در حال حاضر در اکثر موارد در آزمایش هایی با تعداد کمی ژن یا داده های شبیه سازی شده به کار گرفته شده اند. میزان پیچیدگی زیاد این مدل ها و همچنین کمی دقت آنها از مهم ترین نواقص آن ها می باشند. برای بدست آوردن مدل هایی برای کار با داده های حجم بالا و افزایش کارایی مدل های تولید شده به تحقیقات بیشتری در این زمینه نیاز است.
یکی از عمده ترین روش هایی که برای بالا بردن دقت شبکه های استنتاج شده و جبران کمبود داده های آموزشی طی فرآیند یادگیری شبکه به کار گرفته می شود استفاده از دانش اولیه در مورد شبکه های تنظیم کننده ژنی است [11]. یکی از منابع عمده این دانش اولیه اطلاعاتی است که در مورد ساختار کلی شبکه های تنظیم کننده ژن بدست آمده است. تحقیقات انجام شده نشان می دهند که این شبکه ها از نظر ارتباطی خلوت هستند. به بیان دیگر تعداد یال های موجود در این شبکه ها کم است. همچنین شواهد بسیاری بدست آمده اند که نشان می دهند توزیع درجه خروجی در شبکه های تنظیم ژنی از قانون توانی پیروی می کنند [12،13]. در واقع این شبکه ها در درجه خروجی scale-free هستند. این در حالی است که درجه ورودی در آن ها از توزیع پواسن با میانگین کم پیروی می کند [14،15،16].
به زبان زیستی، در شبکه های تنظیم کننده ژنی بیان هر ژن توسط تعداد کمی ژن دیگر تنظیم می شود و همچنین اکثر ژن ها بر روی تعداد کمی ژن دیگر اثر تنظیم کنندگی دارند. اما، تعداد محدودی از ژن ها وجود دارند که بر روی بیان تعداد زیادی از ژن های دیگر اثر دارند. این ژن ها که عمده ترین نقش را در شبکه های تنظیم کننده ژنی بر عهده دارند hub نامیده می شوند.
با وجود اینکه شواهد بسیاری در تایید ساختار scale-free شبکه های تنظیم کننده ژنی بدست آمده است، تمامی روش های یادگیری شبکه های بیزین دینامیک این گونه شبکه ها را شبکه هایی با ساختار تصادفی در نظر می گیرند و یا تنها پیچیدگی شبکه را کنترل می کنند.
در این تحقیق روشی برای یاد گیری شبکه های بیزین دینامیک ارائه می شود که به طور مشخص بر این فرض شکل گرفته که شبکه واقعی ساختاری scale-free در توزیع درجه خروجی دارد. روش ارائه شده پیچیدگی زمانی چند جمله ای دارد و می تواند برای یادگیری شبکه هایی با تعداد گره های زیاد مورد استفاده قرار گیرد.
برای مقایسه توانایی الگوریتم ارائه شده با متدهای قبلی یادگیری شبکه از آزمایش های شبیه سازی متعددی استفاده شده است. نتایج این آزمایش ها نشان می دهند که الگوریتم ارائه شده، زمانی که برای یادگیری شبکه هایی استفاده می شود که scale-free هستند، قادر است کیفیت شبکه استنتاج شده را به صورت قابل توجهی افزایش دهد. هر چه اندازه داده های آموزشی کمتر باشد، تفاوت کیفیت شبکه استنتاج شده به وسیله الگوریتم ارائه شده با شبکه های استنتاج شده به وسیله الگوریتم های قبلی بیشتر می شود. همچنین زمانی که از این الگوریتم برای یاد گیری شبکه های با ساختار تصادفی استفاده می شود، الگوریتم ارائه شده قادر است تا شبکه هایی را بازیابی کند که از لحاظ مطابقت با شبکه واقعی معادل شبکه های استنتاج شده به وسیله روش های قبلی است.

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

فصل دوم

پیشینه تحقیق
2-1- مقدمه
دراین بخش ابتدا مفاهیم زیستی مربوط به این تحقیق مرور می شود. این مفاهیم شامل تعاریف و توضیحات مربوط به ژن، بیان ژن و شبکه های تنظیمات ژنی است. در قسمت بعدی این بخش روش های عمده برای استنتاج شبکه های تنظیم کننده ژنی معرفی شده، به اختصار توضیح داده می شوند.
مقدمات زیستی
در زیر به بیان مفاهیم مربوط به ژن، بیان ژن و شبکه های تنظیمات ژنی پرداخته می شود.
2-2-1- ژن
ژن قسمتی از DNA است که یک خصوصیت ویژه موروثی را کد می کند. دنباله های دیگر موجود در DNA اهداف ساختاری دارند و یا نقش تنظیم کننده را برای استفاده از اطلاعات ژن ها ایفا می کنند. طول یک ژن بر اساس تعداد بازهای موجود در آن بیان می شود و می تواند از چند صد تا چند صد هزار باز را شامل شود؛ اما به طور متوسط یک ژن شامل صد هزار تا صد و پنجاه هزار باز است.
یک ژن می تواند بیش از یک فرم داشته باشد که هر کدام یک آلل خوانده می شوند. آلل های مختلف می توانند خصوصیات فنوتیپیکی مختلفی را ایجاد کنند. برای مثال آلل های مختلف ژن مرتبط با رنگ چشم می توانند موجب ایجاد چشم با رنگ سبز یا قهوه ای شوند. با این وجود، بسیاری از اختلافات ژنی تأثیر قابل مشاهده ای ندارند.
ژن ها دستور العمل ساخت پروتئین یا RNA را کد می کنند. پروتئین ها مهم ترین واحد کاری سلول ها هستند و در تقریباً در تمام فرآیندهای سلولی نقش اساسی ایفا می کنند. گروهی از پروتئین ها ساختاری هستند و مسئولیت شکل دادن به سلول ها و بافت ها را بر عهده دارند. گروه دیگر پروتئین ها آنزیم هستند و باعث سرعت بخشیدن به واکنش های درون سلول می شوند. برخی از پروتئین ها نقش جا به جا کردن مولکول های دیگر را برعهده دارند و برخی دیگر مسئول ارسال و دریافت سیگنال هستند. یکی دیگر از نقش های مهم پروتئین ها تنظیم فرآیندهای درون سلول است.
2-2-2- بیان ژن
در تمامی ارگانیسم ها دو مرحله اصلی برای ساخت پروتئین از روی ژنی که آن پروتئین را کد می کند وجود دارد. در مرحله اول، طی فرآیندی به نام نسخه برداری، از روی DNA حاوی ژن مورد نظر RNA پیام رسان (mRNA) تولید می شود. در مرحله دوم که ترجمه نام دارد، از روی mRNA پروتئین ساخته می شود. فرآیندی که طی آن یک مولکول عملیاتی زیستی از نوع RNA یا پروتئین تولید می شود بیان ژن نام دارد. مولکول تولید شده محصول ژن خوانده می شود.
2-2-3- شبکه های تنظیم کننده ژنی
یک شبکه تنظیمات ژنی مجموعه ای است از قسمت هایی از DNA که به طور غیر مستقیم، از طریق محصول ژنی که می تواند پروتئین یا RNA باشد، با یکدیگر و مواد دیگر درون سلول در تعاملند و در نتیجه این تعامل نرخ تولید mRNA از روی ژن ها را کنترل می کند. قبلاً اشاره شد که پروتئین ها نقش های مختلف و اساسی در سلول ایفا می کنند. بعضی از پروتئین ها وظیفه فعال یا غیر فعال کردن ژن ها را بر عهده دارند. به این گونه پروتئین ها فاکتورهای رونویسی گفته می شود و نقش اصلی را در شبکه های تنظیم ژنی بازی می کنند.
در پیش هسته ای ها، شبکه های تنظیمات به محیط خارجی سلول واکنش نشان می دهند و بدین وسیله شرایط را برای زنده ماندن سلول در آن محیط فراهم می سازند. در ارگانیسم های چند سلولی مانند حیوانات همین شبکه ها شکل بدن را کنترل می کنند. در فرآیند تقسیم سلولی، ژنوم سلول های فرزند به طور کامل با ژنوم سلول مولد یکی است اما ژن هایی که در هر یک از این سلول ها فعالند می توانند با هم متفاوت باشند.
یکی از ویژگی های مهم حیوانات چند سلولی استفاده از گرادیان های مورفوژنی است که یک سیستم مکان یابی را بوجود می آورند که به سلول اطلاع می دهد که در چه نقطه ای از بدن قرار گرفته است و متعاقباً چه ویژگی هایی باید داشته باشد.
ژنی که در یک سلول فعال می شود می تواند پروتئینی تولید کند که از سلول خارج شده و وارد سلول های مجاور شود و زمانی که میزان آن در سلول مقصد به میزان مشخصی بیشتر شد ژن های خاصی را در آن سلول فعال سازد. در این مرحله ممکن است سلول مقصد در اثر فعال شدن ژن های جدید محصولی تولید کند که بر روی سلول اولیه تأثیر گذارد.
در فواصل طولانی تر مورفوژن ها می توانند از فرآیند انتقال سیگنال استفاده کنند. چنین سیگنال هایی ایجاد یک نقشه از بدن را کنترل می کنند. همچنین از طریق فرآیندهای بازخورد نگه داری یک بدن بالغ را کنترل می کنند. اختلال چنین بازخوردهایی که به علت جهش های ژنتیکی بوجود می آیند می تواند باعث ایجاد سرطان شود.
همچنین به موازات این فرآیندها شبکه تنظیمات می تواند ژن هایی را فعال سازد که پروتئین های ساختاری تولید می کنند و باعث می شوند تا سلول خصوصیات فیزیکی مورد نیاز را پیدا کند.
یک شبکه تنظیمات ژنی می تواند چنین توصیف شود:
ژن ها می توانند به عنوان گره های شبکه دیده شوند که ورودی آن ها پروتئین ها (فاکتورهای نسخه برداری) و خروجی آن ها میزان بیان ژن است. خود گره ها می توانند به صورت توابعی تفسیر شوند که با انجام عملیات بر روی ورودی ها خروجی را تولید می کنند. انجام این فرآیند عملکرد مولکولی را مشخص می کند.
در عمل، معمولاً تمامی گره ها ژن در نظر گرفته می شوند و ورودی هر ژن نیز از ژن های دیگری می آید که به طور مستقیم، از طریق محصولات پروتئینی، بر فعالیت آن ژن تاثیر می گذارند.
روش های یاد گیری شبکه های تنظیم کننده ژنی
برای استنتاج شبکه های تنظیم کننده ژنی با استفاده از داده های بیان ژن از روش های متعددی استفاده شده است. این روش ها در سطحی که ارتباطات بین ژن ها را مدل می کنند و همچنین در قابلیت مدل کردن فرآیند های طبیعی و واقعی که در شبکه های تنظیم کننده ژنی روی می دهند با هم تفاوت دارند. در زیر به اختصار چندین روش عمده که برای استنتاج شبکه های تنظیم کننده ژنی ارائه شده اند معرفی می شود.
2-3-1- روش های مبتنی بر خوشه بندی
خوشه بندی روشی است که در آن ژن ها بر اساس تشابه بیان ژن گروه بندی می شوند. بدین معنا که اگر بیان دو ژن به صورت تقریبی با هم زیاد یا کم می شوند، این دو ژن در یک گروه قرار می گیرند. در برخی از روش های خوشه بندی تعداد گره ها به عنوان پارامتر ورودی باید به الگوریتم داده شود. در روش های نوین تر تعداد خوشه ها بر اساس خود داده ها بدست می آیند.
استفاده از روش های خوشه بندی برای استنتاج شبکه های تنظیم کننده ژنی در [17] توضیح داده شده است. در روش ارائه شده از خوشه بندی سلسله مراتبی برای بدست آوردن اطلاعات در مورد ژن ها استفاده شده است.
در [18] برای کاهش تعداد ژن های مسئله از 18432 ژن به 6 گروه ژنی استفاده شده است و سپس تلاش شده است تا ارتباط بین ژن ها در این 6 گروه مشخص شود.
در [19] روش های سنتی خوشه بندی ارتقاء یافته اند. در روش ارائه شده در این تحقیق هر ژن می تواند متعلق به چندین خوشه باشد.
ایراد عمده روش مبتنی بر خوشه بندی این است که این روش ارتباط بین ژن ها را در سطح خیلی بالایی مشخص می کند. در واقع، استفاده از این روش ارتباط بین گروه های مختلف ژنی، نه ارتباط بین خود ژن ها، را مشخص می کند. ایراد دیگر این گونه روش ها این است که در برخی از آن ها باید تعداد خوشه ها از قبل مشخص گردند. همچنین پس از اینکه گروه ها مشخص شدند، راه مطمئنی برای ارزیابی دقت و صحت گروه ها وجود ندارد.
2-3-2- روش های مبتنی بر رگرسیون
تکنیک های رگرسیون روش های آماری هستند که برای فهمیدن روابط بین متغیرهای مستقل و وابسته استفاده می شوند. رگرسیون معمولاً شامل حل کردن و یا تخمین بهترین حل برای مجموعه ای از معادلات است که رفتار متغیرها را مشخص می کنند.
در [20] مسئله استنتاج شبکه های تنظیم کننده ژنی به دو قسمت تقسیم شده است: در مرحله اول تعدادی راه حل برای مسئله به وسیله singular value decomposition بوجود می آیند. سپس از رگرسیون استفاده می شود تا بهترین شبکه از میان راه حل ها انتخاب شود. در تحقیق ارائه شده در [21] از روش رگرسیون بیزین برای انتخاب شبکه با تعداد ارتباطات محدود استفاده شده است.
2-3-3- روش های مبتنی بر اطلاعات متقابل
اطلاعات متقابل روشی آماری است که میزان وابستگی بین دو متغیر را اندازه گیری می کند. اطلاعات متقابل بر اساس تفاضل بین مجموعه آنتروپی دو متغیر و آنتروپی شرطی یک متغیر بر حسب متغیر دیگر تعریف می شود. آنتروپی می تواند برای متغیر های گسسته و پیوسته تعریف شود [22].
از روش های مبتنی بر اطلاعات متقابل برای استنتاج شبکه های تنظیم کننده ژنی در [22] استفاده شده است.
2-3-4- روش های تابعی
در روش های تابعی سعی بر این است که تغییرات در بیان هر ژن بر اساس تابعی (معمولاً بولین) از تغییرات در ژن های دیگر مدل شود. برای این منظور، معمولاً از شبکه های بولین استفاده می شود.
الگوریتم REVEAL برای یادگیری شبکه های بولین از شناخته شده ترین روش ها برای استنتاج شبکه های تنظیمات ژنی از روی داده های بیان ژن است [23]. در این روش بر اساس ارتباط متقابل بین بیان ژن ها برای رفتار هر ژن تابع بولینی ایجاد می شود . از این توابع برای تشخیص ژن هایی که بر روی رفتار ژن مورد نظر تاثیر دارند استفاده می شود. اثبات ریاضی این مدل و همچنین آنالیز پیچیدگی محاسباتی برای آن در تحقیقات بعدی ارائه گردید [24]. به مدل های بعدی که در این زمینه ارائه شدند این قابلیت افزوده شد که بتوانند ارتباطات بین متغیر هایی با بیش از دو مقدار را مدل کنند [25].
2-3-5- روش های مبتنی بر تئوری سیستم
در حالی که اغلب روش های استنتاج شبکه از روش پایین به بالا برای ساختن شبکه استفاده می کنند، روش های مبتنی بر تئوری سیستم از روش مخالف، یعنی بالا به پایین، استفاده می کنند. در این گونه روش ها، شبکه به ماژول های مختلف دسته بندی می شود و تلاش می شود تا ارتباطات بین این ماژول های سطح بالا مشخص شود. برای ماژوله کردن شبکه می توان از دانش قبلی در مورد شبکه استفاده کرد و یا اینکه این کار را از طریق روش های خوشه بندی انجام داد [26].
2-3-6- روش های بیزین
روش های بیزین روش هایی هستند که بر احتمال همبستگی سطوح بیان برای ژن های مختلف تکیه دارند. برای ساختن شبکه در این روش ها، هر کدام از ژن ها یک متغیر تصادفی در نظر گرفته می شود. سپس سعی می شود تا توزیع احتمالی که رفتار این متغیرها را توصیف می کند بدست آید. وابستگی های موجود در بهترین توریع ارتباط بین ژن ها را مشخص می کند.
ابزار مورد استفاده در روش های بیزین، شبکه های بیزین هستند. از شبکه های بیزین برای اولین بار در تحقیق انجام شده به وسیله Friedman برای بازیابی شبکه های تنظیمات ژنی استفاده شد [6]. در [27] هر کدام از یال های شبکه بیزین عنوان گذاری شدند تا نوع ارتباط بین ژن ها مشخص شود. ارتباط یک ژن با ژن دیگر می تواند باعث افزایش و یا کاهش فعالیت ژن تاثیر پذیرنده شود.
یکی از محدودیت های شبکه های بیزین این است که امکان تعیین قطعی جهت ارتباط بین دو ژن حین یادگیری شبکه وجود ندارد. مشکل دیگر این است که چون روش های بیزین روش های آماری هستند و میزان داده های آموزشی که برای یاد گیری شبکه های تنظیم کننده ژنی استفاده می شوند کم است، شبکه های استنتاج شده توسط این روش ها به ناهنجاری های داده های آموزشی حساس هستند. مشکل دیگر این است که امکان مدل کردن ارتباط های حلقه ای (مانند چرخه های بازخورد در شبکه های تنظیم کننده ژنی) در شبکه های بیزین وجود ندارد.
برای رفع برخی از مشکلات مطرح شده در مورد شبکه های بیزین، در تحقیقات بعدی از شبکه های بیزین دینامیک استفاده شد [28،29]. این شبکه ها می توانند برای استنتاج شبکه های تنظیم کننده ژن از روی داده های سری زمانی بیان ژن مورد استفاده قرار گیرند. در این شبکه ها، جهت هر یال مشخص و قطعی است. همچنین شبکه های بیزین دینامیک قابلیت مدل کردن ارتباطات حلقه ای را دارند.
در [28]، شبکه های بیزین دینامیکی را برای مدل کردن واکنش هایی که به علت تغییرات فیزیولوژیکی درEscherichia coli رخ می دهند تولید کردند. در این روش از دانش بیولوژی برای گروه بندی ژن هایی که با یکدیگر رونویسی می شوند و در نتیجه co-regulated هستند استفاده شده بود. این عمل باعث کاهش تعداد پارامترهای مسئله و افزایش کارایی این مدل شد. این متد بر روی 169 ژن در 9 پترن از E.Coli آزمایش شد و توانست correlation های موجود در 4 پترن از 9 پترن را به درستی شناسایی کند.
[7] شبکه بیزین دینامیکی را ارائه کرد که شامل متغیرهای پنهان بود تا بدین طریق مشکل نویزهای بیولوژیکی و نویزهای اندازه گیری را حل کند. این مدل از یکی از انواع مدل های رگرسیون خطی و نویز با توزیع نرمال استفاده می کند. روش قید شده بر روی شبکه ترمیم DNA در E.Coli با تمرکز بر روی 8 ژن اصلی آزمایش شد و نتایج بدست آمده نشان داد که این مدل قادر است تا مدارهای اصلی تنظیمات ژنی را استخراج کند.
در [30] از شبکه بیزین دینامیک برای مدل کردن زیر شبکه ای از 45 ژن در سیستم چرخه سلولی Yeast استفاده شد. با مقایسه شبکه بدست آمده در این آزمایش و شبکه ای که قبلاً در پایگاه داده KEGG موجود بود، نویسندگان این تحقیق نتیجه گرفتند که شبکه بیزین دینامیک تعداد زیادی از یال های موجود در شبکه را به درستی استخراج می کند.
برای آزمایش کردن کاربرد شبکه های بیزین دینامیک در کار با داده های بیان ژن و اندازه گیری دقت آن در [10] آزمایشی مبتنی بر شبیه سازی انجام شد. بر خلاف کار با داده های بیولوژیکی واقعی، هنگام کار با داده های شبیه سازی شده ساختار واقعی شبکه تولید کننده داده ها مشخص است و مقایسه کامل شبکه بدست آمده با شبکه اصلی به سادگی امکان پذیر می باشد. نتایج بدست آمده نشان داد که در حالی که ساختار کلی شبکه بدست آمده مفید نیست، ساختار های محلی تا اندازه ای بازیابی می شوند.
در [8] از شبکه بیزین دینامیک با تأخیرهای زمانی مختلف استفاده شده است. در این روش از شیفت دادن سری های زمانی به اندازه مشخص پیش بینی شده استفاده شد و این روش بر روی داده های چرخه سلولی Yeast به کار گرفته شد.
در [31] از اطلاعات متقابل بین پروفایل های بیان دو ژن و تست χ2 برای تشخیص درجه اهمیت اطلاعات متقابل برای تصمیم گیری در مورد ساختار شبکه استفاده شده است.
در [32] از نگرشی مشابه اطلاعات متقابل استفاده شد؛ اما در این تحقیق اصل کوتاه ترین طول توصیف برای بدست آوردن آستانه اهمیت و حذف یال ها اضافی بکار گرفته شد. با این حال به علت استفاده کردن از قالب های کد کردن مختلف این روش شبکه های غیر یکتایی را تولید می کند.
[33] بر این مشکل با استفاده از اندازه گیری طول توصیف بر اساس یک مدل کلی غلبه یافت. مدل کلی در این تحقیق شباهت بیشینه نرمال شده می باشد.

فصل سوم

روش پیشنهادی
3-1- مقدمه
همان گونه که در فصل قبل عنوان شد، شبکه های بیزین دینامیک از عمده ترین مدل هایی هستند که برای استنتاج شبکه های تنظیمات ژنی استفاده می شوند. از مزایای شبکه های بیزین دینامیک می توان به توانایی مدل کردن ماهیت تصادفی رفتار شبکه های تنظیمات ژنی، توانایی مدل کردن حلقه های بازخورد و قابلیت استفاده از منابع اطلاعاتی مختلف برای استنتاج شبکه اشاره کرد.
یکی از منابع اطلاعاتی مهم که برای استنتاج دقیق تر شبکه های تنظیمات ژنی می تواند مورد استفاده قرار گیرد ساختار کلی این گونه شبکه ها است. ویژگی اصلی که در این تحقیق مورد استفاده قرار می گیرد این است که درجه خروجی گره ها (ژن ها) در شبکه های تنظیمات ژنی از توزیع سری-توانی پیروی می کند. این بدین معنی است که احتمال اینکه فعالیت یک ژن بر روی فعالیت K ژن دیگر اثر داشته باشد را می توان با توزیع P(k)∝k-α تخمین زد. گراف هایی که این خاصیت را دارند، گراف های scale-free خوانده می شوند.
در این تحقیق، با تمرکز بر روی ویژگی scale-free بودن شبکه های تنظیمات ژنی و استفاده از شبکه های بیزین دینامیک، الگوریتمی ارائه می گردد که می تواند با پیچیدگی محاسباتی چند جمله ای شبکه اصلی را با دقت بالایی نسبت به روش های متداول استنتاج کند.
مطالب ارائه شده در این فصل عبارتند از: در قسمت اول این بخش به مرور مفاهیم و تعاریف مربوط به شبکه های بیزین دینامیک پرداخته می شود و همچنین روش های یاد گیری متداول این گونه شبکه ها بررسی می شوند. در قسمت بعد شبکه های scale-free معرفی خواهند شد و خواص این شبکه ها با شبکه های تصادفی مقایسه خواهند شد. در قسمت آخر این فصل الگوریتم پیشنهادی برای یادگیری شبکه های بیزین دینامیکی که درجه خروجی در آن ها از سری توانی پیروی می کنند ارائه خواهد شد.
3-2- شبکه های بیزین دینامیک
شبکه های بیزین دینامیک [34،35] گونه ارتقاء یافته ای از شبکه های بیزین هستند که قابلیت مدل کردن فرآیندهایی که در طول زمان رخ می دهند را دارند. برای این منظور زمان باید به گام های گسسته تقسیم گردد. همچنین فرآیندی که توسط این شبکه ها مدل می شود، باید فرض Markov را ارضا کنند. به بیان ساده، مقادیر بعدی متغیرهای سیستم باید فقط به مقادیر فعلی این متغیرها وابسته باشد و از مقادیر آن ها در گام های زمانی قبلی مستقل باشد. بدین طریق، شبکه های بیزین دینامیک قادر هستند تا علاوه بر رابطه بین متغیرها در یک گام زمانی، رابطه آن ها در گام های زمانی متوالی را نیز نشان دهند.
فرض کنید که Z={Z1,Z2,…,ZN} مجموعه ای از N متغیر و Zt مجموعه ای از مقادیر این متغیرها در گام زمانی t می باشد. یک شبکه بیزین دینامیک از دو شبکه بیزین مجزا (B1,B→) تشکیل شده است. B1 شبکه بیزینی است که رابطه متغیرهای موجود در مجموعه Z در اولین گام زمانی را نمایش می دهد. به بیان دیگر، B1 نشان دهنده توزیع توام متغیرهای مجموعه Zt است. B→ یک شبکه بیزین دو قطعه زمانی است که رابطه بین متغیرها در گام های زمانی متوالی را نشان می دهد. به عبارت دقیق تر، B→ نشان دهنده توزیع توام P(Zt|Zt-1) برای گام های زمانی دوم به بعد است. شایان ذکر است که توزیع P(Zt|Zt-1) برای تمامی گامهای زمانی یکسان است و تغییری نمی کند. شکل 3-1 مثالی از این دو شبکه را نمایش می دهد.

شکل 3-1- مثالی از دو شبکه های بیزین تشکیل دهنده یک شبکه بیزین دینامیک
با توجه به استقلال بین متغیرها که به وسیله یک شبکه بیزین دینامیک نمایش داده می شود، P(Zt|Zt-1) بصورت زیر فاکتورگیری می شود:
P(Zt|Zt-1) = i=1NP(Zti|π(Zti))(3-1)
π(Zti) تابعی است که مجموعه ای شامل والدهای متغیر Zti را برمی گرداند. اعضای این مجموعه می توانند متغیر های در گام زمانی فعلی (t)، و یا گام زمانی قبلی (t-1) باشند. در یک شبکه بیزین دینامیک، به یال هایی که روابط بین متغیرها را در یک گام زمانی نشان می دهند یال های درون گام گفته می شود و یال هایی که روابط بین متغیر ها را در گام های متوالی نشان می دهند یال های بین گامی نامیده می شوند.
با در نظر گرفتن فرض Markov و همچنین فرمول (3-1)، برای توزیع توام تمامی متغیر ها در طول کل فرآیند داریم:
PZ1, Z2,…ZT=P(Z1) t=2TP(Zt|Zt-1)= t=1Ti=1NP(Zti|π(Zti))(3-2)
3-3- یادگیری شبکه های بیزین دینامیک
الگوریتم هایی که برای یاد گیری شبکه های بیزین دینامیک استفاده می شوند را می توان به دو دسته تقسیم بندی کرد:
الگوریتم هایی که بر اساس روش جستجو و ارزیابی عمل می کنند.
الگوریتم هایی که بر اساس شبیه سازی Markov Chain Monte Carlo (MCMC) استفاده می کنند.
الگوریتم هایی که جزء دسته اول طبقه بندی می شوند کیفیت یک شبکه بیزین دینامیک را، با توجه به داده های آموزشی، بر اساس امتیازی که به آن شبکه اختصاص می دهند می سنجند. در واقع در این گونه الگوریتم ها، هدف یافتن شبکه ای با بالا ترین امتیاز است. بنابر این اگر G* نشان دهنده بهترین شبکه باشد، داریم:
G*=argmax ScoreG;D(3-3)
ScoreG;D تابعی است که یک شبکه را بر اساس داده های آموزشی ارزیابی می کند و یک عدد حقیقی را به عنوان امتیاز آن شبکه باز می گرداند.
روش های امتیازدهی به شبکه به دو دسته تقسیم می شوند: روش های امتیازدهی بیزین، و روش های امتیازدهی بر اساس تئوری اطلاعات. در ادامه به معرفی این روش ها پرداخته می شود.
3-3-1- روش های امتیازدهی بیزین
در روش های امتیازدهی بیزین از فرمول بیز برای سنجش کیفیت یک شبکه استفاده می شود. طبق فرمول بیز، احتمال صحت یک شبکه بر اساس داده های آموزشی برابر است با:
PG|D=P(D|G)P(G)P(D)(3-4)
در فرمول بالا، P(G) نشان دهنده میزان باور قبلی ما به صحت شبکه G و P(D|G) نشان دهنده میزان احتمال داده های آموزشی با فرض تولید این داده ها به وسیله شبکه G می باشد. P(D) احتمال حاشیه ای داده های آموزشی را نشان می دهد که برای تمامی شبکه ها مقدار ثابتی است. چون بهترین شبکه مستقل از این احتمال است، می توان آن را در نظر نگرفت و برای یافتن بهترین شبکه از فرمول زیر استفاده کرد:
PG|D∝P(D|G)P(G)(3-5)
در روش های امتیازدهی بیزین در عمل از لگاریتم (3-4) برای امتیاز دهی استفاده می شود.
ScoreG;D∝logPDG+logP(G)(3-6)
P(G) توزیع احتمالی اولیه بر روی ساختار شبکه است و میزان باور اولیه ما را برای صحت شبکه G نشان می دهد. یکی از روش های متداول برای تعریف این احتمال، استفاده از ماتریس احتمالی یال ها می باشد. برای شبکه ای متشکل از N متغیر، ماتریس احتمالی یال ها ماتریسی N×N است که عنصر (i,j)ام آن برابر است با احتمال اولیه اینکه در شبکه متغیر iام والد متغیر jام باشد. در این صورت، اگر ماتریس احتمالی یال ها را با E و عنصر (i,j)ام آن را با eij نشان دهیم، P(G) چنین تعریف می شود:

 برای دانلود فایل کامل به سایت منبع مراجعه کنید  : omidfile.com

یا برای دیدن قسمت های دیگر این موضوع در سایت ما کلمه کلیدی را وارد کنید :

 

PG= i=1Nj=1NeijIij×(1-eij)1-Iij(3-7)
Iij نشانگری است که اگر در شبکه بین متغیر iام و متغیر jام یالی وجود داشته باشد، مقدار یک می گیرد و در غیر این صورت، مقدار آن برابر با صفر است.
در فرمول (3-6)، زمانی که پارامترهای توزیع های احتمال شرطی شبکه G نامعلوم هستند، مقدار P(D|G) از فرمول زیر بدست می آید:
PDG= θP(D|G,θ)P(θ)dθ(3-8)
برای شبکه های بیزین با متغیرهای گسسته، توزیع های مربوط به P(θ) را از خانواده توزیع های Dirichlet انتخاب می کنند. توزیع Dirichlet این گونه تعریف می شود:
Pθ1,θ2,…,θK-1,α1,α2,…,αK= i=1KΓ(αi)Γ(i=1Kαi)i=1Kθiαi-1(3-9)
θi متغیرهای تصادفی هستند که باید دو شرط زیر را ارضا کنند:
θ1,θ2,…,θK> 0
i=1Kθi=1(3-10)
αi ها پارامترهای توزیع هستند و می توانند مقادیری بزرگ تر از صفرداشته باشند.
همان گونه که در بالا ذکر شد، برای شبکه های بیزین با متغیرهای گسسته، توزیع های مربوط به P(θ) را از خانواده توزیع های Dirichlet انتخاب می کنند. در این حالت، بعد از انتگرال گیری در فرمول (3-8)، PDG برابر می شود با:
PDG=i=1Nj=1qiΓ(Nij')Γ(Nij+Nij')k=1riΓ(Nijk+Nijk')Γ(Nijk')(3-11)
در فرمول بالا، qi برابر با تعداد حالات مختلف برای مقداردهی به والدهای متغیر iام است و ri تعداد مقادیری که خود این متغیر می تواند داشته باشد. Nijk برابر است با تعداد دفعاتی که متغیر iام مقدار kام را در دامنه خود داشته است به شرطی که مقادیر والدهای این متغیر در حالت jام باشند. Nijk' پارامتر توزیع Dirichlet مربوط به متغیر iام، در حالتی که والدهای این متغیر در حالت jام باشند، است. همچنین داریم: Nij'= k=1riNijk' و Nij= k=1riNijk.
3-3-1-1- امتیازدهی به روش K2
در صورتی که در فرمول (3-11) تمامی پارامترهای توزیع برابر یک قرار داده شوند، PDG معادل تابع امتیازدهی K2 می شود. در این حالت داریم:
PDG=i=1Nj=1qi(ri-1)!Nij+ri-1!k=1riNijk!(3-12)
3-3-1-2- امتیازدهی به روش BDe
اگر در فرمول (3-11) Nijk' مطابق فرمول زیر تعریف شود، PDG معادل تابع امتیازدهی BDe می شود.
Nijk'=N'×P(Zi=k, πZi=j|G)(3-13)
در فرمول بالا، شرط Zi=k یعنی متغیر iام مقدار kام خود را داشته باشد و πZi=j یعنی مجموعه مقادیر والدهای متغیر iام در حالت jام خود باشد. N' میزان باور ما را به توزیع اولیه نشان می دهد.
3-3-2- روش های امتیازدهی بر اساس تئوری اطلاعات
روش های بر گرفته شده از تئوری اطلاعات که برای امتیازدهی شبکه های بیزین استفاده می شوند، بر اساس فشرده سازی اطلاعات عمل می کنند.در این گونه روش ها، کیفیت یک شبکه بیزین متناسب است با میزانی که شبکه قادر است با توجه به کدی که تولید می کند داده های آموزشی را فشرده سازی کند. کدی که یک شبکه بیزین تولید می کند بر اساس ساختار گراف شبکه و گزاره های استقلال یا عدم استقلال بین متغیرها که توسط یال های گراف مشخص می شود، تعیین می گردد. حد نهایی فشرده سازی اطلاعات طبق تئوری شانون مشخص می شود. طبق این تئوری، وقتی تعداد نمونه های مستقل با توزیع یکنواخت یک مجموعه به بینهایت میل می کند، هیچ روش فشرده سازی قادر نیست، بدون از دست دادن اطلاعات، پیغامی را با طولی کوتاه تر از اندازه ای که با آنتروپی شانون مشخص می شود ایجاد کند.
کدهای متعددی هستند که به صورت حدی می توانند پیغامی را تولید کنند که اندازه آن به اندازه ای که با آنتروپی شانون مشخص می شود میل کند. برای ساختن چنین کدی باید یک توزیع احتمالی بر روی داده ها تعریف شود. این توزیع احتمالی به صورت قطعی می تواند توسط یک شبکه بیزین مشخص گردد. بر همین اساس، روش های امتیاز دهی زیر تعریف می شوند.
3-3-2-1- امتیازدهی به روش log-likelihood (LL)
تابعی که در این روش امتیازدهی استفاده می شود چنین تعریف می شود:
LLGD=i=1Nj=1qik=1riNijklog(NijkNij)(3-14)
مشکل اصلی این تابع این است که هر چه در شبکه تعداد یال بیشتری وجود داشته باشد، شبکه امتیاز بیشتری می گیرد. در واقع در این روش امتیازدهی، شبکه ای که در آن تمامی یال ها وجود دارند و گراف شبکه یک گراف کامل است، بیشترین امتیاز را می گیرد. برای رفع این مشکل از امتیازی که توسط این تابع برای یک شبکه بدست می آید مقداری را به عنوان جریمه کسر می کنند. این مقدار وابسته است به میزان پیچیدگی یک شبکه. هر اندازه که تعداد یال های یک شبکه بیشتر باشد، پیچیدگی آن شبکه نیز بیشتر است و امتیاز مربوط به آن شبکه جریمه بیشتری می گیرد.
3-3-2-2- امتیازدهی به روش BIC
در این روش امتیازی که یک شبکه می گیرد برابر است با:
BICGD=LLGD-logM2|G|(3-15)
در فرمول بالا، M تعداد نمونه های آموزشی است و |G| برابر با تعداد متغیرهای مستقل مورد نیاز برای تعریف کامل شبکه G است. تعداد این پارامترها برابر است با:
G=i=1N(ri-1)qi(3-16)
3-3-2-3- امتیازدهی به روش AIC
این روش امتیاز دهی شباهت بسیار زیادی به روش امتیازدهی قبلی دارد. تفاوت این دو روش در این است که در روش AIC جریمه کمتری برای پیچیدگی شبکه در نظر گرفته می شود که مستقل از تعداد نمونه های آموزشی است.
BICGD=LLGD-|G|(3-17)
3-3-2-4- امتیازدهی به روش MIT
این روش امتیازدهی بر اساس اطلاعات متقابل عمل می کند. در این روش، کیفیت یک شبکه بیزین به صورت زیر ارزیابی می شود:
MITGD=i=1N2T×IZi,πZi-j=1siχα,liσi(j)(3-18)
در این فرمول، تابع IZi,πZi مقدار اطلاعات متقابل بین یک گره در یک شبکه بیزین و والدهای آن متغیر را بر می گرداند. α سطح significance را برای توزیع Chi-square مشخص می کند.

3-3-3- پیچیدگی زمانی یادگیری شبکه های بیزین دینامیک
اگر یال هایی که روابط متغیرها را در یک گام زمانی نشان می دهند در نظر نگیریم و ساختار یک شبکه بیزین دینامیک را به یال هایی که روابط متغیرها در گام های زمانی مختلف نشان می دهند محدود کنیم، برای N متغیر، تعداد 2N2 شبکه بیزین دینامیک یکتا می توان ایجاد کرد. در واقع تعداد شبکه های بیزین دینامیکی که با N متغیر می توان ساخت، به صورت فرانمایی با N رشد می کند. برای مثال، برای تنها 10 متغیر بیش از 1030 شبکه بیزین دینامیک مختلف وجود دارد. چنین فضایی باعث می شود که حتی برای مسائلی با تعداد متغیر کم، پیدا کردن بهترین شبکه امکان پذیر نباشد. به عنوان راه حلی برای این مشکل، معمولاً از روش های جستجوی محلی برای پیدا کردن شبکه ای با امتیاز بیشینه محلی استفاده می شود. روش های جستجوی محلی که برای این منظور استفاده می شوند عبارتند از: Greedy Search، Simulated annealing، Hill climbing و روش های جستجو بر اساس الگوریتم ژنتیک.
با وجود اینکه تعداد شبکه های بیزین دینامیک برای N متغیر برابر 2N2 است، اگر تابعی که برای امتیازدهی شبکه ها استفاده می شود خاصیت ویژه ای را با عنوان تفکیک پذیری دارا باشد، این امکان فراهم می شود که بتوان بهترین شبکه را با جستجو در فضایی بسیار کوچک تر پیدا کرد. یک تابع امتیازدهی زمانی تفکیک پذیر است که شرط زیر را ارضا کند:
ScoreG;D= i=1NScore(Zi,π(Zi);D)(3-19)
با توجه به فرمول (3-19)، یک تابع امتیازدهی زمانی تفکیک پذیر است که امتیازی که به یک شبکه اختصاص می دهد را بتوان به صورت حاصل جمع مقادیری بیان کرد که هر کدام فقط به یکی از متغیرها و والدهای آن متغیر وابسته است. در چنین حالتی، بهترین مجموعه والدها برای یک متغیر از ساختار باقی شبکه مستقل است و می توان والدهای هر متغیر را به صورت مجزا پیدا کرد. در اینجا باید اشاره شود که تمامی توابع امتیازدهی که در بخش (3-3) معرفی شدند توابع امتیازدهی تفکیک پذیر هستند و می توان مقدار نهایی امتیازی را که هر یک از آن ها به یک شبکه اختصاص می دهند به صورت مجموع امتیازاتی که به گره های شبکه اختصاص می دهند در نظر گرفت.
اگر فرض شود که تابع امتیازدهی تفکیک پذیر است، فضای جستجو برای پیدا کردن بهترین شبکه بدین صورت تعیین می شود: برای انتخاب مجموعه والدها هر یک از N متغیرمسئله 2N حالت وجود دارد. اما بدلیل اینکه این امکان وجود دارد که والدهای هر متغیر را به صورت مستقل پیدا کنیم، کل فضای جستجو برابر با N×2N می شود. در واقع، تفکیک پذیری تابع امتیاز دهی، فضای جستجو را از فضایی شامل 2N2 حالت به فضایی شامل N×2N حالت کاهش می دهد. در این صورت، برای یافتن بهترین شبکه در مسئله ای با 10 متغیر، تعدادی حدود 104 حالت باید بررسی شود.
با وجود اینکه استفاده از توابع امتیازدهی تفکیک پذیر فضای جستجو را برای شبکه با بالاترین امتیاز به شدت کوچک می کند، این فضا هنوز بصورت نمایی با تعداد متغیرها رشد می کند. اما این امکان وجود دارد که با اعمال محدودیت های بیشتر بر روی ساختار شبکه، فضای مسئله را باز هم کوچک تر کرد. یکی از متداول ترین محدودیت هایی که بر روی ساختار شبکه اعمال می شود محدود کردن تعداد والد گره ها در شبکه است. در این حالت، اگر فرض شود تعداد والدها برای هر گره شبکه حداکثر می تواند L باشد، تعداد حالات برای انتخاب والدهای هر گره برابر می شود با i=0LNi. بنابر این، با فرض تفکیک پذیری تابع امتیازدهی، تعداد حالات فضای جستجو برابر می شود با: N×i=0LNi. با اشاره به مثال قبلی، برای شبکه ای با 10 متغیر و محدودیت سه برای تعداد والدهای هر گره، تعداد حالات فضای جستجو برابر با 1760 حالت خواهد بود. برای مقادیر L≪N، داریم: i=0LNi~ O(NL). در این حالت، بزرگی فضای جستجو برابر است با: O(NL+1).
شکل (3-2) قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک را به وسیله روش های جستجو و امتیاز دهی ارائه می دهد.

for cNode from 1 to Nfor nPrnt from 0 to LAllParents= All possible parents of cNode containing nPrnt nodesfor i from 1 to | all_Parents|prnts= the i-th parent set in All_Parentsscr = Score(CNode, prnts, Data)if(scr>bestScore[cNode])bestScorecNode=scrbestParentcNode=prntsشکل 3-2- قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک
3-4- شبکه های تصادفی و شبکه های Scale-Free
شبکه های تصادفی از معروف ترین و پر استفاده ترین شبکه ها در کاربرد های گوناگون هستند. برای به وجود آوردن شبکه های تصادفی از مکانیزم ساده ای استفاده می شود. بدین گونه که در شبکه ای متشکل از N گره، هر جفت گره با احتمال مشخص α به یکدیگر متصل می شوند. با توجه به اینکه تعداد حالات انتخاب یک جفت گره در شبکه ای با N گره برابر با N2 است، تعداد یال ها برای چنین شبکه ای به طور متوسط برابر با N2×α است. همچنین در شبکه ای که با این مکانیزم بوجود می آید، به طور متوسط، تعداد یال های هر گره برابر با α×(N-1) است. در شبکه های تصادفی، توزیع احتمالی برای تعداد یال های یک گره می تواند به این صورت تعریف شود:
Pk= N-1kαk(1-α)N-k-1(3-20)
شکل 3-3 شمای کلی چنین توزیعی را نمایش می دهد.

شکل 3-3- شمای کلی توزیع دو جمله ای
علیرغم کاربرد وسیع شبکه های تصادفی، بسیاری از شبکه های واقعی خصوصیاتی دارند که شبکه های تصادفی قادر به توجیه این خصوصیات نیستند. برای نمونه می توان از شبکه صفحات وب، شبکه های بیولوژیکی و شبکه ارجاء نویسندگان مقالات علمی نام برد. خصوصیات این گونه شبکه ها را می توان با تئوری شبکه های scale-free توضیح داد. شبکه های scale-free گونه ای از شبکه ها هستند که خصوصیات بسیار متفاوتی نسبت به شبکه های تصادفی دارند. در حالی که در شبکه های تصادفی تمامی گره ها به طور تقریبی تعداد یال یکسانی دارند، در شبکه های scale-free اکثر گره ها به تعداد کمی از گره های دیگر متصل هستند، اما تعداد محدودی از گره ها وجود دارند که ارتباطات بسیار زیادی با گره های دیگر دارند. در شبکه های scale-free احتمال اینکه یک گره به k گره دیگر متصل باشد برابر است با:
Pk ~k-α(3-21)
در شبکه های واقعی مقدار α معمولاً بین 2 و 3 قرار دارد. تصویر 3-4 شکل کلی چنین توزیعی را نمایش می دهد.

شکل 3-4- شمای کلی توزیع قانون توانی
اصلی ترین مکانیزمی که برای توضیح بوجود آمدن شبکه های scale-free پیشنهاد شده است preferential attachment نام دارد. ایده اصلی این مکانیزم این است که گرهی که به تازگی به یک شبکه اضافه شده است ترجیح می دهد تا با گره هایی ارتباط برقرار کند که خودشان ارتباطات بسیاری دارند. مثال ملموسی از این گونه رفتار در شبکه های اجتماعی دیده می شود. بر اساس preferential attachment یک عضو جدید در یک شبکه اجتماعی ترجیح می دهد تا با اعضای معروف آن شبکه، که ارتباطات زیادی دارند، ارتباط برقرار کند.
مدل ارائه شده در [36] مهم ترین مدلی است که بر اساس preferential attachment شبکه scale-free با یال های بدون جهت تولید می کند. این مدل بدین گونه عمل می کند:
فرآیند با شبکه اولیه ای که شامل تعداد کمی گره و یال است آغاز می شود. در هر مرحله از این الگوریتم، یک گره جدید با تعداد مشخصی یال به شبکه اضافه می گردد. طرف دیگر هر کدام از این یال ها بر طبق توزیع احتمالی زیر مشخص می گردد:
Pti= degt⁡(i)j=1ntdegt⁡(j)(3-22)
در فرمول بالا، nt تعداد گره های موجود در شبکه در مرحله tام را نشان می دهد و degt⁡(i) تابعی است که تعداد یال های گره iام را در مرحله tام بر می گرداند.
همان طور که به صورت ضمنی از تابع توزیع (3-22) دریافت می شود، در هر مرحله از این الگوریتم، احتمال بوجود آمدن لینک های جدید برای گره هایی که از قبل تعداد یال های زیادی دارند و به آن ها Hub گفته می شود، بیشتر از گره هایی است که درجه آن ها کم است.
الگوریتم بالا، شبکه های scale-free تولید می کند که توزیع احتمالی درجه گره ها در آن از فرمول Pk ~k-α با مقدار تقریبی α=3 پیروی می کند.
مدل ارائه شده در بالا، شبکه ای تولید می کند که یال ها در آن بدون جهت هستند. شبکه هایی با یال های جهت دار نیز می توانند scale-free باشند. در این حالت شبکه جهت دار می تواند در توزیع احتمالی مربوط به درجه ورودی گره ها، درجه خروجی گره ها و یا هر دو scale-free باشد. مدل های گوناگونی برای تولید شبکه های جهت داری با هر کدام از این ویژگی ها ارائه شده اند. در ادامه الگوریتمی معرفی می شود که مدل ارائه شده در این تحقیق الهام گرفته از این الگوریتم است.
Grendel [37] یک شبیه ساز شبکه های تنظیمات ژنی است که به تازگی ارائه گردیده است. این شبیه ساز از الگوریتم خاصی برای ایجاد شبکه های جهت داری که توزیع احتمالی درجه خروجی در آن ها از قانون توانی که مربوط به شبکه های scale-free است پیروی می کند. در شبکه های تولید شده به وسیله این الگوریتم، توزیع احتمالی درجه ورودی می تواند توزیع دلخواهی داشته باشد که معمولاً برای شبکه های تنظیمات ژنی این توزیع به گونه ای انتخاب می شود که درجه ورودی هر گره کوچک باشد. این الگوریتم بدین صورت عمل می کند:
در ابتدا فرآیند با شبکه ای کوچک متشکل از n0 گره و بدون یال آغاز می گردد. در هر مرحله از الگوریتم، یک گره جدید با تعداد محدودی یال ورودی به شبکه اضافه می گردد. طرف دیگر این یال ها با توجه به توزیع احتمالی زیر از بین گره های موجود در شبکه انتخاب می شود:
Pti= deg⁡_outti+BntB+j=1ntdeg⁡_outt⁡(j)(3-23)

پاسخ دهید

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