مجله علمی زاراسنگ - مجله علمی و آموزشی

سایت مقالات فارسی – استنتاج شبکه های تنظیمات ژنی از روی داده های سری زمانی Microarray به …

(3-11)

در فرمول بالا، برابر با تعداد حالات مختلف برای مقداردهی به والدهای متغیر ام است و تعداد مقادیری که خود این متغیر می تواند داشته باشد. برابر است با تعداد دفعاتی که متغیر ام مقدار ام را در دامنه خود داشته است به شرطی که مقادیر والدهای این متغیر در حالت ام باشند. پارامتر توزیع Dirichlet مربوط به متغیر ام، در حالتی که والدهای این متغیر در حالت ام باشند، است. همچنین داریم: و .
3-3-1-1- امتیازدهی به روش K2
در صورتی که در فرمول (3-11) تمامی پارامترهای توزیع برابر یک قرار داده شوند، معادل تابع امتیازدهی K2 می شود. در این حالت داریم:

دانلود کامل پایان نامه در سایت pifo.ir موجود است.

(3-12)

3-3-1-2- امتیازدهی به روش BDe
اگر در فرمول (3-11) مطابق فرمول زیر تعریف شود، معادل تابع امتیازدهی BDe می شود.

(3-13)

در فرمول بالا، شرط یعنی متغیر ام مقدار ام خود را داشته باشد و یعنی مجموعه مقادیر والدهای متغیر ام در حالت ام خود باشد. میزان باور ما را به توزیع اولیه نشان می دهد.
3-3-2- روش های امتیازدهی بر اساس تئوری اطلاعات
روش های بر گرفته شده از تئوری اطلاعات که برای امتیازدهی شبکه های بیزین استفاده می شوند، بر اساس فشرده سازی اطلاعات عمل می کنند.در این گونه روش ها، کیفیت یک شبکه بیزین متناسب است با میزانی که شبکه قادر است با توجه به کدی که تولید می کند داده های آموزشی را فشرده سازی کند. کدی که یک شبکه بیزین تولید می کند بر اساس ساختار گراف شبکه و گزاره های استقلال یا عدم استقلال بین متغیرها که توسط یال های گراف مشخص می شود، تعیین می گردد. حد نهایی فشرده سازی اطلاعات طبق تئوری شانون مشخص می شود. طبق این تئوری، وقتی تعداد نمونه های مستقل با توزیع یکنواخت یک مجموعه به بینهایت میل می کند، هیچ روش فشرده سازی قادر نیست، بدون از دست دادن اطلاعات، پیغامی را با طولی کوتاه تر از اندازه ای که با آنتروپی شانون مشخص می شود ایجاد کند.
کدهای متعددی هستند که به صورت حدی می توانند پیغامی را تولید کنند که اندازه آن به اندازه ای که با آنتروپی شانون مشخص می شود میل کند. برای ساختن چنین کدی باید یک توزیع احتمالی بر روی داده ها تعریف شود. این توزیع احتمالی به صورت قطعی می تواند توسط یک شبکه بیزین مشخص گردد. بر همین اساس، روش های امتیاز دهی زیر تعریف می شوند.
3-3-2-1- امتیازدهی به روش log-likelihood (LL)
تابعی که در این روش امتیازدهی استفاده می شود چنین تعریف می شود:

yle="box-sizing: inherit; width: 1104px;">

[ 05:30:00 ق.ظ ]

استنتاج شبکه های تنظیمات ژنی از روی داده های سری زمانی Microarray …

(3-18)

در این فرمول، تابع مقدار اطلاعات متقابل بین یک گره در یک شبکه بیزین و والدهای آن متغیر را بر می گرداند. سطح significance را برای توزیع Chi-square مشخص می کند.
3-3-3- پیچیدگی زمانی یادگیری شبکه های بیزین دینامیک
اگر یال هایی که روابط متغیرها را در یک گام زمانی نشان می دهند در نظر نگیریم و ساختار یک شبکه بیزین دینامیک را به یال هایی که روابط متغیرها در گام های زمانی مختلف نشان می دهند محدود کنیم، برای متغیر، تعداد شبکه بیزین دینامیک یکتا می توان ایجاد کرد. در واقع تعداد شبکه های بیزین دینامیکی که با متغیر می توان ساخت، به صورت فرانمایی[28] با رشد می کند. برای مثال، برای تنها 10 متغیر بیش از شبکه بیزین دینامیک مختلف وجود دارد. چنین فضایی باعث می شود که حتی برای مسائلی با تعداد متغیر کم، پیدا کردن بهترین شبکه امکان پذیر نباشد. به عنوان راه حلی برای این مشکل، معمولاً از روش های جستجوی محلی[29] برای پیدا کردن شبکه ای با امتیاز بیشینه محلی استفاده می شود. روش های جستجوی محلی که برای این منظور استفاده می شوند عبارتند از: Greedy Search، Simulated annealing، Hill climbing و روش های جستجو بر اساس الگوریتم ژنتیک.
با وجود اینکه تعداد شبکه های بیزین دینامیک برای متغیر برابر است، اگر تابعی که برای امتیازدهی شبکه ها استفاده می شود خاصیت ویژه ای را با عنوان تفکیک پذیری[30] دارا باشد، این امکان فراهم می شود که بتوان بهترین شبکه را با جستجو در فضایی بسیار کوچک تر پیدا کرد. یک تابع امتیازدهی زمانی تفکیک پذیر است که شرط زیر را ارضا کند:

