بیزین دینامیک، شبکه های بیزی، تنظیمات ژنی، جستجوی محلی

امتیازی که توسط این تابع برای یک شبکه بدست می آید مقداری را به عنوان جریمه کسر می کنند. این مقدار وابسته است به میزان پیچیدگی یک شبکه. هر اندازه که تعداد یال های یک شبکه بیشتر باشد، پیچیدگی آن شبکه نیز بیشتر است و امتیاز مربوط به آن شبکه جریمه بیشتری می گیرد.

3-3-2-2- امتیازدهی به روش BIC
در این روش امتیازی که یک شبکه می گیرد برابر است با:

BIC(G│D)=LL(G│D)-log⁡(M)/2|G|
(3-15)

در فرمول بالا، M تعداد نمونه های آموزشی است و |G| برابر با تعداد متغیرهای مستقل مورد نیاز برای تعریف کامل شبکه G است. تعداد این پارامترها برابر است با:

|G|=∑_(i=1)^N▒〖(r_i-1)q_i 〗
(3-16)

3-3-2-3- امتیازدهی به روش AIC
این روش امتیاز دهی شباهت بسیار زیادی به روش امتیازدهی قبلی دارد. تفاوت این دو روش در این است که در روش AIC جریمه کمتری برای پیچیدگی شبکه در نظر گرفته می شود که مستقل از تعداد نمونه های آموزشی است.

BIC(G│D)=LL(G│D)-|G|
(3-17)

3-3-2-4- امتیازدهی به روش MIT
این روش امتیازدهی بر اساس اطلاعات متقابل27 عمل می کند. در این روش، کیفیت یک شبکه بیزین به صورت زیر ارزیابی می شود:

MIT(G│D)=∑_(i=1)^N▒〖2T×I(Z^i,π(Z^i ))-∑_(j=1)^(s_i)▒χ_(α,l_(iσ_i (j)) ) 〗
(3-18)

در این فرمول، تابع I(Z^i,π(Z^i )) مقدار اطلاعات متقابل بین یک گره در یک شبکه بیزین و والدهای آن متغیر را بر می گرداند. α سطح significance را برای توزیع Chi-square مشخص می کند.

3-3-3- پیچیدگی زمانی یادگیری شبکه های بیزین دینامیک
اگر یال هایی که روابط متغیرها را در یک گام زمانی نشان می دهند در نظر نگیریم و ساختار یک شبکه بیزین دینامیک را به یال هایی که روابط متغیرها در گام های زمانی مختلف نشان می دهند محدود کنیم، برای N متغیر، تعداد 2^(N^2 ) شبکه بیزین دینامیک یکتا می توان ایجاد کرد. در واقع تعداد شبکه های بیزین دینامیکی که با N متغیر می توان ساخت، به صورت فرانمایی28 با N رشد می کند. برای مثال، برای تنها 10 متغیر بیش از 〖10〗^30 شبکه بیزین دینامیک مختلف وجود دارد. چنین فضایی باعث می شود که حتی برای مسائلی با تعداد متغیر کم، پیدا کردن بهترین شبکه امکان پذیر نباشد. به عنوان راه حلی برای این مشکل، معمولاً از روش های جستجوی محلی29 برای پیدا کردن شبکه ای با امتیاز بیشینه محلی استفاده می شود. روش های جستجوی محلی که برای این منظور استفاده می شوند عبارتند از: Greedy Search، Simulated annealing، Hill climbing و روش های جستجو بر اساس الگوریتم ژنتیک.
با وجود اینکه تعداد شبکه های بیزین دینامیک برای N متغیر برابر 2^(N^2 ) است، اگر تابعی که برای امتیازدهی شبکه ها استفاده می شود خاصیت ویژه ای را با عنوان تفکیک پذیری30 دارا باشد، این امکان فراهم می شود که بتوان بهترین شبکه را با جستجو در فضایی بسیار کوچک تر پیدا کرد. یک تابع امتیازدهی زمانی تفکیک پذیر است که شرط زیر را ارضا کند:

Score(G;D)= ∑_(i=1)^N▒〖Score(Z^i,π(Z^i);D)〗
(3-19)

