Hirschbergs algoritmi - Hirschbergs algorithm - Wikipedia

Yilda Kompyuter fanlari, Xirshberg algoritmi, ixtirochisi nomi bilan, Dan Xirshberg, a dinamik dasturlash algoritm bu eng maqbul topadi ketma-ketlikni tekislash ikkitasi o'rtasida torlar. Optimallik. Bilan o'lchanadi Levenshteyn masofasi, bir qatorni ikkinchisiga almashtirish uchun zarur bo'lgan qo'shish, almashtirish, o'chirish va bekor harakatlar qiymati yig'indisi sifatida belgilangan. Hirschberg algoritmi shunchaki kosmik tejamkor versiyasi sifatida tavsiflanadi Needleman - Wunsch algoritmi ishlatadigan bo'ling va zabt eting.^[1] Hirschberg algoritmi odatda ishlatiladi hisoblash biologiyasi ning maksimal global hizalanmalarini topish uchun DNK va oqsil ketma-ketliklar.

Algoritm haqida ma'lumot

Hirschberg algoritmi - ketma-ketlikni optimal ravishda tekislash uchun odatda qo'llaniladigan algoritm. Portlash va FASTA suboptimaldir evristika. Agar x va y bu satrlar, bu erda uzunlik (x) = n va uzunlik (y) = m, Needleman-Wunsch algoritmi ichida optimal hizalamayı topadi O (nm) vaqtidan foydalanib, O (nm) bo'sh joy. Hirschberg algoritmi - bu hali ham O (Need) -Vunsh algoritmini mohirona o'zgartirgan (nm) vaqt, lekin faqat O (min {) kerakn,m}) bo'shliq va amalda ancha tezroq.^[2]Algoritmning qo'llanilishlaridan biri bu DNK yoki oqsil sekanslarining ketma-ket hizalanmalarini topishdir. Bu shuningdek hisoblash uchun kosmik jihatdan samarali usuldir eng uzun umumiy ketma-ketlik umumiy kabi ma'lumotlar to'plami o'rtasida farq vosita.

Hirschberg algoritmini quyidagilarni kuzatish orqali Needleman-Wunsch algoritmidan olish mumkin:^[3]

1. faqat Needleman-Wunsch skrining matritsasining joriy va oldingi qatorini saqlash orqali tekislashning optimal ko'rsatkichini hisoblash mumkin;
2. agar ${ displaystyle (Z, W) = operatorname {NW} (X, Y)}$ ning optimal hizalamasidir ${ displaystyle (X, Y)}$va ${ displaystyle X = X ^ {l} + X ^ {r}}$ ning o'zboshimchalik bilan bo'linishi ${ displaystyle X}$, bo'lim mavjud ${ displaystyle Y ^ {l} + Y ^ {r}}$ ning ${ displaystyle Y}$ shu kabi ${ displaystyle operator nomi {NW} (X, Y) = operator nomi {NW} (X ^ {l}, Y ^ {l}) + operator nomi {NW} (X ^ {r}, Y ^ {r} )}$.

Algoritm tavsifi

${ displaystyle X_ {i}}$ ning i-belgisini bildiradi ${ displaystyle X}$, qayerda ${ displaystyle 1 leqslant i leqslant operator nomi {uzunlik} (X)}$. ${ displaystyle X_ {i: j}}$ o'lchamdagi pastki qatorni bildiradi ${ displaystyle j-i + 1}$, i-dan j-chi belgigacha o'zgarib turadi ${ displaystyle X}$. ${ displaystyle operatorname {rev} (X)}$ ning teskari versiyasidir ${ displaystyle X}$.

${ displaystyle X}$ va ${ displaystyle Y}$ hizalanadigan ketma-ketliklardir. Ruxsat bering ${ displaystyle x}$ belgi bo'lishi ${ displaystyle X}$va ${ displaystyle y}$ belgi bo'lishi ${ displaystyle Y}$. Biz buni taxmin qilamiz ${ displaystyle operatorname {Del} (x)}$, ${ displaystyle operator nomi {Ins} (y)}$ va ${ displaystyle operatorname {Sub} (x, y)}$ aniq belgilangan butun sonli funktsiyalar. Ushbu funktsiyalar o'chirish narxini anglatadi ${ displaystyle x}$, kiritish ${ displaystyle y}$va almashtirish ${ displaystyle x}$ bilan ${ displaystyle y}$navbati bilan.

Biz aniqlaymiz ${ displaystyle operatorname {NWScore} (X, Y)}$, bu Needleman-Wunsch ball matritsasining so'nggi qatorini qaytaradi ${ displaystyle mathrm {Skor} (i, j)}$:

funktsiya NWScore (X, Y) Skor (0,0) = 0 // 2 * (uzunlik (Y) + 1) qator uchun j = 1 ga uzunlik (Y) Skor (0, j) = Skor (0, j - 1) + Ins (Yj)    uchun i = 1 ga length (X) // Init array Score (1,0) = Score (0, 0) + Del (Xmen)        uchun j = 1 ga uzunlik (Y) ballSub = Skor (0, j - 1) + Sub (Xmen, Yj) scoreDel = Skor (0, j) + Del (Xmen) scoreIns = Skor (1, j - 1) + Ins (Yj) Skor (1, j) = max (scoreSub, scoreDel, scoreIns) oxiri        // Skorni [1] Skorga nusxalash [0] Skor (0, :) = Skor (1, :) oxiri    uchun j = 0 ga uzunlik (Y) LastLine (j) = Skor (1, j) qaytish LastLine

