هم تراز سازی در حافظه خطی

دانشنامه عمومی

در بیوانفورماتیک، هم ترازسازی از الگوریتم های پرکاربرد برای سنجش شباهت بین مقایسه توالی های زیستی مانند: آران ای، دی ان ای و پروتئین است. روش های هم ترازسازی در حالت عادی، حافظه زیادی مصرف می کنند. به همین دلیل در صورت طولانی بودن رشته های ورودی به دلیل محدودیت حافظه دسترسی تصادفی ( RAM ) قابل انجام نیستند. به همین دلیل نیاز داریم الگوریتم هایی طراحی کنیم که حافظه را بهینه تر مصرف کنند. ایده اصلی این روش، استفاده از الگوریتم تقسیم و حل است.
برای اینکه شباهت دو رشته را پیدا کنیم میتوانیم گرافای به شکل جدول بسازیم. راس سطر i ام و ستون j ام نشان می دهد که روی حرف i از رشته اول ( سمت راست ) و حرف j از رشته دوم ( سمت بالا ) هستیم. هر مسیر ممکن از راس بالا سمت چپ به پایین سمت راست نشان دهنده یک جواب ممکن است. یال های عمودی نشان دهنده جلو رفتن روی رشته اول، یال های افقی جلو رفتن روی رشته دوم و یال های مورب جلو رفتن روی هر دو رشته را نشان می دهند. وزن یال ها از روی یک ماتریس شباهت مانند BLOSUM62 که البته برای آمینواسیدها است تعریف می شود. به طور کلی بیشترین وزن را یال هایی دارند که مربوط به حرف های یکی هستند. مانند یال های قرمز در شکل.
پس مسئله هم تراز سازی به پیدا کردن طولانی ترین مسیر در یک گراف که در اینجا حالتی از گراف جهت دار غیرمدور است تبدیل می شود. این مسئله یکی از مسائل معروف حوزه برنامه نویسی پویا است و به راحتی می توان آن را در زمان O ( | S 1 | × | S 2 | ) حل کرد. به این شکل که برای هر راس وزن طولانی ترین مسیر به آن را w e i g h t می نامیم و به این شکل بروز رسانی می کنیم:
weight = 0 n = size ( s1 ) m = size ( s2 ) for i - > 0 to n: for j - > 0 to m: a = weight + score ( s1, s2 ) // socre in the matrix b = weight + penalty // penalty for skipping a character c = weight + penalty weight = max ( a, b, c ) return weight محاسبه امتیاز هم تراز سازی اگر تنها چیزی که برای ما مهم است محاسبه بیشترین امتیاز هم تراز سازی باشد همان طور که در کد بخش قبل می توان دید برای بروز رسانی تنها به سطر آخر آرایه w e i g h t نیاز داریم. پس تنها همان سطر را ذخیره سازی می کنیم و وقتی مقدارهای سطر بعد محاسبه شدند می توان این مقادیر را جایگزین کرد و آرایه w e i g h t یک بعدی می شود. بنابراین حافظه اجرایی خطی می شود.
عکس هم تراز سازی در حافظه خطیعکس هم تراز سازی در حافظه خطی
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران