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

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


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

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

AGACTAGTTAC
CGA‒‒‒GACGT

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

  
    
      
        S
        (
        A
        ,
        
        C
        )
        +
        S
        (
        G
        ,
        
        G
        )
        +
        S
        (
        A
        ,
        
        A
        )
        +
        3
        ×
        d
        +
        S
        (
        G
        ,
        
        G
        )
        +
        S
        (
        T
        ,
        
        A
        )
        +
        S
        (
        T
        ,
        
        C
        )
        +
        S
        (
        A
        ,
        
        G
        )
        +
        S
        (
        C
        ,
        
        T
        )
      
    
    {\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)}
  

  
    
      
        =
        −
        3
        +
        7
        +
        10
        −
        (
        3
        ×
        5
        )
        +
        7
        +
        (
        −
        4
        )
        +
        0
        +
        (
        −
        1
        )
        +
        0
        =
        1.
      
    
    {\displaystyle =-3+7+10-(3\times 5)+7+(-4)+0+(-1)+0=1.}
  Ամենաբարձր գնահատականով հավասարում գտնելու համար նշանակվում է երկչափ
մատրիցա F, այնքան տող պարունակող, որքան սիմվոլ կա 
  
    
      
        A
      
    
    {\displaystyle A}
   հաջորդականության մեջ, և այնքան սյունակներ, որքան սիմվոլ կա 
  
    
      
        B
      
    
    {\displaystyle B}
   հաջորդականության մեջ։ 
  
    
      
        i
      
    
    {\displaystyle i}
   տողի և 
  
    
      
        j
      
    
    {\displaystyle j}
   սյունակի գրվածը հետագայում նշանակվում է իբրև 
  
    
      
        
          F
          
            i
            j
          
        
      
    
    {\displaystyle F_{ij}}
  ։ Այս կերպ, եթե մենք հավասարեցնում ենք 
  
    
      
        n
      
    
    {\displaystyle n}
   и 
  
    
      
        m
      
    
    {\displaystyle m}
   չափերի հաջորդականությունը, ապա պահանջվող հիշողության քանակը կլինի 
  
    
      
        O
        (
        n
        m
        )
      
    
    {\displaystyle O(nm)}
  . (Խիշբերգի ալգորիթմը թույլ է տալիս հանել օպտիմալ հավասարումը օգտագործելով 
  
    
      
        O
        (
        n
        +
        m
        )
      
    
    {\displaystyle O(n+m)}
   հիշողության քանակը, բայց մոտավորապես կրկնակի շատ հաշվման ժամկետ)։
Ալգորիթմի աշխատանքի գործընթացի ժամանակ 
  
    
      
        
          F
          
            i
            j
          
        
      
    
    {\displaystyle F_{ij}}
   մեծությունը կընդունի օպտիմալ գնահատականի նշանակություն առաջին, հավասարման համար ;n</math> սիմվոլները 
  
    
      
        A
      
    
    {\displaystyle A}
  -ում և առաջին 
  
    
      
        j
        =
        0
        ,
        
        …
        ,
        
        m
      
    
    {\displaystyle j=0,\;\ldots ,\;m}
   սիմվոլները 
  
    
      
        B
      
    
    {\displaystyle B}
  . Այդ ժամանակ Բելլմանի օպտիմալության սկզբունքը կարող է կառուցվել հետևյալ կերպ։
Հիմք։

  
    
      
        
          F
          
            0
            j
          
        
        =
        d
        ⋅
        j
      
    
    {\displaystyle F_{0j}=d\cdot j}
  

  
    
      
        
          F
          
            i
            0
          
        
        =
        d
        ⋅
        i
      
    
    {\displaystyle F_{i0}=d\cdot i}
  

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


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

  
    
      
        
          F
          
            i
            j
          
        
        =
        
          max
          
            h
            <
            i
            ,
            
            k
            <
            j
          
        
        {
        
          F
          
            h
            ,
            
            j
            −
            1
          
        
        +
        S
        (
        
          A
          
            i
          
        
        ,
        
        
          B
          
            j
          
        
        )
        ,
        
        
          F
          
            i
            −
            i
            ,
            
            k
          
        
        +
        S
        (
        
          A
          
            i
          
        
        ,
        
        
          B
          
            j
          
        
        )
        }
        .
      
    
    {\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 թվականին(տողերի համեմատում)։
Նիդլմանը և Վունշը ձևավորեցին իրենց խնդիրը տերմինների առավելագույն նմանությամբ։ Մյուս հնարավորությունը կայանում է տարածություն հերթականության խմբագրումը, առաջադրված Լևենշտեյնի կողմից և ցույց է տրված, որ այս երկու խնդիրները երկվալենտ են։,


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