خوارزمية هيرشبرغ

في علم الحاسوب ، تُعدّ خوارزمية هيرشبيرغ ، نسبةً إلى مخترعها دان هيرشبيرغ ، خوارزمية برمجة ديناميكية تُستخدم لإيجاد أفضل محاذاة تسلسلية بين سلسلتين نصيتين . تُقاس هذه المحاذاة المثلى بمسافة ليفنشتاين ، وهي مجموع تكاليف عمليات الإدخال والاستبدال والحذف والإجراءات الفارغة اللازمة لتحويل إحدى السلسلتين إلى الأخرى. تُوصف خوارزمية هيرشبيرغ ببساطة بأنها نسخة أكثر كفاءة في استخدام المساحة من خوارزمية نيدلمان-وونش ، وتستخدم البرمجة الديناميكية . ^{[ 1 ]} تُستخدم خوارزمية هيرشبيرغ بشكل شائع في علم الأحياء الحاسوبي لإيجاد أفضل محاذاة شاملة لتسلسلات الحمض النووي والبروتين .

خوارزمية هيرشبرغ هي خوارزمية عامة قابلة للتطبيق لتحقيق محاذاة تسلسل مثالية. أما خوارزميتا BLAST و FASTA فهما خوارزميتان استدلاليتان دون المستوى الأمثل .${\displaystyle X}$و${\displaystyle Y}$هي سلاسل نصية، حيث${\displaystyle \operatorname {length} (X)=n}$و${\displaystyle \operatorname {length} (Y)=m}$، تجد خوارزمية Needleman-Wunsch محاذاة مثالية في${\displaystyle O(nm)}$الوقت، باستخدام${\displaystyle O(nm)}$المساحة. خوارزمية هيرشبرغ هي تعديل ذكي لخوارزمية نيدلمان-وونش، والتي لا تزال تأخذ${\displaystyle O(nm)}$الوقت، ولكن الاحتياجات فقط${\displaystyle O(\min\{n,m\})}$^{[ 2 ]} يُعدّ هذا الأسلوب أسرع بكثير من الناحية العملية، ويستهلك مساحة تخزين كبيرة. ومن تطبيقاته إيجاد محاذاة تسلسل الحمض النووي أو البروتينات. كما أنه طريقة فعّالة من حيث المساحة لحساب أطول تسلسل فرعي مشترك بين مجموعتين من البيانات، كما هو الحال مع أداة المقارنة الشائعة .

يمكن اشتقاق خوارزمية هيرشبرغ من خوارزمية نيدلمان-وونش من خلال ملاحظة ما يلي: ^{[ 3 ]}

1. يمكن حساب درجة المحاذاة المثلى عن طريق تخزين الصف الحالي والصف السابق فقط من مصفوفة درجات نيدلمان-وونش؛
2. لو${\displaystyle (Z,W)=\operatorname {NW} (X,Y)}$هو المحاذاة المثلى لـ${\displaystyle (X,Y)}$، و${\displaystyle X=X^{l}+X^{r}}$هو تقسيم عشوائي لـ${\displaystyle X}$يوجد تقسيم${\displaystyle Y^{l}+Y^{r}}$ل${\displaystyle Y}$بحيث${\displaystyle \operatorname {NW} (X,Y)=\operatorname {NW} (X^{l},Y^{l})+\operatorname {NW} (X^{r},Y^{r})}$.

${\displaystyle X_{i}}$يشير إلى الحرف رقم i من${\displaystyle X}$، أين${\displaystyle 1\leqslant i\leqslant \operatorname {length} (X)}$.${\displaystyle X_{i:j}}$يشير إلى سلسلة فرعية بحجم${\displaystyle j-i+1}$، بدءًا من الحرف i وحتى الحرف j من${\displaystyle X}$.${\displaystyle \operatorname {rev} (X)}$هو النسخة المعكوسة من${\displaystyle X}$.

${\displaystyle X}$و${\displaystyle Y}$هي تسلسلات يجب محاذاتها.${\displaystyle x}$كن شخصية من${\displaystyle X}$، و${\displaystyle y}$كن شخصية من${\displaystyle Y}$نفترض أن${\displaystyle \operatorname {Del} (x)}$،${\displaystyle \operatorname {Ins} (y)}$و${\displaystyle \operatorname {Sub} (x,y)}$هي دوال محددة جيدًا ذات قيم صحيحة. تمثل هذه الدوال تكلفة الحذف${\displaystyle x}$، إدخال${\displaystyle y}$واستبدالها${\displaystyle x}$مع${\displaystyle y}$، على التوالى.

نحن نحدد${\displaystyle \operatorname {NWScore} (X,Y)}$، والذي يُعيد السطر الأخير من مصفوفة نقاط نيدلمان-وونش${\displaystyle \mathrm {Score} (i,j)}$:

دالة NWScore(X, Y) Score(0, 0) = 0 // مصفوفة 2 * (طول(Y) + 1) من أجل j = 1 إلى طول(Y) Score(0, j) = Score(0, j - 1) + Ins(Y j ) for i = 1 to length(X) // تهيئة المصفوفة Score(1, 0) = Score(0, 0) + Del(X i ) for j = 1 to length(Y) scoreSub = Score(0, j - 1) + Sub(X i , Y j ) scoreDel = Score(0, j) + Del(X i ) scoreIns = Score(1, j - 1) + Ins(Y j ) Score(1, j) = max(scoreSub, scoreDel, scoreIns) نهاية // انسخ Score[1] إلى Score[0] النتيجة(0، :) = النتيجة(1، :) نهاية حلقة التكرار من j = 0 إلى طول (Y) LastLine(j) = Score(1, j) إرجاع السطر الأخير

