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

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

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

 ժամանակակից պատկերացում 
Հավասարեցված սիմվոլների համապատասխանությունը տրվում է նմանության մատրիցայի միջոցով։ Այստեղ  -  և  սիմվոլների նմանությունն է։ Այն նաև օգտագործվում է գծային տուգանք բացթողնման համար, որը այստեղ -ն է։

Օրինակ, եթե նմանության մատրիցան տրվում է աղյուսակով.
-AGCT
A10-1-3-4
G-17-5-3
C-3-590
T-4-308
ապա հավասարեցումը։

 AGACTAGTTAC
 CGA‒‒‒GACGT
 բացթողնման համար կունենա հետևյալ գնահատականը։


Ամենաբարձր գնահատականով հավասարում գտնելու համար նշանակվում է երկչափ
մատրիցա F, այնքան տող պարունակող, որքան սիմվոլ կա  հաջորդականության մեջ, և այնքան սյունակներ, որքան սիմվոլ կա  հաջորդականության մեջ։  տողի և  սյունակի գրվածը հետագայում նշանակվում է իբրև ։ Այս կերպ, եթե մենք հավասարեցնում ենք  и  չափերի հաջորդականությունը, ապա պահանջվող հիշողության քանակը կլինի . (Խիշբերգի ալգորիթմը թույլ է տալիս հանել օպտիմալ հավասարումը օգտագործելով  հիշողության քանակը, բայց մոտավորապես կրկնակի շատ հաշվման ժամկետ)։

Ալգորիթմի աշխատանքի գործընթացի ժամանակ  մեծությունը կընդունի օպտիմալ գնահատականի նշանակություն առաջին, հավասարման համար ;n</math> սիմվոլները -ում և առաջին  սիմվոլները . Այդ ժամանակ Բելլմանի օպտիմալության սկզբունքը կարող է կառուցվել հետևյալ կերպ։

Հիմք։




Այս կերպ ալգորիթի կեղծ կոդը 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 մատրիցան հաշվարկված է, նրա  էլեմենտը տալիս է առավելագույն գնահատական բոլոր հնարավոր հավասարումների մեջ։ Հավասարումն հաշվելու համար, որն ստացել է նման գնահատական, պետք է սկսել ներքևի աջ վանդակից և նրանում համեմատել արժեքները, երեք հնարավոր աղյուրների հետ (համապատասխանեցում, դրույք), որպեսզի տեսնենք, թե որտեղից այն։  և  հավասարումների համապատասխանության դեպքում,  դելեցիայի դեպքում հավասարեցված է բացթողնման հետ, իսկ դրույքի դեպքում բացթողնման հետ հավասարեցված է արդեն -ն։ Ընդհանուր դեպքում հնարավոր է ավելի քան մեկ տարբերակ միևնույն նշանակությամբ, ինչը կհանգեցնի այլընտրանքային օպտիմալ հավասարեցումներին։

 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
  }

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



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

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

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

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

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