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

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

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

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

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

-AGCT
A10-1-3-4
G-17-5-3
C-3-590
T-4-308

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

 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 սիմվոլները 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 &larr; ""
  i &larr; '''length'''(A)
  j &larr; '''length'''(B)
  '''while''' (i > 0 '''and''' j > 0)
  {
 Score &larr; F(i, j)
 ScoreDiag &larr; F(i - 1, j - 1)
 ScoreUp &larr; F(i, j - 1)
 ScoreLeft &larr; F(i - 1, j)
 '''if''' (Score == ScoreDiag + S(A<sub>i</sub>, B<sub>j</sub>))
 {
  AlignmentA &larr; A<sub>i</sub> + AlignmentA
  AlignmentB &larr; B<sub>j</sub> + AlignmentB
  i &larr; i - 1
  j &larr; j - 1
 }
 '''else''' '''if''' (Score == ScoreLeft + d)
 {
  AlignmentA &larr; A<sub>i</sub> + AlignmentA
  AlignmentB &larr; "-" + AlignmentB
  i &larr; i - 1
 }
 '''otherwise''' (Score == ScoreUp + d)
 {
  AlignmentA &larr; "-" + AlignmentA
  AlignmentB &larr; B<sub>j</sub> + AlignmentB
  j &larr; j - 1
 }
  }
  '''while''' (i > 0)
  {
 AlignmentA &larr; A<sub>i</sub> + AlignmentA
 AlignmentB &larr; "-" + AlignmentB
 i &larr; i - 1
  }
  '''while''' (j > 0)
  {
 AlignmentA &larr; "-" + AlignmentA
 AlignmentB ← B<sub>j</sub> + AlignmentB
 j ← j - 1
  }
`

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

: F_{ij}=\max_{h

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

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

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

## Ծանոթագրություններ

Կատեգորիա:Դինամիկ ծրագրավորում
Կատեգորիա:Կենսաինֆորմատիկա