لاحظ أنه في أي وقت،${\displaystyle \operatorname {NWScore} }$لا يتطلب الأمر سوى الصفين الأخيرين من مصفوفة النتائج. وبالتالي،${\displaystyle \operatorname {NWScore} }$يتم تنفيذه في${\displaystyle O(\min\{\operatorname {length} (X),\operatorname {length} (Y)\})}$فضاء.

تتبع خوارزمية هيرشبرغ ما يلي:

دالة هيرشبرغ(X، Y) Z = "" W = "" إذا كان طول (X) يساوي صفرًا، فكرر العملية من أجل i = 1 إلى طول (Y). Z = Z + '-' W = W + Y i end else if length(Y) == 0 for i = 1 to length(X) Z = Z + X i W = W + '-' وإلا إذا كان طول (X) يساوي 1 أو طول (Y) يساوي 1 (Z, W) = NeedlemanWunsch(X, Y) آخر xlen = length(X) xmid = length(X) / 2 ylen = length(Y) ScoreL = NWScore(X 1:xmid , Y) ScoreR = NWScore(rev(X xmid+1:xlen ), rev(Y)) ymid = arg max ScoreL + rev(ScoreR) (Z,W) = هيرشبيرج(X 1:xmid , y 1:ymid ) + Hirschberg(X xmid+1:xlen , Y ymid+1:ylen ) عودة النهاية (Z, W)

في سياق الملاحظة (2)، افترض أن${\displaystyle X^{l}+X^{r}}$هو تقسيم لـ${\displaystyle X}$. فِهرِس${\displaystyle \mathrm {ymid} }$يتم حسابها بحيث${\displaystyle Y^{l}=Y_{1:\mathrm {ymid} }}$و${\displaystyle Y^{r}=Y_{\mathrm {ymid} +1:\operatorname {length} (Y)}}$.

يترك

${\displaystyle {\begin{aligned}X&={\text{AGTACGCA}},\\Y&={\text{TATGC}},\\\operatorname {Del} (x)&=-2,\\\operatorname {Ins} (y)&=-2,\\\operatorname {Sub} (x,y)&={\begin{cases}+2,&{\text{if }}x=y\\-1,&{\text{if }}x\neq y.\end{cases}}\end{aligned}}}$

يتم تحديد المحاذاة المثلى بواسطة

W = AGTACGCA Z = --TATGC-

في الواقع، يمكن التحقق من ذلك عن طريق التراجع إلى مصفوفة نيدلمان-وونش المقابلة لها:

TATGC 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 G -4 -3 -2 -1 0 -2 T -6 -2 -4 0 -2 -1 A -8 -4 0 -2 -1 -3 C -10 -6 -2 -1 -3 1 G -12 -8 -4 -3 1 -1 C -14 -10 -6 -5 -1 3 A -16 -12 -8 -7 -3 1

يبدأ الأمر باستدعاء المستوى الأعلى إلى${\displaystyle \operatorname {Hirschberg} ({\text{AGTACGCA}},{\text{TATGC}})}$، مما يقسم الحجة الأولى إلى نصفين:${\displaystyle X={\text{AGTA}}+{\text{CGCA}}}$الدعوة إلى${\displaystyle \operatorname {NWScore} ({\text{AGTA}},Y)}$ينتج المصفوفة التالية:

TATGC 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 G -4 -3 -2 -1 0 -2 T -6 -2 -4 0 -2 -1 A -8 -4 0 -2 -1 -3

على نفس المنوال،${\displaystyle \operatorname {NWScore} (\operatorname {rev} ({\text{CGCA}}),\operatorname {rev} (Y))}$ينتج المصفوفة التالية:

CGTAT 0 -2 -4 -6 -8 -10 أ -2 -1 -3 -5 -4 -6 ج -4 0 -2 -4 -6 -5 ز -6 -2 2 0 -2 -4 ج -8 -4 0 1 -1 -3

أما الأسطر الأخيرة (بعد عكس الأخيرة) ومجموعها فهي على التوالي

ScoreL = [ -8 -4 0 -2 -1 -3 ] rev(ScoreR) = [ -3 -1 1 0 -4 -8 ] المجموع = [-11 -5 1 -2 -5 -11]

تظهر القيمة القصوى (الموضحة بالخط العريض) عند ymid = 2، مما ينتج عنه التقسيم${\displaystyle Y={\text{TA}}+{\text{TGC}}}$.

ينتج عن عملية التكرار الكاملة لهيرشبرغ (والتي نحذفها للاختصار) الشجرة التالية:

 (AGTACGCA,TATGC) / \ (AGTA,TA) (CGCA,TGC) / \ / \ (AG, ) (TA,TA) (CG,TG) (CA,C) / \ / \ (ص،ص) (أ،أ) (ج،ص) (ج،ج)

تحتوي أوراق الشجرة على المحاذاة المثلى.

• أطول سلسلة فرعية مشتركة