الگوریتم هیرشبرگ

 

در علوم رایانه, الگوریتم هیرشبرگ (به انگلیسی Hirschberg's Algorithm) الگوریتمی پویا برای هم‌ترازسازی بهینه‌ی دو توالی است که دان هیرشبرگ (Dan Hirschberg) طی سال‌های ۱۹۷۵ و ۱۹۷۷ آن را ابداع و ارائه کرد.

در این الگوریتم برای ارزیابی هم‌ترازی‌ها از فاصله لون‌اشتاین استفاده می‌شود; در هم‌ترازی بهینه مجموع هزینه‌های درج, حذف و جایگزین‌کردن حروف برای یکسان‌کردن دو رشته, کمینه‌ی تمام هم‌ترازی‌های ممکن است.

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

معمولا در بیوانفورماتیک از الگوریتم هیرشبرگ برای هم‌ترازسازی سراسری توالی‌های زیستی (توالی‌های آمینواسیدی و توالی‌های DNA) استفاده می‌شود.

تشابه با الگوریتم نیدلمن-وانچ

الگوریتم هیرشبرگ, مشابه الگوریتم نیدلمن-وانچ, بهترین امتیاز را با استفاده از برنامه نویسی پویا محاسبه کرده و هم‌ترازی متناظر با آن را می‌یابد.

ایده‌های اصلی

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

1. برای محاسبه‌ی امتیاز (یا فاصله‌ی) بهینه‌ی هم‌ترازی, کافی است سطر‌ قبلی و سطر جاری را ذخیره کرد (و نه کل سطور ماتریس امتیاز نیدلمن-وانچ).
2. اگر $(align1,align2)=OptAlign(Str1,Str2)$هم‌ترازی سراسری بهینه‌ی رشته‌های Str1 و Str2 باشد و $Str1=Str1^{left}+Str1^{right}$تقسیم‌بندی دلخواهی از Str1 باشد, تقسیم بندی $Str2=Str2^{left}+Str2^{right}$از Str2 وجود دارد که $(align1,align2)=OptAlign(Str1^{left},Str2^{left})+OptAlign(Str1^{right},Str2^{right})$.

امتیازدهی

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

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

الگوریتم

برای رشته‌ی مفروض $X$; $X_{i}$ حرف i ام این رشته‌ ($1\leq i\leq length(X)$), $X_{i:j}$ زیررشته‌‌ی آن از حرف i ام تا j ام و $rev(X)$ رشته‌ی معکوس آن است.

برای دو حرف x و y که به ترتیب از رشته‌های X و Y اند; امتیاز حذف x, درج y, جایگزینی x با y و تطابق x و y به ترتیب برابر $Sub(x,y),Ins(y),Del(x)$و $Match(x,y)$است.

تابع $NW(X,y)$آخرین سطر از ماتریس امتیاز نیدلمن-وانچ (که معمولا با F یا score نشان داده می‌شود) را برمی‌گرداند:

function NWScore(X,Y)
   Score(0,0) = 0
   for j=1 to length(Y)
     Score(0,j) = Score(0,j-1) + Ins(Yj)
   for i=1 to length(X)
     Score(i,0) = Score(i-1,0) + Del(Xi)
     for j=1 to length(Y)
       scoreSub = Score(i-1,j-1) + Sub(Xi, Yj)
       scoreDel = Score(i-1,j) + Del(Xi)
       scoreIns = Score(i,j-1) + Ins(Yj)
       Score(i,j) = max(scoreSub, scoreDel, scoreIns)
     end
   end
   for j=0 to length(Y)
     LastLine(j) = Score(length(X),j)
   return LastLine

این شبه‌کد, آخرین سطر ماتریس را در زمان $O(mn)$ و با حافظه‌ی $O(mn)$ محاسبه می‌کند. پیاده‌سازی زیر در MATLAB, با همین پیچیدگی زمانی ولی با حافظه‌ی $O(min\{m,n\})$ نتیجه را محاسبه می‌کند:

function [ lastLine ] = NWscore( X, Y )

% assume length(Y) <= length(X)

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));
        end
        s2 = scorePrev(j + 1) + Del(X(i));
        s3 = lastLine(j) + Ins(Y(j));
        lastLine(j + 1) = max([s1, s2, s3]);
    end
    scorePrev = lastLine;
end
    
end

تابع Hirschberg هم‌ترازی بهینه دو رشته را پیدا می‌کند:

function Hirschberg(X,Y)
   Z = ""
   W = ""
   if length(X) == 0
     for i=1 to length(Y)
       Z = Z + '-'
       W = W + Yi
     end
   else if length(Y) == 0
     for i=1 to length(X)
       Z = Z + Xi
       W = W + '-'
     end
   else if length(X) == 1 or length(Y) == 1
     (Z,W) = NeedlemanWunsch(X,Y)
   else
     xlen = length(X)
     xmid = length(X)/2
     ylen = length(Y)
 
     ScoreL = NWScore(X1:xmid, Y)
     ScoreR = NWScore(rev(Xxmid+1:xlen), rev(Y))
     ymid = arg max ScoreL + rev(ScoreR)
 
     (Z,W) = Hirschberg(X1:xmid, y1:ymid) + Hirschberg(Xxmid+1:xlen, Yymid+1:ylen)
   end
   return (Z,W)

پیاده‌سازی این تابع در MATLAB:

function [ align1, align2, maxScore ] = Hirschberg( X, Y )

if( isempty(X) )
    align1 = char(ones(1, length(Y)) * '-');
    align2 = Y;
elseif( isempty(Y) )
    align1 = X;
    align2 = char(ones(1, length(X)) * '-');
elseif( length(X) == 1 || length(Y) == 1 )
    [align1, align2] = 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 = [temp11, temp12];
    align2 = [temp21, temp22];
end

end

هزینه‌ی اجرا

پیچیدگی زمانی هم‌ترازی دو رشته با طول‌های m و n در الگوریتم هیرشبرگ $O(mn)$ (مشابه الگوریتم نیدلمن-وانچ) است.

این الگوریتم تنها $O(min\{m,n\})$حافظه نیاز دارد که بهینه‌تر از الگوریتم نیدلمن-وانچ (با حافظه $O(mn)$) است.