الگوریتم هیرشبرگ
در علوم رایانه، الگوریتم هیرشبرگ الگوریتمی برای هم‌ترازسازی بهینهٔ دو توالی است که دان هیرشبرگ (Dan Hirschberg) در سال ۱۹۷۵ آن را ارائه کرد.
در این الگوریتم برای ارزیابی هم‌ترازی‌ها از فاصله لون‌اشتاین استفاده می‌شود؛ در هم‌ترازی بهینه مجموع هزینه‌های درج، حذف و جایگزین‌کردن حروف برای یکسان‌کردن دو رشته، کمینهٔ تمام هم‌ترازی‌های ممکن است.
الگوریتم نیدلمن-وانچ یکی از اولین الگوریتم‌هایی است که برای هم‌ترازسازی سراسری دو توالی از برنامه‌نویسی پویا استفاده می‌کند. الگوریتم هیرشبرگ در واقع نسخه‌ای از الگوریتم نیدلمن-وانچ است که با تقسیم و حل مسئله را حل می‌کند و مصرف حافظهٔ بهینه‌تری دارد.
هوشمندی الگوریتم هیرشبرگ در استفاده از مشاهده‌های زیر است: این الگوریتم از ایدهٔ Savitch در نظریهٔ پیچیدگی الهام گرفته‌است.
برای محاسبهٔ امتیاز هم‌ترازی (درج و حذف، جایگزینی و تطابق) از ماتریسهای امتیازدهی استفاده می‌شود. برای مثال، در ماتریس بلوسام-۶۲, امتیاز جایگزینی آمینواسیدهای Ala و Trp، تطابق آمینواسید Ala و حذف آمینواسید Ala، به ترتیب ۳-، ۴ و ۴- است.
معمولاً برای امتیازدهی هم‌ترازی‌های آمینواسیدی (توالی‌های پروتئینی) از ماتریس‌های بلوسام یا ماتریس‌های جهش پذیرفتهٔ نقطه‌ای استفاده می‌شود.
برای رشتهی مفروض formula_5; formula_6 حرف i ام این رشته (formula_7), formula_8 زیررشتهٔ آن از حرف i ام تا j ام و formula_9 رشتهٔ معکوس آن است.
برای دو حرف x و y که به ترتیب از رشتههای X و Y اند؛ امتیاز حذف x, درج y و جایگزینی x با y به ترتیب برابر formula_10است.
شبه‌کد: function NWscore(X,Y)
این تابع آخرین سطر از ماتریس امتیاز نیدلمن-وانچ را (که معمولاً با F یا score نشان داده می‌شود) در زمان formula_11 و با حافظهٔ formula_11 محاسبه می‌کند.
پیاده‌سازی زیر در MATLAB, با همین پیچیدگی زمانی ولی با حافظهٔ formula_13 نتیجه را محاسبه می‌کند: function [ lastLine ] = NWscore( X, Y )
% assume length(Y) <= length(X)
end
شبه‌کد: function Hirschberg(X,Y)
پیاده‌سازی در MATLAB: function [ Z, W, maxScore ] = Hirschberg( X, Y )
end این تابع با استفاده از روش تقسیم و حل، هم‌ترازی بهینه و امتیاز این هم‌ترازی را بدست می‌آورد. نحوهٔ پیاده‌سازی تابع NWscore بیان شد و تابع NW از الگوریتم نیدلمن-وانچ استفاده می‌کند. زمان اجرای این تابع formula_11 است. دقت کنید که الگوریتم نیدلمن-وانچ در حالت کلی به formula_11 حافظه نیاز دارد، اما اینجا، تنها درصورتی استفاده شده‌است که طول یکی از رشتهها (m یا n) برابر ۱ باشد و در نتیجه با مصرف حافظهٔ خطی اجرا می‌شود.
الگوریتم هیرشبرگ، مشابه الگوریتم نیدلمن-وانچ، بهترین امتیاز را با استفاده از برنامه‌نویسی پویا محاسبه کرده و هم‌ترازی متناظر با آن را می‌یابد.
پیچیدگی زمانی هم‌ترازی دو رشته با طول‌های m و n در الگوریتم هیرشبرگ formula_11 (مشابه الگوریتم نیدلمن-وانچ) است.
این الگوریتم تنها formula_13حافظه نیاز دارد که بهینه‌تر از الگوریتم نیدلمن-وانچ (با حافظه formula_11) است.
فرض کنید دو توالی DNA بنام‌های X و Y و امتیازهای هم‌ترازسازی به صورت زیر باشند:
formula_19
formula_20
در اولین مرحلهٔ الگوریتم هیرشبرگ،formula_21فراخوانده می‌شود که رشتهی X را به صورت formula_22 تقسیم‌بندی می‌کند.
سپس formula_23فراخوانده می‌شود که حاصل آن به صورت زیر است:
و در نتیجه: ScoreL = [ -8 -4 0 -2 -1 -3 ] rev(ScoreR) = [ -3 -1 1 0 -4 -8 ] Sum = [-11 -5 1 -2 -5 -11] بیشینهٔ امتیاز در ymid = ۲ است و در نتیجه formula_24 تقسیم‌بندی بهینهٔ Y است.
به همین ترتیب در هر مرحله زیررشته‌ها تقسیم شده و هم‌ترازی بهینه بدست می‌آید. درخت زیر خلاصه‌ای از مراحل تقسیم‌بندی در این مثال را نشان می‌دهد:
برگ‌های این درخت، هم‌ترازی بهینه را نشان می‌دهند که به صورت زیر است: W = AGTACGCA Z = --TATGC- معمولاً در بیوانفورماتیک از الگوریتم هیرشبرگ برای هم‌ترازسازی سراسری توالی‌های زیستی (توالی‌های آمینواسیدی و توالی‌های DNA) استفاده می‌شود. بلاست (BLAST) و فاستا (FASTA) نمونه‌های هیوریستیک استفاده از آن هستند.