الگوریتم هیرشبرگ: تفاوت میان نسخه‌ها

هوشمندی الگوریتم هیرشبرگ در استفاده از مشاهده‌های زیر است:<ref>{{یادکرد کتاب|عنوان="A linear space algorithm for computing maximal common subsequences"|نام خانوادگی=Hirschberg|نام=.Dan S|ناشر=Communications of the ACM|سال=1975|شابک=|مکان=|صفحات=http://dl.acm.org/citation.cfm?doid=360825.360861}}</ref>

# برای محاسبه‌یمحاسبهٔ امتیاز (یا فاصله‌ی) بهینه‌یبهینهٔ هم‌ترازی,هم‌ترازی، کافی است سطر‌سطر قبلی و سطر جاری را ذخیره کرد (و نه کل سطور ماتریس امتیاز نیدلمن-وانچ).

# اگر <math>(align1Z, align2W) = OptAlign(Str1X, Str2Y)</math>هم‌ترازی سراسری بهینه‌یبهینهٔ رشته‌های[[رشته Str1(علوم رایانه)|رشته]]های X و Str2Y باشد و <math>Str1X = Str1X^{leftl} + Str1X^{rightr}</math>تقسیم‌بندی دلخواهی از Str1X باشد,باشد، تقسیم بندیتقسیم‌بندی <math>Str2Y = Str2Y^{leftl} + Str2Y^{rightr}</math>از Str2Y وجود دارد که <math>(align1Z, align2W) = OptAlign(Str1X^{leftl}, Str2Y^{leftl}) + OptAlign(Str1X^{rightr}, Str2Y^{rightr})</math>.

برای محاسبه‌یمحاسبهٔ امتیاز هم‌ترازی (درج و حذف,حذف، جایگزینی و تطابق) از ماتریس‌های[[ماتریس]]های امتیازدهی استفاده می‌شود. برای مثال,مثال، در [[ماتریس]] [[بلوسام|بلوسام-۶۲]], امتیاز جایگزینی آمینواسید‌های[[اسید آمینه|آمینواسید]]های Ala و Trp,Trp، تطابق [[اسید آمینه|آمینواسید]] Ala و حذف [[اسید آمینه|آمینواسید]] Ala,Ala، به ترتیب 3۳-,، 4۴ و 4۴- است.

معمولامعمولاً برای امتیازدهی هم‌ترازی‌های آمینواسیدی[[اسید آمینه|آمینواسید]]ی (رشته‌هایتوالی‌های [[پروتئین|پروتئینی]]) از [[بلوسام|ماتریس‌های بلوسام و]] یا [[جهش پذیرفته نقطه‌ای|ماتریس‌های جهش پذیرفته‌یپذیرفتهٔ نقطه‌ای]] استفاده می‌شود.

برای رشته‌ی[[رشته (علوم رایانه)|رشته]]ی مفروض <math>X</math>; <math>X_i</math> حرف i ام این [[رشته (علوم رایانه)|رشته]] (<math>1\leq i\leq length(X)</math>), <math>X_{i:j}</math> زیررشته‌‌یزیررشتهٔ آن از حرف i ام تا j ام و <math>rev(X)</math> رشته‌یرشتهٔ معکوس آن است.

برای دو حرف x و y که به ترتیب از رشته‌های[[رشته (علوم رایانه)|رشته]]های X و Y اند;اند؛ امتیاز حذف و درج x, جایگزینی x بادرج y و تطابقجایگزینی x وبا y را به ترتیب برابر <math>Sub(x, y), Ins(xy), Del(x)</math>و <math>Match(x, y)</math>است.

if( Xi == Yj ) scoreSub = Score(i-1,j-1) + SubMatch(Xi, Yj)

پیاده‌سازی زیر در [[متلب|MATLAB]], با همین زمان[[پیچیدگی زمانی]] ولی با حافظه‌یحافظهٔ <math>O(min\{m, n\})</math> سطر آخرنتیجه را محاسبه می‌کند:<syntaxhighlight lang="matlab">

scorePrev = zeros(1, length(Y) + 1);

lastLine = zeros(1, length(Y) + 1);

for i = 1:length(Y)

scorePrev(i + 1) = scorePrev(i) + Ins(Y(i));

end

for i = 1:length(X)

lastLine(1) = scorePrev(1) + Del(X(i));

for j = 1:length(Y)

if( X(i) == Y(j) ) s1 = scorePrev(j) + Match(X(i), Y(j));

else s1 = scorePrev(j) + Sub(X(i), Y(j));

s2scorePrev = scorePrev(j + 1) + Del(X(i))lastLine;

(Z,W) = NeedlemanWunschNW(X,Y)

ScoreL = NWScoreNWscore(X1:xmid, Y)

ScoreR = NWScoreNWscore(rev(Xxmid+1:xlen), rev(Y))

پیاده‌سازی این تابع در [[متلب|MATLAB]]:<syntaxhighlight lang="matlab">

function [ align1Z, align2W, maxScore ] = Hirschberg( X, Y )

if( isempty(X) )

align1 Z = char(ones(1, length(Y)) * '-');

align2 W = Y;

elseif( isempty(Y) )

align1 Z = X;

align2 W = char(ones(1, length(X)) * '-');

elseif( length(X) == 1 || length(Y) == 1 )

[align1Z, align2W] = NW(X, Y, scoring);

else

mid1 = floor(length(X) / 2);

[~, s1] = NWscore(X(1:mid1), Y, scoring);

[~, s2] = NWscore(flip(X(mid1 + 1:end)), flip(Y), scoring);

[maxScore, mid2] = max(s1 + flip(s2));

mid2 = mid2 - 1;

[temp11, temp21] = Hirschberg(X(1:mid1), Y(1:mid2), scoring);

[temp12, temp22] = Hirschberg(X(mid1 + 1:end), Y(mid2 + 1:end), scoring);

align1 Z = [temp11, temp12];

align2 W = [temp21, temp22];

end

این الگوریتم تنها <math>O(min\{m, n\})</math>حافظه نیاز دارد که بهینه‌تر از الگوریتم نیدلمن-وانچ (با حافظه <math>O(mn)</math>) است. <ref>{{یادکرد کتابوب|عنواننویسنده=Hirschberg, D. S. (1975). "A linear space algorithm for computing maximal common subsequences".|نامکد خانوادگیزبان=|نامتاریخ=|ناشروبگاه=|سالنشانی=http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html|شابک=|مکان=|صفحاتعنوان=http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html}}</ref>