هم‌تراز سازی در حافظه خطی کیست؟ توضیح بده.
در بیوانفورماتیک، هم‌ترازسازی از الگوریتم‌های پرکاربرد برای سنجش شباهت بین مقایسه توالی‌های زیستی مانند: ‌آران‌ای، دی‌ان‌ای و پروتئین است. روش‌های هم‌ترازسازی در حالت عادی، حافظه زیادی مصرف می‌کنند. به همین دلیل در صورت طولانی بودن رشته‌های ورودی به دلیل محدودیت حافظه دسترسی تصادفی(RAM) قابل انجام نیستند. به همین دلیل نیاز داریم الگوریتم‌هایی طراحی کنیم که حافظه را بهینه‌تر مصرف کنند. ایده اصلی این روش، استفاده از الگوریتم تقسیم و حل است.مقدمه.برای اینکه شباهت دو رشته را پیدا کنیم میتوانیم گرافای به شکل جدول بسازیم. راس سطر formula_1ام و ستون formula_2ام نشان می‌دهد که روی حرف formula_1 از رشته اول(سمت راست) و حرف formula_2 از رشته دوم(سمت بالا) هستیم. هر مسیر ممکن از راس بالا سمت چپ به پایین سمت راست نشان دهنده یک جواب ممکن است. یال‌های عمودی نشان دهنده جلو رفتن روی رشته اول، یال‌های افقی جلو رفتن روی رشته دوم و یال‌های مورب جلو رفتن روی هر دو رشته را نشان می‌دهند. وزن یال‌ها از روی یک ماتریس شباهت مانند که البته برای آمینواسیدها است تعریف می‌شود. به طور کلی بیشترین وزن را یال‌هایی دارند که مربوط به حرف‌های یکی هستند. مانند یال‌های قرمز در شکل.پس مسئله هم‌تراز سازی به پیدا کردن طولانی‌ترین مسیر در یک گراف که در اینجا حالتی از گراف جهت‌دار غیرمدور است تبدیل می‌شود. این مسئله یکی از مسائل معروف حوزه برنامه‌نویسی پویا است و به راحتی می‌توان آن را در زمان formula_5 حل کرد. به این شکل که برای هر راس وزن طولانی‌ترین مسیر به آن را formula_6 می‌نامیم و به این شکل بروز رسانی می‌کنیم:weight[0][0] = 0n = size(s1)m = size(s2)for i -&gt; 0 to n: for j -&gt; 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]محاسبه امتیاز هم‌تراز سازی.اگر تنها چیزی که برای ما مهم است محاسبه بیشترین امتیاز هم‌تراز سازی باشد همان‌طور که در کد بخش قبل می‌توان دید برای بروز رسانی تنها به سطر آخر آرایه formula_7 نیاز داریم. پس تنها همان سطر را ذخیره سازی می‌کنیم و وقتی مقدارهای سطر بعد محاسبه شدند می‌توان این مقادیر را جایگزین کرد و آرایه formula_7 یک بعدی می‌شود. بنابراین حافظه اجرایی خطی می‌شود.محاسبه روش هم‌تراز سازی.برای اینکه بلندترین مسیر و در واقع تطابق‌ها را حساب کنیم ایده بخش قبل کارساز نیست چون باید اشاره‌گرهایی را ذخیره کنیم تا در نهایت بتوانیم مسیر را پیدا کنیم.الگوریتم هم‌تراز سازی در حافظه خطی:ستون وسط گراف را در نظر بگیرید. نکته کلیدی این الگوریتم این است که بهترین مسیر بالاخره در جایی از این ستون عبور می‌کند. هدف اولیه ما این است که در حافظه خطی،این جا را پیدا کنیم. البته ممکن است یکتا نباشد و چندین راس در ستون وسط بتوانند بخشی از بلندترین مسیر باشند که پیدا کردن یکی از آن‌ها کافی است. formula_9 را بلند ترین مسیر که از راس حاضر در ستون وسط و سطر formula_1ام (راس formula_11) است بنامید. همچنین formula_12 را بلندترین مسیر بین شروع و formula_11 تعریف کنیم. و formula_14 را بلندترین مسیر بین formula_11 و راس پایانی.formula_16 می‌شود یعنی جمع مسیرش از شروع تا formula_11 و از formula_11 تا پایان.پس کافی است formula_19 و formula_20 را حساب کنیم. محاسبه هر یک از آن‌ها مشابه الگوریتمی که در بخش قبل گفته شد در حافظه خطی قابل انجام است فقط نتیجه‌ها را باید ذخیره کنیم تا در نهایت آرایه formula_21 را بسازیم. بعد از اینکه راس بهینه برای ستون وسط پیدا شد (راس سیاه شکل یا formula_22) کافی است اجرای الگوریتم را برای مستطیل‌های با گوشه‌های شروع تا formula_22 و formula_22 تا پایان انجام دهیم.پیچیدگی زمانی همچنان formula_5 اما حافظه خطی می‌شود.شبه کد این الگوریتم:&lt;syntaxhighlight&gt; 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)&lt;/syntaxhighlight&gt;