E'tibor bering, har qanday vaqtda, ${ displaystyle operatorname {NWScore}}$ faqat ball matritsasining eng so'nggi ikki qatorini talab qiladi. Shunday qilib, ${ displaystyle operatorname {NWScore}}$ amalga oshiriladi ${ displaystyle O ( operatorname {min} { operatorname {length} (X), operatorname {length} (Y) })}$ bo'sh joy

Hirschberg algoritmi quyidagicha:

funktsiya Hirschberg (X, Y) Z = "" W = "" agar uzunlik (X) == 0 uchun i = 1 ga uzunlik (Y) Z = Z + '-' W = W + Ymen        oxiri    boshqa bo'lsa uzunlik (Y) == 0 uchun i = 1 ga uzunlik (X) Z = Z + Xmen            W = W + '-' oxiri    boshqa bo'lsa uzunlik (X) == 1 yoki uzunlik (Y) == 1 (Z, V) = NeedlemanWunsch (X, Y) boshqa        xlen = uzunlik (X) xmid = uzunlik (X) / 2 ylen = uzunlik (Y) Skor L = NWScore (X)1: xmid, Y) ScoreR = NWScore (rev (Xxmid + 1: xlen), rev (Y)) ymid = arg max ScoreL + rev (ScoreR) (Z, W) = Xirshberg (X1: xmid, y1: ymid) + Xirshberg (Xxmid + 1: xlen, Yymid + 1: ylen)    oxiri    qaytish (Z, V)

Kuzatish (2) kontekstida, deb taxmin qiling ${ displaystyle X ^ {l} + X ^ {r}}$ ning bo'limi ${ displaystyle X}$. Indeks ${ displaystyle mathrm {ymid}}$ shunday hisoblangan ${ displaystyle Y ^ {l} = Y_ {1: mathrm {ymid}}}$ va ${ displaystyle Y ^ {r} = Y _ { mathrm {ymid} +1: operatorname {length} (Y)}}$.

Misol

Ruxsat bering

${ displaystyle { begin {aligned} X & = mathrm {AGTACGCA}, Y & = mathrm {TATGC}, operatorname {Del} (x) & = - 2, operatorname {Ins} ( y) & = - 2, operator nomi {Sub} (x, y) & = { start {case} +2, & { mbox {if}} x = y - 1, & { mbox {if}} x neq y. end {case}}} end {hizalangan}}}$

Optimal hizalama tomonidan berilgan

 V = AGTACGCA Z = --TATGC-

Haqiqatan ham, buni tegishli Needleman-Wunsch matritsasini orqaga qaytarish orqali tekshirish mumkin:

         T A T G C     0  -2  -4  -6  -8 -10 A  -2  -1   0  -2  -4  -6 G  -4  -3  -2  -1   0  -2 T  -6  -2  -4   0  -2  -1 A  -8  -4   0  -2  -1  -3 C -10  -6  -2  -1  -3   1 G -12  -8  -4  -3   1  -1 C -14 -10  -6  -5  -1   3 A -16 -12  -8  -7  -3   1

Bittasi yuqori darajadagi qo'ng'iroqdan boshlanadi ${ displaystyle operatorname {Hirschberg} ( mathrm {AGTACGCA}, mathrm {TATGC})}$, bu birinchi argumentni ikkiga bo'linadi: ${ displaystyle X = mathrm {AGTA} + mathrm {CGCA}}$. Qo'ng'iroq ${ displaystyle operatorname {NWScore} ( mathrm {AGTA}, Y)}$ quyidagi matritsani ishlab chiqaradi:

        T A T G C    0  -2  -4  -6  -8 -10 A -2  -1   0  -2  -4  -6 G -4  -3  -2  -1   0  -2 T -6  -2  -4   0  -2  -1 A -8  -4   0  -2  -1  -3

Xuddi shunday, ${ displaystyle operator nomi {NWScore} ( operator nomi {rev} ( mathrm {CGCA}), operator nomi {rev} (Y))}$ quyidagi matritsani hosil qiladi:

       C G T A T    0 -2  -4  -6  -8 -10 A -2 -1  -3  -5  -4  -6 C -4  0  -2  -4  -6  -5 G -6 -2   2   0  -2  -4 C -8 -4   0   1  -1  -3

Ularning oxirgi satrlari (ikkinchisini qaytargandan so'ng) va ularning yig'indisi mos ravishda

 ScoreL = [-8 -4 0 -2 -1 -3] rev (ScoreR) = [-3 -1 1 0 -4 -8] Sum = [-11 -5 1 -2 -5 -11]

Maksimal (qalin harf bilan ko'rsatilgan) da paydo bo'ladi {{{1}}}, bo'limni ishlab chiqarish ${ displaystyle Y = mathrm {TA} + mathrm {TGC}}$.

Hirschbergning butun rekursiyasi (biz uni qisqartirish uchun qoldiramiz) quyidagi daraxtni hosil qiladi:

               (AGTACGCA, TATGC) /  (AGTA, TA) (CGCA, TGC) /  /  (AG,) (TA, TA) (CG, TG) (CA, C) /  /  (T, T)) A, A) (C, T) (G, G) 

Daraxtning barglari optimal tekislashni o'z ichiga oladi.

Shuningdek qarang

• Eng uzun umumiy oqibat

Adabiyotlar