Նիդելման-Վունշի ալգորիթմ

Նիդլման — Վունշի ալգորիթմը — դա ալգորիթմ է երկու հաջորդականությունների հավասարեցումը կատարելու համար (կկոչենք նրանց $A$ և $B$), որոնք օգտագործվում են բիոինֆորմատիկայում ամինաթթվային կամ նուկլեոտիդա յին հաջորդականության հավասարումների ժամանակ: Ալգորիթմն առաջին անգամ առաջարկվել է 1970 թվականին Սոլ Նիդլմանի և Քրիստիան Վունշի կողմից:.

Նիդլման —Վունշի ալգորիթմը հանդիսանում է դինամիկ ծրագրավորման առաջին օրինակը համեմատած կենսաբանական հաջորդականության:

ժամանակակից պատկերացում

Հավասարեցված սիմվոլների համապատասխանությունը տրվում է նմանության մատրիցայի միջոցով: Այստեղ $S(a,\;b)$ — $a$ և $b$ սիմվոլների նմանությունն է : Այն նաև օգտագործվում է գծային տուգանք բացթողնման համար , որը այստեղ $d$-ն է:

Օրինակ, եթե նմանության մատրիցան տրվում է աղյուսակով.

-	A	G	C	T
A	10	-1	-3	-4
G	-1	7	-5	-3
C	-3	-5	9	0
T	-4	-3	0	8

ապա հավասարեցումը:

  AGACTAGTTAC
  CGA‒‒‒GACGT

$d=-5$ բացթողնման համար կունենա հետևյալ գնահատականը:

$S(A,\;C)+S(G,\;G)+S(A,\;A)+3\times d+S(G,\;G)+S(T,\;A)+S(T,\;C)+S(A,\;G)+S(C,\;T)$

$=-3+7+10-(3\times 5)+7+(-4)+0+(-1)+0=1.$

Ամենաբարձր գնահատականով հավասարում գտնելու համար նշանակվում է երկչափ մատրիցա F, այնքան տող պարունակող, որքան սիմվոլ կա $A$ հաջորդականության մեջ, և այնքան սյունակներ, որքան սիմվոլ կա $B$ հաջորդականության մեջ: $i$ տողի և $j$ սյունակի գրվածը հետագայում նշանակվում է իբրև $F_{ij}$: Այս կերպ , եթե մենք հավասարեցնում ենք $n$ и $m$ չափերի հաջորդականությունը, ապա պահանջվող հիշողության քանակը կլինի $O(nm)$. (Խիշբերգի ալգորիթմը թույլ է տալիս հանել օպտիմալ հավասարումը օգտագործելով $O(n+m)$ հիշողության քանակը, բայց մոտավորապես կրկնակի շատ հաշվման ժամկետ):

Ալգորիթմի աշխատանքի գործընթացի ժամանակ $F_{ij}$ մեծությունը կընդունի օպտիմալ գնահատականի նշանակություն առաջին , հավասարման համար ;n</math> սիմվոլները $A$-ում և առաջին $j=0,\;\ldots,\;m$ սիմվոլները $B$. Այդ ժամանակ Բելլմանի օպտիմալության սկզբունքը կարող է կառուցվել հետևյալ կերպ:

  Базис:
  $F_{0j}=d\cdot j$
  $F_{i0}=d\cdot i$
  $F_{ij}=\max(F_{i-1,\;j-1}+S(A_i,\;B_j),\;F_{i,\;j-1}+d,\;F_{i-1,\;j}+d).$

Այս կերպ ալգորիթի կեղծ կոդը   F  մատրիցայի հանման համար կունենա  հետևյալ  տեսքը

  for i=0 to length(A)
    F(i,0) ← d*i
  for j=0 to length(B)
    F(0, j) ← d*j
  for i=1 to length(A)
    for j = 1 to length(B)
    {
      Match ← F(i-1, j-1) + S(Ai, Bj)
      Delete ← F(i-1, j) + d
      Insert ← F(i, j-1) + d
      F(i, j) ← max(Match, Insert, Delete)
    }

Երբ  F մատրիցան  հաշվարկված է ,  նրա  $F_{ij}$ էլեմենտը տալիս է առավելագույն գնահատական բոլոր հնարավոր հավասարումների մեջ: Հավասարումն հաշվելու համար, որն   ստացել   է   նման գնահատական, պետք է սկսել ներքևի աջ վանդակից և նրանում համեմատել արժեքները, երեք հնարավոր աղյուրների հետ  (համապատասխանեցում, դրույք), որպեսզի տեսնենք, թե որտեղից այն :  $A_i$  և $B_j$ հավասարումների   համապատասխանության   դեպքում,  $A_i$ դելեցիայի դեպքում հավասարեցված է բացթողնման հետ , իսկ դրույքի դեպքում  բացթողնման հետ հավասարեցված է արդեն  $B_j$-ն: (Ընդհանուր դեպքում  հնարավոր է ավելի քան մեկ տարբերակ միևնույն նշանակությամբ, ինչը   կհանգեցնի   այլընտրանքային օպտիմալ  հավասարեցումներին: 

  AlignmentA ← ""
  AlignmentB ← ""
  i ← length(A)
  j ← length(B)
  while (i > 0 and j > 0)
  {
    Score ← F(i, j)
    ScoreDiag ← F(i - 1, j - 1)
    ScoreUp ← F(i, j - 1)
    ScoreLeft ← F(i - 1, j)
    if (Score == ScoreDiag + S(Ai, Bj))
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← Bj + AlignmentB
      i ← i - 1
      j ← j - 1
    }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← "-" + AlignmentB
      i ← i - 1
    }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA ← "-" + AlignmentA
      AlignmentB ← Bj + AlignmentB
      j ← j - 1
    }
  }
  while (i > 0)
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  while (j > 0)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← Bj + AlignmentB
    j ← j - 1
  }

Պատմական դիտողություն

Նիդլմանը և Վունշը իրենց ալգորիթմը նկարագրել են բացահայտ ձևով այն դեպքի համար, երբ գնահատվում է միայն համապատասխանող և չհամապատասխանող սիմվոլները, սակայն ոչ ($d=0$)- ի դեպքում: 1970 թվականից օրիգինալ հրապարակմամբ առաջարկվում է ռեկուրսիան

$F_{ij}=\max_{h<i,\;k<j}\{F_{h,\;j-1}+S(A_i,\;B_j),\;F_{i-i,\;k}+S(A_i,\;B_j)\}.$

Դինամիկ ծրագրավորման անհամապատասխանող ալգորիթմը հաշվարկման համար պահանջում է խորնարդ ժամ: Հոդվածում նաև նշվում է , որ ռեկուրսիան կարղ է լինել ադապտացված տուգանքների բացթողնման համար ցանկացած բանաձևի դեպքում:

Տուգանքի մեծության բացթողումը կարող է լինել չափի ֆունկցիան կամ բացթողնման ուղղությունը: Այդ նույն խնդրի լուծումը (չկա տուգանքի բացթողում) առաջին անգամ շարադրվել է 1972թվականին Դավիդ Սանկոֆի կողմից: Համանման քառակուսու ալգորիթմը ժամանակին ինքնուրույն բացահայտել է 1968 թվականին Տ. Վինցիուկը, խոսքի վերամշակում (դինամիկ սանդղակի նախաաղավաղումներ) Ռոբերտի, Ա. Վագների, Մայկլի և Ֆիշերի 1974 թվականին(տողերի համեմատում):

Նիդլմանը և Վունշը ձևավորեցին իրենց խնդիրը տերմինների առավելագույն նմանությամբ:Մյուս հնարավորությունը կայանում է տարածություն հերթականության խմբագրումը , առաջադրված Լևենշտեյնի կողմից և ցույց է տրված, որ այս երկու խնդիրները երկվալենտ են:,