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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

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

ժամանակակից պատկերացում[խմբագրել | խմբագրել կոդը]

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

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

- 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

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

Ամենաբարձր գնահատականով հավասարում գտնելու համար նշանակվում է երկչափ մատրիցա 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 թվականին(տողերի համեմատում)։

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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Needleman, Saul B.; and Wunsch, Christian D. (1970)։ «A general method applicable to the search for similarities in the amino acid sequence of two proteins»։ Journal of Molecular Biology 48 (3): 443–53։ doi:10.1016/0022-2836(70)90057-4։ PMID 5420325 
  2. Sellers, P. H. (1974)։ «On the theory and computation of evolutionary distances»։ SIAM Journal on Applied Mathematics 26 (4): 787–793