Mundarija: Kirish I bob. Biologik ketma – ketliklar

Ketma-ketlikni moslashtirish muammolari
n-belgilar ketma-ketligi s va m-belgilar ketma-ketligi t uchun (n+1)?(m+1) matritsa tuzamiz.
Global tekislash: F ( i, j ) = s[1…i ] ning t[1…j] bilan eng yaxshi moslashuvi balli
Mahalliy tekislash: F ( i, j ) = s[1…i ] qo‘shimchasi va t[1…j] qo‘shimchasining eng yaxshi moslashuvi balli
Ketma-ket tekislash algoritmlarida uchta bosqich mavjud:
Initsializatsiya bosqichida biz hizalama matritsasining birinchi qatori va ustuni uchun qiymatlarni belgilaymiz. Algoritmning keyingi bosqichi bunga bog'liq.
To'ldirish bosqichida butun matritsa yuqoridan pastga, chapdan o'ngga bo'shliq jazolari va ball matritsasiga bog'liq bo'lgan tegishli qiymatlar bilan ballar bilan to'ldiriladi.
Har bir F ( i, j ) uchun ko‘rsatkichlarni eng yaxshi natijaga erishgan hujayraga saqlang. Global tekislash uchun biz ketma-ketlikni tiklash uchun ko'rsatgichlarni F (m, n) dan F(0, 0) gacha kuzatamiz. Mahalliy tekislash uchun biz matritsaning istalgan joyida bo'lishi mumkin bo'lgan F (i, j) ning maksimal qiymatini qidiramiz. Biz F (i, j) dan ko'rsatkichlarni kuzatamiz va qiymati 0 bo'lgan katakchaga kelganimizda to'xtab qolamiz.
Skor matritsasi bilan mahalliy moslashtirish
Tegishli matritsani ( F ) va orqaga qaytish matritsasini yaratgandan va ishga tushirgandan so'ng, har bir katak uchun F (i, j) balli quyidagicha hisoblanadi:
diagonal_score=F[i-1[ j-1] + PAM250(s[i], t[j]),
ball=maksimal[ 0, chap_skor, diagonal_skor, yuqori_skor]
Bundan tashqari, orqaga qaytishni amalga oshirish uchun har bir hujayraga havolani saqlashimiz kerak.
F matritsasini to'ldirgandan so'ng, biz eng yuqori ball bo'lgan maxi,jF(i, j) katakchasini topib, optimal tekislash ballini va optimal yakuniy nuqtalarni topamiz. best_score standart qiymati -1 ga teng.
i_maximum_score, j_maximum_score = i, j
Optimal moslashuvni tiklash uchun biz i_maximum_score, j_maximum_score pozitsiyasidan orqaga qarab, 0 ballga ega bo'lgan katakka yetib kelganimizda orqaga qaytishni tugatamiz.
Bu algoritmning vaqt va makon murakkabligi O(mn) dir, bu m s ketma-ketlikning uzunligi, n esa t ketma-ketlikning uzunligi.
Affin bo'shliq jazosi bilan mahalliy moslashish
Ushbu muammo uchun bo'shliqni ochish jazosi va bo'shliqni uzaytirish jazosi mavjud. Bo'shliqni ochish jazosi bo'shliqning boshida qo'llaniladi, so'ngra undan keyingi boshqa bo'shliq bo'shliqni uzaytirish jazosi bilan beriladi.
To'rt xil matritsa mavjud: yuqoriga_skor , chap_skor , m_skor , trace_back