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

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

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

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

AGACTAGTTACCGA‒‒‒GACGT

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

${\displaystyle 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)}$

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

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

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

Հիմք։

${\displaystyle F_{0j}=d\cdot j}$ ${\displaystyle F_{i0}=d\cdot i}$ ${\displaystyle 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*ifor j=0 to length(B)F(0, j) ← d*jfor 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) + dInsert ← F(i, j-1) + dF(i, j) ← max(Match, Insert, Delete)}

Երբ F մատրիցան հաշվարկված է, նրա ${\displaystyle F_{ij}}$ էլեմենտը տալիս է առավելագույն գնահատական բոլոր հնարավոր հավասարումների մեջ։ Հավասարումն հաշվելու համար, որն ստացել է նման գնահատական, պետք է սկսել ներքևի աջ վանդակից և նրանում համեմատել արժեքները, երեք հնարավոր աղյուրների հետ (համապատասխանեցում, դրույք), որպեսզի տեսնենք, թե որտեղից այն։ ${\displaystyle A_{i}}$ և ${\displaystyle B_{j}}$ հավասարումների համապատասխանության դեպքում, ${\displaystyle A_{i}}$ դելեցիայի դեպքում հավասարեցված է բացթողնման հետ, իսկ դրույքի դեպքում բացթողնման հետ հավասարեցված է արդեն ${\displaystyle 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 + AlignmentAAlignmentB ← "-" + AlignmentBi ← i - 1 } while (j > 0) {AlignmentA ← "-" + AlignmentAAlignmentB ← Bj + AlignmentBj ← j - 1 }

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

${\displaystyle 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 թվականին(տողերի համեմատում)։

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