|
روش‌های '''پیش‌بینی عملکرد پروتئین''' روش‌هایی است که محققان بیوانفورماتیک برای تعیین نقش‌های بیولوژیکی یا بیوشیمیایی پروتئین‌ها از آنها استفاده می‌کنند. این پروتئین‌ها معمولاً از آن دسته پروتئین‌هایی هستند که کمتر مورد مطالعه و پیش‌بینی براساس توالی یابی ژنوم قرار گرفته‌اند. این پیش‌بینی‌ها غالباً توسط روش‌های محاسباتی مبتنی بر داده‌ها به دست می‌آیند. این داده‌ها از طرق گوناگونی مانند [[هم‌ساخت‌شناسی|هومولوژی]] توالی [[اسید نوکلئیک|نوکلئیک اسیدها]]، ساختار [[دومین پروتئین]]، [[متن‌کاوی]] داده‌های منتشر شده، نمایش [[تبارزایش|فیلوژنتیک]]، نمایش [[بیان ژن]] و بررسی عملکرد پروتئین‌ها با یکدیگر حاصل می‌شوند.
'''تجزیه و تحلیل جریان داده''' یکی از روش‌هایی است که با استفاده از آن می‌توان اطلاعات مربوط به داده‌هایی که در نقاط مختلف یک [[برنامهٔ رایانه‌ای]] محاسبه می‌شوند را فراهم کرد. [[گراف روند کنترلی]] برای تعیین قسمت‌های برنامه که به تعریف یک متغیر یا مقداردهی یک متغیر منجر شده‌است، استفاده می‌شود. تحلیل جریان داده اطلاعاتی را تولید می‌کند که معمولاً [[کامپایلر]]ها از آن برای [[بهینه‌سازی برنامه]] استفاده می‌کنند.<ref>[https://www.geeksforgeeks.org/data-flow-analysis-compiler/ "Data flow analysis in Compiler"]</ref><ref>[http://portal.acm.org/citation.cfm?id=808479 "Control Flow Analysis" by Frances E. Allen]</ref> ▼
▲'''تجزیه و تحلیل جریان داده''' یکی از روش‌هایی است که با استفاده از آن می‌توان اطلاعات مربوط به داده‌هایی که در نقاط مختلف یک [[برنامهٔ رایانه‌ای]] محاسبه می‌شوند را فراهم کرد. [[گراف روند کنترلی]] برای تعیین قسمت‌های برنامه که به تعریف یک متغیر یا مقداردهی یک متغیر منجر شده‌است، استفاده می‌شود. تحلیل جریان داده اطلاعاتی را تولید می‌کند که معمولاً [[کامپایلر]]ها از آن برای [[بهینه‌سازی برنامه]] استفاده می‌کنند.<ref>[https://www.geeksforgeeks.org/data-flow-analysis-compiler/ "Data flow analysis in Compiler"]</ref><ref>[http://portal.acm.org/citation.cfm?id=808479 "Control Flow Analysis" by Frances E. Allen]</ref>
در یک گراف کنترل جریان هر [[گره (علوم رایانه)| گره]] در گراف یک بلوک پایه را نشان می‌دهد. بلوک پایه مجموعه ای از دستوالعمل‌های متوالی است به طوری که هیچ دستور پرشی به این خطوط به جز خط اول وجود نداشته باشد و به جز خط آخر هیچ‌کدام ازین دستورات پرشی نباشند؛ در واقع این مجموعه دستورالعمل پشت سر هم و به ترتیب اجرا می‌شوند.<ref>[https://www.geeksforgeeks.org/basic-blocks-in-compiler-design/ "Basic Blocks in Compiler Design"]</ref>
یک راه ساده برای پیاده‌سازی تجزیه و تحلیل جریان داده این است که معادله جریان داده را برای هر گره از گراف روند کنترلی تنظیم کنیم و سپس به صورت محلی خروجی هر گره را از ورودی‌های آن محاسبه کنیم و این کار را تا زمانی که سیستم به [[نقطه ثابت]]ی برسد تکرار کنیم.
== اصول اساسی ==
= جستار هایجستارهای وابسته= ▼تجزیه و تحلیل جریان داده فرایند تولید اطلاعات دربارهٔ شیوه به کار رفتن متغیرهای تعریف شده در برنامه است و تلاش می‌کند اطلاعات خاصی را در هر نقطه از اجرا به دست بیاورد. معمولاً به دست آوردن این اطلاعات در محدودهٔ بلوک‌های پایه کفایت می‌کند؛ زیرا با استفاده از آن به راحتی می‌توان اطلاعات نقاط مختلف بلوک پایه را به دست آورد. در تحلیل جریان رو به جلو، حالت خروجی یک بلوک تابعی از حالت ورودی آن بلوک است. این تابع ترکیب اثرات عبارات موجود در بلوک می‌باشد. حالت ورودی یک بلوک تابعی از حالت‌های خروجی اجداد آن بلوک می‌باشد. در نتیجه مجموعه ای از معادلات جریان داده به دست می‌آید:
برای هر بلاک b:
<math>
out_b = trans_b (in_b)
</math>
<math >
in_b = join_{p \in pred_b}(out_p)
</math>
در این‌جا <math> trans_b </math> تابع انتقال بلوک <math>b</math> می‌باشد. این تابع روی حالت ورودی <math>in_b</math> کار می‌کند و حالت خروجی <math>out_b</math> را نتیجه می‌دهد و <math>join</math> عملگر پیوند است که حالت‌های خروجی اجداد بلوک <math>b</math> را ترکیب کرده و حالت ورودی <math>b</math> را نتیجه می‌دهد.
بعد از حل این مجموعه از معادلات، می‌توان از حالت‌های ورودی و خروجی بلوک‌ها برای استخراج ویژگی‌های برنامه در محدوده بلوک‌های پایه استفاده کرد. با اعمال کردن تابع انتقال هر عبارت به صورت جداگانه، می‌توان اطلاعات مطلوب را در هر نقطه از بلوک پایه به دست آورد.
هر نوع خاصی از تحلیل جریان داده، تابع انتقال و عملگر پیوند خاص خود را دارد. برخی از مسئله‌های جریان داده، به تحلیل جریان رو به عقب نیاز دارند. این تحلیل به جز تابع انتقال و عملگر پیوند تقریباً مشابه تحلیل رو به جلو می‌باشد؛ تابه انتقال در این تحلیل روی حالت خروجی بلوک اعمال می‌شود و حالت ورودی آن را نتیجه می‌دهد و عملگر پیوند روی حالت‌های ورودی بلوک‌های فرزند اعمال شده و حالت خروجی یک بلاک را نتیجه می‌دهد.
می توانید شمایی ساده از گراف کنترل جربان داده را در تصویر زیر مشاهده کنید <ref>https://suif.stanford.edu/~courses/cs243/lectures/l2.pdf</ref>:
<gallery heights= 300 widths=300 style="text-align:center">
Data_flow.jpg|شمایی از یک گراف کنترل جریان داده
</gallery>
=حل مسائل تجزیه و تحلیل جریان داده=
رایج‌ترین روش برای حل مسائل تجزیه و تحلیل جریان داده، استفاده از الگوریتم‌های تکراری{{انگلیسی|iterative algorithm}} است. محبوبیت این الگوریتم ها به خاطر سرعت ٬ قدرت و سادگی پیاده سازی آن هاست . این الگوریتم، با یک تقریب از حالت ورودی هر بلوک شروع می‌کند و حالت خروجی را با اعمال کردن تابع انتقال هر بلوک بر روی حالت ورودی آن، به دست می‌آورد. حالت ورودی جدید برای هر بلوک با اعمال عملگر پیوند روی اجداد آن بلوک در [[گراف روند کنترلی]] به دست می آید. حال الگوریتم روی حالت های اولیه جدید تکرار خواهد شد و این تکرار تا زمانی ادامه پیدا می کند که سیستم به [[نقطه ثابت]]ی برسد به این معنا که با تکرار فرآیند الگوریتم ٬حالت ورودی و خروجی جدید برای هر بلوک با حالت ورودی و خروجی قبلی آن تفاوتی نکند.<ref name = a>https://pdfs.semanticscholar.org/db53/41a4bc653b84a12780139d795a910c1c8b60.pdf</ref>
===همگرایی===
همانطور که پیش تر گفته شد٬در روش استفاده از الگوریتم‌های تکراری ٬ تکرار الگوریتم تا زمانی ادامه پیدا می کند که به نقطه ثابتی برسد؛ پس برای اینکه در عمل بتوانیم از این روش استفاده کنیم٬ سیستم باید همگرا باشد. همگرایی سیستم با اعمال یک سری شرط روی [[دامنه (آمار)|دامنه ]] مقادیر حالت ها٬تابع انتقال و عملگر پیوند تضمین خواهد شد.این شروط عبارتند از :
*دامنه مقادیر باید [[مجموعه جزئاً مرتب]] و کراندار باشد.
*ترکیب تابع انتقال و پیوند باید یک [[تابع یکنوا]] نسبت به ترتیب مقادیر در دامته باشد.
با وجود این دو شرط نتیجه یک تابع یکنوای کراندار است و یک تابع یکنوای کراندار حتماً همگرا است .
===مقداردهی اولیه===
همانطور که پیش تر گفته شد،الگوریتم با یک تقریب از حالت ورودی هر بلوک شروع می‌شود . این مقدار دهی اولیه باید به گونه ای باشد که نتیجه نهایی صحیح و دقیق باشد برای مثال چنانچه قرار است نتایج برای بهینه سازی کد در کامپایلرها مورد استفاده قرار بگیرد٬نتیجه حاصل باید منطق برنامه را حفظ کند .
===اهمیت ترتیب پیمایش بلوک ها===
ترتیب پیمایش بلوک ها در فرآیند اجرای الگوریتم روی کارآیی الگوریتم و زمان اجرای آن ،تأثیر مستقیم دارد. عامل مهم دیگری که در این بحث اهمیت دارد ،رو به جلو {{انگلیسی|forward}} یا رو به عقب {{انگلیسی|backward}} بودن تحلیل در گراف روند کنترل می باشد . اگر تحلیل ما رو به جلو باشد، بهتر است اجداد هر گره در گراف ، قبل از آن شده باشند؛چرا که حالت هر بلوک وابسته به حالات اجداد آن در گراف خواهد بود و اگر قبل از دیدن هر گره اجداد آن دیده شده باشند ،سرٍعت همگرایی الگوریتم بیشتر خواهد بود.اگر در گراف حلقه نداشته باشیم، می توان ترتیبی از بلوک ها را پیدا کرد که تنها با یک بار اجرای الگوریتم روی هر بلوک، مقدار نهایی و صحیح هر بلوک به دست آید. برخی از ترتیب های ممکن برای پیمایش گراف در اجرای الگوریتم عبارتند از :
*پیمایش تصادفی : در این روش بلوک ها به ترتیب تصادفی پیمایش می شوند و به رو به جلو یا رو به عقب بودن تحلیل توجهی نمی شود به همین دلیل عملکرد این مدل ترتیب پیمایش به نسبت پبمایش های دیگر ضعیف است .
*پیمایش پس ترتیب {{انگلیسی| Postorder}} : این ترتیب پیمایش برای تحلیل رو به عقب مناسب است . در این روش هر گره زمانی دیده می شود که همه ی فرزندان آن در گراف دیده شده باشند .برای پیاده سازی این روش پیمایش از [[الگوریتم جستجوی اول عمق]] استفاده می شود.
*پیمایش عکس پس ترتیب {{انگلیسی|Reverse postorder}}: این ترتیب پیمایش برای تحلیل رو به جلو مناسب است . در این روش هر گره قبل از هر یک از فرزندانش دیده خواهد شد؛ مگر اینکه گره فرزند یک یال رو به عقب داشته باشد.(این روش با پیمایش پیشوندی {{انگلیسی| preorder}} متفاوت است.)
===الگوریتم تکرار راند-رابین===
الگوریتم تکرار راند-رابین یکی از الگوریتم هایی است که برای حل مسائل تجزیه و تحلیل جریان داده از آن استفاده می‌شود. در این الگوریتم در هر نوبت تکرار الگوریتم، همه بلاک ها از نو پیمایش می شوند و تا رسیدن به نقطه ثابت تکرار ادامه خواهد داشت. شبه کد این الگوریتم مشابه شبه کد زیر است :
{{چپچین}}
:for ''i'' ← 1 to ''N''
::''initialize node i''
:while (''sets are still changing'')
::for ''i'' ← 1 to ''N''
:::''recompute sets at node i''
{{پایان چپچین}}
ترتیب پیمایش گره ها در این روش ثابت است .
===رویکرد لیست کار===
این روش مدل بهبود یافته ای از الگوریتم راند-رابین است. در این روش، تکرار تنها در بخشی از گراف که در حال تغییر است انجام می شود. در این الگوریتم پس از مقدار دهی اولیه، یک لیست به نام لیست کار ایجاد می شود که در ابتدای الگوریتم همه ی گره ها در این لیست قرار دارند . در هر مرحله، یک گره از لیست کار حذف می شود و اطلاعات مربوط به جریان داده ی آن ، مشابه آنچه پیش تر توضیح داده شد، به روزرسانی می شود . اگر این به روزرسانی باعث تغییر در اطلاعات گره(حالت گره) شود ، همه ی گره هایی که این تغییر اطلاعات روی آنها تاثیر دارد به لیست کار اضافه می شوند و این فرآیند تا خالی شدن لیست کار ادامه خواهد داشت. شبه کد این الگوریتم مشابه زیر است<ref name="a"/> :
{{چپچین}}
:Worklist ← ∅
:for i ← 1 to N
::initialize the sets at node i add i to the Worklist
:while (Worklist ≠ ∅)
::remove a node i from the Worklist recompute set at node I
::if new set ≠ old set for i then
:::add each successor of i to Worklist, uniquely
{{پایان چپچین}}
*[[درهم کردن ثابت]]
*[[تفسیر انتزاعی]]
= منابع =
| 