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

در بیوانفورماتیک، هم‌ترازسازی از الگوریتم‌های پرکاربرد برای سنجش شباهت بین مقایسه توالی‌های زیستی مانند: ‌آران‌ای، دی‌ان‌ای و پروتئین است. روش‌های هم‌ترازسازی در حالت عادی، حافظه زیادی مصرف می‌کنند. به همین دلیل در صورت طولانی بودن رشته‌های ورودی به دلیل محدودیت حافظه دسترسی تصادفی(RAM) قابل انجام نیستند. به همین دلیل نیاز داریم الگوریتم‌هایی طراحی کنیم که حافظه را بهینه‌تر مصرف کنند. ایده اصلی این روش، استفاده از الگوریتم تقسیم و حل است.

مقدمه

جدول هم‌تراز سازی

برای اینکه شباهت دو رشته را پیدا کنیم میتوانیم گرافای به شکل جدول بسازیم. راس سطر $i$ام و ستون $j$ام نشان می‌دهد که روی حرف $i$ از رشته اول(سمت راست) و حرف $j$ از رشته دوم(سمت بالا) هستیم. هر مسیر ممکن از راس بالا سمت چپ به پایین سمت راست نشان دهنده یک جواب ممکن است. یال‌های عمودی نشان دهنده جلو رفتن روی رشته اول، یال‌های افقی جلو رفتن روی رشته دوم و یال‌های مورب جلو رفتن روی هر دو رشته را نشان می‌دهند. وزن یال‌ها از روی یک ماتریس شباهت مانند BLOSUM62 که البته برای آمینواسیدها است تعریف می‌شود. به طور کلی بیشترین وزن را یال‌هایی دارند که مربوط به حرف‌های یکی هستند. مانند یال‌های قرمز در شکل.

پس مسئله هم‌تراز سازی به پیدا کردن طولانی‌ترین مسیر در یک گراف که در اینجا حالتی از گراف جهت‌دار غیرمدور است تبدیل می‌شود. این مسئله یکی از مسائل معروف حوزه برنامه‌نویسی پویا است و به راحتی می‌توان آن را در زمان $O(|S_{1}|\times |S_{2}|)$ حل کرد. به این شکل که برای هر راس وزن طولانی‌ترین مسیر به آن را $weight[i][j]$ می‌نامیم و به این شکل بروز رسانی می‌کنیم:

weight[0][0] = 0
n = size(s1)
m = size(s2)
for i -> 0 to n:
	for j -> 0 to m:
		a = weight[i - 1][j - 1] + score(s1[i], s2[j]) // socre in the matrix
		b = weight[i - 1][j] + penalty // penalty for skipping a character
		c = weight[i][j - 1] + penalty 
		weight[i][j] = max(a, b, c)

return weight[n][m]

محاسبه امتیاز هم‌تراز سازی

اگر تنها چیزی که برای ما مهم است محاسبه بیشترین امتیاز هم‌تراز سازی باشد همان‌طور که در کد بخش قبل می‌توان دید برای بروز رسانی تنها به سطر آخر آرایه $weight$ نیاز داریم. پس تنها همان سطر را ذخیره سازی می‌کنیم و وقتی مقدارهای سطر بعد محاسبه شدند می‌توان این مقادیر را جایگزین کرد و آرایه $weight$ یک بعدی می‌شود. بنابراین حافظه اجرایی خطی می‌شود.

محاسبه روش هم‌تراز سازی

ستون وسط گراف هم‌ترازی

برای اینکه بلندترین مسیر و در واقع تطابق‌ها را حساب کنیم ایده بخش قبل کارساز نیست چون باید اشاره‌گرهایی را ذخیره کنیم تا در نهایت بتوانیم مسیر را پیدا کنیم.

الگوریتم هم‌تراز سازی در حافظه خطی:

ستون وسط گراف را در نظر بگیرید. نکته کلیدی این الگوریتم این است که بهترین مسیر بالاخره در جایی از این ستون عبور می‌کند. هدف اولیه ما این است که در حافظه خطی،این جا را پیدا کنیم. البته ممکن است یکتا نباشد و چندین راس در ستون وسط بتوانند بخشی از بلندترین مسیر باشند که پیدا کردن یکی از آن‌ها کافی است. $length_{i}$ را بلند ترین مسیر که از راس حاضر در ستون وسط و سطر $i$ام (راس $v$) است بنامید. همچنین $fromSource_{i}$ را بلندترین مسیر بین شروع و $v$ تعریف کنیم. و $toSink_{i}$ را بلندترین مسیر بین $v$ و راس پایانی.

$length_{i}=fromSource_{i}+toSink(i)$ می‌شود یعنی جمع مسیرش از شروع تا $v$ و از $v$ تا پایان.

پس کافی است $fromSource$ و $toSink$ را حساب کنیم. محاسبه هر یک از آن‌ها مشابه الگوریتمی که در بخش قبل گفته شد در حافظه خطی قابل انجام است فقط نتیجه‌ها را باید ذخیره کنیم تا در نهایت آرایه $length$ را بسازیم. بعد از اینکه راس بهینه برای ستون وسط پیدا شد (راس سیاه شکل یا $middleNode$) کافی است اجرای الگوریتم را برای مستطیل‌های با گوشه‌های شروع تا $middleNode$ و $middleNode$ تا پایان انجام دهیم.

پیچیدگی زمانی همچنان $O(|S_{1}|\times |S_{2}|)$ اما حافظه خطی می‌شود.

شبه کد این الگوریتم:

    LinearSpaceAlignment(top, bottom, left, right)
        if left = right
            return alignment formed by bottom − top vertical edges
        if top = bottom
            return alignment formed by right − left horizontal edges
        middle ← ⌊ (left + right)/2⌋
        midNode ← MiddleNode(top, bottom, left, right)
        midEdge ← MiddleEdge(top, bottom, left, right)
        LinearSpaceAlignment(top, midNode, left, middle)
        output midEdge
        if midEdge = "→" or midEdge = "↘"
            middle ← middle + 1
        if midEdge = "↓" or midEdge ="↘"
            midNode ← midNode + 1
        LinearSpaceAlignment(midNode, bottom, middle, right)

جستارهای وابسته

• هم‌ترازسازی توالی
• برنامه‌نویسی پویا
• الگوریتم تقسیم و حل