منبع فایل کامل این پایان نامه این سایت pipaf.ir است

(3-19)

با توجه به فرمول (3-19)، یک تابع امتیازدهی زمانی تفکیک پذیر است که امتیازی که به یک شبکه اختصاص می دهد را بتوان به صورت حاصل جمع مقادیری بیان کرد که هر کدام فقط به یکی از متغیرها و والدهای آن متغیر وابسته است. در چنین حالتی، بهترین مجموعه والدها برای یک متغیر از ساختار باقی شبکه مستقل است و می توان والدهای هر متغیر را به صورت مجزا پیدا کرد. در اینجا باید اشاره شود که تمامی توابع امتیازدهی که در بخش (3-3) معرفی شدند توابع امتیازدهی تفکیک پذیر هستند و می توان مقدار نهایی امتیازی را که هر یک از آن ها به یک شبکه اختصاص می دهند به صورت مجموع امتیازاتی که به گره های شبکه اختصاص می دهند در نظر گرفت.
اگر فرض شود که تابع امتیازدهی تفکیک پذیر است، فضای جستجو برای پیدا کردن بهترین شبکه بدین صورت تعیین می شود: برای انتخاب مجموعه والدها هر یک از متغیرمسئله حالت وجود دارد. اما بدلیل اینکه این امکان وجود دارد که والدهای هر متغیر را به صورت مستقل پیدا کنیم، کل فضای جستجو برابر با می شود. در واقع، تفکیک پذیری تابع امتیاز دهی، فضای جستجو را از فضایی شامل حالت به فضایی شامل حالت کاهش می دهد. در این صورت، برای یافتن بهترین شبکه در مسئله ای با 10 متغیر، تعدادی حدود حالت باید بررسی شود.
با وجود اینکه استفاده از توابع امتیازدهی تفکیک پذیر فضای جستجو را برای شبکه با بالاترین امتیاز به شدت کوچک می کند، این فضا هنوز بصورت نمایی با تعداد متغیرها رشد می کند. اما این امکان وجود دارد که با اعمال محدودیت های بیشتر بر روی ساختار شبکه، فضای مسئله را باز هم کوچک تر کرد. یکی از متداول ترین محدودیت هایی که بر روی ساختار شبکه اعمال می شود محدود کردن تعداد والد گره ها در شبکه است. در این حالت، اگر فرض شود تعداد والدها برای هر گره شبکه حداکثر می تواند باشد، تعداد حالات برای انتخاب والدهای هر گره برابر می شود با . بنابر این، با فرض تفکیک پذیری تابع امتیازدهی، تعداد حالات فضای جستجو برابر می شود با: . با اشاره به مثال قبلی، برای شبکه ای با 10 متغیر و محدودیت سه برای تعداد والدهای هر گره، تعداد حالات فضای جستجو برابر با 1760 حالت خواهد بود. برای مقادیر ، داریم: . در این حالت، بزرگی فضای جستجو برابر است با: .
شکل (3-2) قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک را به وسیله روش های جستجو و امتیاز دهی ارائه می دهد.

–

شکل 3-2- قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک

3-4- شبکه های تصادفی و شبکه های Scale-Free
شبکه های تصادفی از معروف ترین و پر استفاده ترین شبکه ها در کاربرد های گوناگون هستند. برای به وجود آوردن شبکه های تصادفی از مکانیزم ساده ای استفاده می شود. بدین گونه که در شبکه ای متشکل از گره، هر جفت گره با احتمال مشخص به یکدیگر متصل می شوند. با توجه به اینکه تعداد حالات انتخاب یک جفت گره در شبکه ای با گره برابر با است، تعداد یال ها برای چنین شبکه ای به طور متوسط برابر با است. همچنین در شبکه ای که با این مکانیزم بوجود می آید، به طور متوسط، تعداد یال های هر گره برابر با است. در شبکه های تصادفی، توزیع احتمالی برای تعداد یال های یک گره می تواند به این صورت تعریف شود:

yle="box-sizing: inherit; width: 1104px;">

(3-20)

[ 05:30:00 ق.ظ ]

علمی : استنتاج شبکه های تنظیمات ژنی از روی داده های سری زمانی Microarray به …

(3-25)

نشان دهنده کل شبکه بدون در نظر گرفتن یال های ورودی به گره ام است. ترم دوم در سمت راست معادله (3-25) باعث می شود که امتیاز والدها با تعداد گره بیشتر مقداری افزایش یابد. به بیان دیگر، این ترم میزان جریمه را برای مجموعه هایی با تعداد گره های بیشتر کاهش می دهد.
تا اینجا فرض شده بود که تنها منبع برای بازسازی شبکه از روی شبکه ساختار فعلی شبکه است. حال اگر فرض شود که یک سری زمانی تولید شده به وسیله شبکه در اختیار است، می توان برای بازیابی شبکه از ترکیب این منبع اطلاعاتی به همراه ساختار شبکه و احتمالاً دانش قبلی در مورد ساختار شبکه استفاده کرد. برای این منظور می توان از ترکیب توابع امتیازدهی (3-25) و (3-6) استفاده کرد. تابع جدید برابر است با:

دانلود کامل پایان نامه در سایت pifo.ir موجود است.

(3-26)

نکته قابل توجه دیگر این است که در موقعیتی که در بالا توصیف شده است، می دانیم که یال های شبکه مطمئناً در شبکه اصلی هم وجود دارند. این فرض باعث می شود که ساختار شبکه منبع قابل اعتمادی برای بازیابی شبکه اصلی باشد. اما در عمل، ما چنین اطلاعاتی نداریم و مسئله ساختن شبکه از ابتدا است. در چنین حالتی اضافه کردن یال هایی که اشتباه هستند بسیار محتمل است. زمانی که پیدا کردن بهترین مجموعه والدها برای هر گره از ساختار شبکه مستقل است، اضافه کردن یال های اشتباه تاثیری در بازیابی باقی شبکه ندارند. اما، در روش ارائه شده، اضافه کردن یال های اشتباه بر روی درجه خروجی گره ها تاثیر می گذارند. این تاثیر به نوبه خود باعث تغییر در توزیع (3-24) می شود که این می تواند کل فرآیند بازیابی شبکه را تحت تاثیر قرار دهد.
برای حل این مشکل و کاهش احتمال اضافه کردن یال های اشتباه، حداقل در مراحل ابتدایی فرآیند یادگیری شبکه، الگوریتم ارائه شده یال ها را به صورت افزایشی و طی مراحل مختلف به شبکه اضافه می کند. فرآیند با افزودن یال هایی که باعث ایجاد بیشترین افزایش در امتیاز شبکه می شوند آغاز می شود. بر اساس اطلاعاتی که ما از داده های آموزشی و دانش اولیه داریم، این ها یال هایی هستند که بیشترین اطمینان از وجود آن ها در شبکه اصلی داریم. بعد از افزودن این یال ها، فرض می کنیم که ساختار شبکه ساخته شده در این مرحله حقیقی است و بر اساس این ساختار، احتمال اختصاص یافته به هر گره را در توزیع احتمالی (3-24) دوباره محاسبه می کنیم. در این مرحله دوباره یال هایی که باعث بیشترین افزایش می شوند را به شبکه اضافه کرده، مراحل قبل را تکرار می کنیم.
به صورت دقیق تر فرآیند یاد گیری در الگوریتم ارائه شده بدین صورت است: ابتدا امتیاز مربوط به هر گره، با فرض این که گره ها هیچ والدی ندارند، محاسبه می شود. در گام بعدی بهترین مجموعه والدها برای هر گره بر اساس تابع امتیازدهی (3-26) انتخاب می شود و میزان افزایشی که توسط اضافه کردن یال های مربوطه در امتیاز آن گره ایجاد می شود محاسبه می گردد. بعد از محاسبه میزان تغییر امتیاز برای تمامی گره ها، گره ها بر اساس این میزان افزایش به صورت نزولی مرتب می شوند و 10% گره ها که بیشترین تغییر در امتیاز را دارند انتخاب می شوند.در پایان، یال های مربوط به بهترین والدها برای گره های انتخاب شده به شبکه اضافه می شوند. بعد از افزوده شدن این یال ها احتمال منسوب به هر گره بر اساس (3-24) دوباره محاسبه می شود. در حلقه بعدی الگوریتم، دوباره بهترین مجموعه والدها برای هر گره بر اساس (3-26) محاسبه می شود و مراحل قبل تکرار می گردند. این فرآیند تا جایی تکرار می شود که میزان افزایش امتیاز در آن مرحله از کسر مشخصی از کل افزایش بدست آمده از ابتدای فرآیند کمتر شود. این فرآیند به طور دقیق در تصویر (3-5) ارائه شده است.