با توجه به فرمول (3-19)، یک تابع امتیازدهی زمانی تفکیک پذیر است که امتیازی که به یک شبکه اختصاص می دهد را بتوان به صورت حاصل جمع مقادیری بیان کرد که هر کدام فقط به یکی از متغیرها و والدهای آن متغیر وابسته است. در چنین حالتی، بهترین مجموعه والدها برای یک متغیر از ساختار باقی شبکه مستقل است و می توان والدهای هر متغیر را به صورت مجزا پیدا کرد. در اینجا باید اشاره شود که تمامی توابع امتیازدهی که در بخش (3-3) معرفی شدند توابع امتیازدهی تفکیک پذیر هستند و می توان مقدار نهایی امتیازی را که هر یک از آن ها به یک شبکه اختصاص می دهند به صورت مجموع امتیازاتی که به گره های شبکه اختصاص می دهند در نظر گرفت.
اگر فرض شود که تابع امتیازدهی تفکیک پذیر است، فضای جستجو برای پیدا کردن بهترین شبکه بدین صورت تعیین می شود: برای انتخاب مجموعه والدها هر یک از N متغیرمسئله 2^N حالت وجود دارد. اما بدلیل اینکه این امکان وجود دارد که والدهای هر متغیر را به صورت مستقل پیدا کنیم، کل فضای جستجو برابر با N×2^N می شود. در واقع، تفکیک پذیری تابع امتیاز دهی، فضای جستجو را از فضایی شامل 2^(N^2 ) حالت به فضایی شامل N×2^N حالت کاهش می دهد. در این صورت، برای یافتن بهترین شبکه در مسئله ای با 10 متغیر، تعدادی حدود 〖10〗^4 حالت باید بررسی شود.
با وجود اینکه استفاده از توابع امتیازدهی تفکیک پذیر فضای جستجو را برای شبکه با بالاترین امتیاز به شدت کوچک می کند، این فضا هنوز بصورت نمایی با تعداد متغیرها رشد می کند. اما این امکان وجود دارد که با اعمال محدودیت های بیشتر بر روی ساختار شبکه، فضای مسئله را باز هم کوچک تر کرد. یکی از متداول ترین محدودیت هایی که بر روی ساختار شبکه اعمال می شود محدود کردن تعداد والد گره ها در شبکه است. در این حالت، اگر فرض شود تعداد والدها برای هر گره شبکه حداکثر می تواند L باشد، تعداد حالات برای انتخاب والدهای هر گره برابر می شود با ∑_(i=0)^L▒(N¦i) . بنابر این، با فرض تفکیک پذیری تابع امتیازدهی، تعداد حالات فضای جستجو برابر می شود با: N×∑_(i=0)^L▒(N¦i) . با اشاره به مثال قبلی، برای شبکه ای با 10 متغیر و محدودیت سه برای تعداد والدهای هر گره، تعداد حالات فضای جستجو برابر با 1760 حالت خواهد بود. برای مقادیر L≪N، داریم: ∑_(i=0)^L▒(N¦i) ~ O(N^L). در این حالت، بزرگی فضای جستجو برابر است با: O(N^(L+1)).
شکل (3-2) قالب اصلی الگوریتم یادگیری شبکه های بیزین دینامیک را به وسیله روش های جستجو و امتیاز دهی ارائه می دهد.

مطلب مشابه :  بیزین دینامیک، شبکه های بیزی، تنظیمات ژنی، تئوری اطلاعات

for cNode from
1 to N
for nPrnt from 0 to L
All_Parents= All possible parents of cNode
containing nPrnt nodes
for i from 1 to | all_Parents|
prnts= the i-th parent set in All_Parents
scr = Score(CNode, prnts, Data)
if(scrbestScore[cNode])
bestScore[cNode]=scr
bestParent[cNode]=prnts

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

3-4- شبکه های تصادفی و شبکه های Scale-Free

شبکه های تصادفی از معروف ترین و پر استفاده ترین شبکه ها در کاربرد های گوناگون هستند. برای به وجود آوردن شبکه های تصادفی از مکانیزم ساده ای استفاده می شود. بدین گونه که در شبکه ای متشکل از N گره، هر جفت گره با احتمال مشخص α به یکدیگر متصل می شوند. با توجه به اینکه تعداد حالات انتخاب یک جفت گره در شبکه ای با N گره برابر با (N¦2) است، تعداد یال ها برای چنین شبکه ای به طور متوسط برابر با (N¦2)×α است. همچنین در شبکه ای که با این مکانیزم بوجود می آید، به طور متوسط، تعداد یال های هر گره برابر با α×(N-1) است. در شبکه های تصادفی، توزیع احتمالی برای تعداد یال های یک گره می تواند به این صورت تعریف شود:

P(k)= ((N-1)¦k) α^k 〖(1-α)〗^(N-k-1)
(3-20)

شکل 3-3 شمای کلی چنین توزیعی را نمایش می دهد.

شکل 3-3- شمای کلی توزیع دو جمله ای