br />

01
02
03
04
05
06
07
08
09
10
11
12
13
14

موضوعات: بدون موضوع لینک ثابت

[ 05:29:00 ق.ظ ]

در آزمایش های این قسمت از مجموعه ای از 50 شبکه بیزین دینامیک شامل 100 گره که درجه خروجی در آن ها از قانون توانی پیروی کرده استفاده شده است. برای تولید این 50 شبکه فرآیندی که در بخش (4-2) توضیح داده شد به کار گرفته شده است. بیشینه تعداد یال های ورودی به هر گره در فرآیند تولید شبکه ها 2 در نظر گرفته شده است. از هر کدام از شبکه های تولید شده 5 سری زمانی به طول 50 و 5 سری زمانی به طول 100 نمونه گیری شده است. سری های زمانی که طول یکسانی داشتند با هم ترکیب شده اند تا دو مجموعه داده های آموزشی، یکی شامل 250 سری زمانی با طول 50 و دیگری شامل 250 سری زمانی با طول 100، بدست آیند. باید توجه شود که طول سری های زمانی بیان ژن در عمل اغلب کمتر از 100 است. بنابر این سری های زمانی در داده های آموزشی این آزمایش از لحاظ طول نماینده خوبی برای سری های بیان ژن واقعی هستند.
برای یادگیری شبکه های بیزین دینامیک از داده های آموزشی از متدها و توابع امتیاز دهی مختلفی استفاده گردیده است که در جداول 1 و2 مشخص شده اند.
پارامتر ها برای روش هایی که در این آزمایش استفاده شدند بدین گونه تنظیم شده اند: در روش ارائه شده، برابر با 05/0 و برابر با 5/0 در نظر گرفته شده است. در روش GlobalMIT پارامتر برابر 999/0 قرار داده شده است. برای روش BDe+P از ترکیب تابع امتیاز دهی BDe و توزیع احتمالی بر روی ساختار شبکه ها استفاده شده است. در این فرمول تعداد کل یال های شبکه است و پارامتر برابر با 05/0 در نظر گرفته شده است.
بعد از فرآیند یادگیری، شبکه استنتاج شده به وسیله هر متد با شبکه اصلی مقایسه شده است و مقادیر Recall، Precision و F-Measure برای شبکه استنتاج شده محاسبه شده اند. از نتایج بدست آمده هر روش بر روی 250 سری زمانی در هر یک از مجموعه داده های آموزشی میانگین گیری شده است. این میانگین به همراه انحراف از معیار مربوطه برای هر روش در جدول (4-1) برای داده های آموزشی با طول 50، و در جدول (4-2) برای داده های آموزشی با طول 100 نمایش داده شده اند.
همان گونه که در جدول ها مشخص است الگوریتم ارائه شده بر روی هر دو مجموعه داده آموزشی بالاترین مقدار Recall و F-Measure را بدست آورده است. آنالیز مقادیر بدست آورده شده نشان می دهد که اختلاف بین F-Measure الگوریتم ارائه شده و بقیه روش ها از لحاظ آماری significant است.
نکته قابل توجه دیگر این است که میزان اختلاف F-Measure الگوریتم ارائه شده با بقیه روش ها در نتایجی که بر روی داده های آموزشی با طول 50 بدست آمده اند در مقایسه با میزان اختلاف نتایج بدست آمده بر روی داده های آموزشی با طول 100 بیشتر است. این رفتار قابل انتظار است چون هر اندازه که داده های آموزشی اطلاعات کمتری را برای استنتاج شبکه در اختیار ما قرار دهند، اثر دیگر منابع اطلاعاتی مثل دانش اولیه در مورد شبکه و یا اطلاعات مربوط به ساختار شبکه در فرآیند یادگیری نقش بیشتری ایفا می کنند. در واقع اگر طول سری زمانی که به عنوان داده آموزشی استفاده می شود به اندازه کافی بزرگ باشد، نقش سایر منابع اطلاعاتی به صفر میل می کند.
این واقعیت که الگوریتم ارائه شده می تواند در مواردی که داده های آموزشی ناکافی هستند باعث افزایش قابل توجه شبکه استنتاج شده شود بسیار مطلوب است چون همان گونه که قبلاً توضیح داده شد، کوتاه بودن طول سری های زمانی بیان ژن که برای استنتاج شبکه های تنظیمات ژنی استفاده می شوند از عمده ترین مشکلات در بازسازی این گونه شبکه ها می باشد و باعث کاهش شدید کیفیت شبکه های استنتاج شده می شود.

موضوعات: بدون موضوع لینک ثابت

[ 05:29:00 ق.ظ ]