علیرغم کاربرد وسیع شبکه های تصادفی، بسیاری از شبکه های واقعی خصوصیاتی دارند که شبکه های تصادفی قادر به توجیه این خصوصیات نیستند. برای نمونه می توان از شبکه صفحات وب، شبکه های بیولوژیکی و شبکه ارجاء نویسندگان مقالات علمی نام برد. خصوصیات این گونه شبکه ها را می توان با تئوری شبکه های scale-free توضیح داد. شبکه های scale-free گونه ای از شبکه ها هستند که خصوصیات بسیار متفاوتی نسبت به شبکه های تصادفی دارند. در حالی که در شبکه های تصادفی تمامی گره ها به طور تقریبی تعداد یال یکسانی دارند، در شبکه های scale-free اکثر گره ها به تعداد کمی از گره های دیگر متصل هستند، اما تعداد محدودی از گره ها وجود دارند که ارتباطات بسیار زیادی با گره های دیگر دارند. در شبکه های scale-free احتمال اینکه یک گره به k گره دیگر متصل باشد برابر است با:

P(k) ~k^(-α)
(3-21)

در شبکه های واقعی مقدار α معمولاً بین 2 و 3 قرار دارد. تصویر 3-4 شکل کلی چنین توزیعی را نمایش می دهد.

شکل 3-4- شمای کلی توزیع قانون توانی

اصلی ترین مکانیزمی که برای توضیح بوجود آمدن شبکه های scale-free پیشنهاد شده است preferential attachment نام دارد. ایده اصلی این مکانیزم این است که گرهی که به تازگی به یک شبکه اضافه شده است ترجیح می دهد تا با گره هایی ارتباط برقرار کند که خودشان ارتباطات بسیاری دارند. مثال ملموسی از این گونه رفتار در شبکه های اجتماعی دیده می شود. بر اساس preferential attachment یک عضو جدید در یک شبکه اجتماعی ترجیح می دهد تا با اعضای معروف آن شبکه، که ارتباطات زیادی دارند، ارتباط برقرار کند.
مدل ارائه شده در [36] مهم ترین مدلی است که بر اساس preferential attachment شبکه scale-free با یال های بدون جهت تولید می کند. این مدل بدین گونه عمل می کند:
فرآیند با شبکه اولیه ای که شامل تعداد کمی گره و یال است آغاز می شود. در هر مرحله از این الگوریتم، یک گره جدید با تعداد مشخصی یال به شبکه اضافه می گردد. طرف دیگر هر کدام از این یال ها بر طبق توزیع احتمالی زیر مشخص می گردد:

P_t (i)= (〖deg〗_t⁡(i))/(∑_(j=1)^(n_t)▒〖〖deg〗_t⁡(j)〗)
(3-22)

در فرمول بالا، n_t تعداد گره های موجود در شبکه در مرحله tام را نشان می دهد و 〖deg〗_t⁡(i) تابعی است که تعداد یال های گره iام را در مرحله tام بر می گرداند.
همان طور که به صورت ضمنی از تابع توزیع (3-22) دریافت می شود، در هر مرحله از این الگوریتم، احتمال بوجود آمدن لینک های جدید برای گره هایی که از قبل تعداد یال های زیادی دارند و به آن ها Hub گفته می شود، بیشتر از گره هایی است که درجه آن ها کم است.
الگوریتم بالا، شبکه های scale-free تولید می کند که توزیع احتمالی درجه گره ها در آن از فرمول P(k) ~k^(-α) با مقدار تقریبی α=3 پیروی می کند.
مدل ارائه شده در بالا، شبکه ای تولید می کند که یال ها در آن بدون جهت هستند. شبکه هایی با یال های جهت دار نیز می توانند scale-free باشند. در این حالت شبکه جهت دار می تواند در توزیع احتمالی مربوط به درجه ورودی گره ها، درجه خروجی گره ها و یا هر دو scale-free باشد. مدل های گوناگونی برای تولید شبکه های جهت داری با هر کدام از این ویژگی ها ارائه شده اند. در ادامه الگوریتمی معرفی می شود که مدل ارائه شده در این تحقیق الهام گرفته از این الگوریتم است.
Grendel [37] یک شبیه ساز شبکه های تنظیمات ژنی است که به تازگی ارائه گردیده است. این شبیه ساز از الگوریتم خاصی برای ایجاد شبکه های جهت داری که توزیع احتمالی درجه خروجی در آن ها از قانون توانی که مربوط به شبکه های scale-free است پیروی می کند. در شبکه های تولید شده به وسیله این الگوریتم، توزیع احتمالی درجه ورودی می تواند توزیع دلخواهی داشته باشد که معمولاً برای شبکه های تنظیمات ژنی این توزیع به گونه ای انتخاب می شود که درجه ورودی هر گره کوچک باشد. این الگوریتم بدین صورت عمل می کند:
در ابتدا فرآیند با شبکه ای کوچک متشکل از n_0 گره و بدون یال آغاز می گردد. در هر مرحله از الگوریتم، یک گره جدید با تعداد محدودی یال ورودی به شبکه اضافه می گردد. طرف دیگر این یال ها با توجه به توزیع احتمالی زیر از بین گره های موجود در شبکه انتخاب می شود:

مطلب مشابه :  تحقیق درمورداشخاص ثالث، حقوق بشر

P_t (i)= ( 〖deg⁡_out〗_t⁡(i)+B)/(n_t B+∑_(j=1)^(n_t)▒〖〖deg⁡_out〗_t⁡(j)〗)
(3-23)

در این فرمول، 〖deg⁡_out〗_t⁡(i) تابعی است که
درجه خروجی گره iام را در مرحله tام بر می گرداند. B پارامتری است که توان مربوط به توزیع احتمالی درجه خروجی شبکه را مشخص می کند.

3-5- روش پیشنهادی

در این بخش، روش پیشنهادی برای استنتاج شبکه های تنظیمات ژنی به وسیله شبکه های بیزین دینامیک ارائه می گردد.
روش ارائه شده بر اساس سه فرض اصلی شکل گرفته است. این سه فرض عبارتند از:
فرض اول: داده های آموزشی به طور کامل قابل مشاهده هستند و مقدار هیچ متغیری در آن ها نا معلوم نیست.
فرض دوم: تعداد یال های ورودی به هر یک از گره های شبکه واقعی محدود است
فرض سوم: توزیع احتمالی درجه خروجی گره های شبکه ای که داده های آموزشی را تولید کرده است، از قانون توانی پیروی می کند. به بیان دیگر این شبکه در توزیع احتمالی درجه خروجی گره ها scale-free است.
فرض اول عنوان می کند که داده های آموزشی نباید حاوی مقادیر نا معلوم31 باشند. داده های آموزشی برای استنتاج شبکه های تنظیمات ژنی عموماً داده های بدست آمده به وسیله microarray هستند. اغلب، این نوع داده ها حاوی مقادیری نامعلوم هستند. برای سازگار کردن این نوع داده ها با فرض اول روش ارائه شده باید از یکی از روش های پیشنهاد شده برای تخمین مقادیر نامعلوم در بیان ژن استفاده نمود.
فرض دوم مربوط به پیچیدگی زمانی روش ارائه شده است. همان گونه که پیش از این عنوان گردید، اگر روش امتیاز دهی که برای یادگیری شبکه بیزین دینامیک استفاده می شود دارای خاصیت تفکیک پذیری باشد، با محدود کردن تعداد والدها برای هر کدام از متغیرها، این امکان فراهم می شود تا یادگیری شبکه در زمانی با پیچیدگی چند جمله ای صورت پذیرد. لازم به یاد آوری است که در حالت کلی پیچیدگی زمانی برای یاد گیری شبکه های بیزین دینامیک فرانمایی و در صورتی که روش امتیاز دهی تفکیک پذیر باشد، بدون محدود کردن تعداد والدها، نمایی است.
فرض سوم که مربوط به scale-free بودن توزیع احتمالی درجه خروجی گره های شبکه واقعی است، مهم ترین زیربنای روش ارائه شده است و هسته اصلی این الگوریتم را تشکیل می دهد. همان گونه که توضیح داده شد، در شبکه ای که در آن توزیع احتمالی درجه خروجی گره ها scale-free است، احتمال این که یکی از گره ها k یال خروجی داشته باشد برابر با P(k)~k^(-α) است.
فرض کنید که ما شبکه ای متشکل از N گره را در اختیار داریم که ساختار آن با فرض دوم و سوم که در بالا به آن ها اشاره شد سازگار است. این شبکه را با حرف G نشان می دهیم. ما تعدادی از یال های این شبکه را بصورت تصادفی انتخاب می کنیم و آن ها را از شبکه اصلی حذف می کنیم تا شبکه جدیدی بدست آید که آن را با G^’ نشان می دهیم. باید توجه داشت که شبکه جدید نیز با فرض دوم و سوم سازگار است. حال فرض کنید که ما می دانیم که یال های متصل به گره iام از شبکه اصلی حذف شده ان

Leave a Comment