L. A. Kadirova, A. A. No’monjonov bioinformatika o‘zbekiston Respublikasi vazirligi tomonidan ta’lim yo‘nalishi bo‘yicha darslik sifatida tavsiya etilgan

I
ALEXANDRNIKOLAEVICHOGURTSOV
A -L-E-KSANDROGURTSOV
II
ALEXANDRNIKOLAEVICHOGURTSOV
ALEKSANDR OGURTSOV
III)
ALEXANDRNIKOLAEVICHOGURTSOV
ALEKSANDR --- O -- --- GURTSOV



Nuqta matritsasi boʻylab yuqoridan chapdan oʻngga oʻtuvchi har qanday yoʻl katakchalar ketma-ketligini kesib oʻtadi, ularning har biri bir juft joyni bashorat qiladi, ularning har biri tekislikka mos keladigan satr va ustundan; yoki ketma-ketliklardan biridagi bo'shliqni bildiradi. Yo'l faqat to'ldirilgan pozitsiyalardan o'tishi shart emas. Shu bilan birga, yo'lning diagonal oyog'idagi to'ldirilgan pozitsiyalar qanchalik ko'p bo'lsa, hizalanishda mos keladigan qoldiqlar shunchalik ko'p bo'ladi.
Agar keyingi hujayralar orasidagi harakat yo'nalishi diagonal bo'lsa, u holda ketma-ket taqqoslangan qoldiqlar juftligi ular orasiga qo'shimchasiz (mos keladi) mos keladi.
Harakat yo'nalishi gorizontal bo'lsa, u holda qator ko'rsatkichi bo'lib xizmat qiladigan ketma-ketlikka bo'sh joy qo'shiladi .
Harakat yo'nalishi vertikal (pastga) bo'lsa, u holda ustunlarni indekslaydigan ketma-ketlikka bo'shliq kiritiladi .
qanday harakatni yuqoriga yoki chapga olib bo'lmaydi, chunki bu bir ketma-ketlikning bir nechta qoldiqlarini boshqasining faqat bitta qoldig'i bilan solishtirishga to'g'ri keladi. Yuqorida tavsiflangan nuqta matritsasi yo'lini tanlash usulining matematik talqini tekislash yo'lini grafik sifatida ko'rsatishga asoslangan.
Grafik cho'qqilar (yoki tugunlar) to'plami va tugunlar orasidagi bog'lanishlar to'plami sifatida aniqlanadi, ular qirralar ( yoki yoylar ) deb ataladi.
grafik (yoki qisqacha digraf ) bu (ko'p) grafik bo'lib, uning qirralari yo'nalish bilan belgilanadi.
Digrafdagi marshrut - bu cho'qqilar va yoylarning o'zgaruvchan ketma-ketligi (cho'qqilarni takrorlash mumkin). Marshrut uzunligi - undagi yoylar soni.
Yo'l - digrafdagi yoylar takrorlanmaydigan marshrut; oddiy usul - takrorlanuvchi uchlari yo'q. Agar bir cho'qqidan ikkinchisiga yo'l bo'lsa, ikkinchi cho'qqiga birinchisidan chiqish mumkin .
Uzunligi m va n boʻlgan ikkita ketma-ketlikni koʻrib chiqaylik.Bu ketma-ketliklarning tekislanishi ( m D 1) □ ( n □ ) oʻlchamdagi ( ij, ) (0 □ □ im, 0D j □ n ) tugunlari boʻlgan G yoʻnaltirilgan grafikdir. 1). Grafik chekkasi (ij, ) dan tugunga (i jU, □ ) faqat 0D iQQ D i 1 va 0D/□□ j □ 1 bo’lgandagina mumkin.
3.12-rasmda vertikal, gorizontal va diagonal qirralar mavjud bo'lgan X = gtccgtg va Y = atactgg ketma-ketliklari uchun tekislash grafigi ko'rsatilgan.

3.12-rasm. gtccgtg va atactgg ning ketma-ketlikni tekislash grafigi

Yo'naltirilgan grafikda grafikning oxiri (yoki cho'kmasi) barcha qo'shni qirralarning yo'naltirilgan tugunidir va grafikning (yoki manbaning) boshi barcha qo'shni qirralarning yo'naltirilgan tugunidir. Global hizalama grafigida yagona kelib chiqish (manba) tugun (0,0) va tekislash grafigining yagona uchi (cho'kish) tugun (mn,) hisoblanadi.

Hizalama grafigida qalin strelkalar bilan belgilangan yo'l (3.12-rasm) quyidagicha ifodalanishi mumkin .
(0,1)D(1,1)D(2,2)D(3,3)D(4,4)D(5,4)D(6,5)D(6,6)D (7 ,7), bu yerda s bosh (0,0). Tegishli hizalama o'xshash bo'ladi
-gtccgt-g
a-tac-tgg
Matritsali yo'lni sharhlashning yana bir usuli - tahrirlash tartibi (tahrirlash skripti). U ustunlarni indekslash ketma-ketligini - gorizontal ketma-ketlikni (jadval tepasida) - satrlarni indekslash ketma-ketligiga - vertikal ravishda joylashtirilgan ketma-ketlikka (jadvalning chap tomonida) aylantiradigan bir qator operatsiyalarning ko'rsatkichidir.
Har bir harakat bizga operatsiyalardan biri - almashtirish, kiritish yoki o'chirish (o'chirish) haqida gapirib beradi. Yo'lning oxiriga yetganda, bir ketma-ketlikning boshqasiga o'zgarishi olinadi.
Umuman olganda, bir necha xil tahrirlash ketma-ketligi bir xil miqdordagi qadamlarda bir ketma-ketlikni boshqasiga aylantirishi mumkin, ammo ular turli xil tekislashlarga mos kelishi mumkin.
Turli xil tekislash variantlari natijalarini miqdoriy jihatdan solishtirish uchun ma'lum bir reyting sxemasi tahrirlash operatsiyalari bilan bog'liq. Ushbu sxemalar juda oddiy bo'lishi mumkin, masalan, har bir mos keladigan belgilar juftligi uchun (+1 ball) (almashtirish) va mos kelmaslik uchun jarima (-1 ball).
Jazolar qat'iy, mutanosib va chiziqli bo'lishi mumkin, ular bo'shliqni kiritish uchun jazo va bo'shliqni davom ettirganlik uchun qo'shimcha jazodan iborat.
Baholash sxemalari juda xilma-xildir, lekin har qanday holatda, har bir hizalanish ba'zi umumiy ball ( og'irlik yoki ball) bilan bog'lanishi mumkin, bu sizga tekislangan ketma-ketliklarning o'xshashligini miqdoriy baholash imkonini beradi .
Albatta, biologik molekulaning evolyutsiya tarixi, fazoviy tuzilishi, biologik funksiyasi va “o‘zboshimchalik”ni cheklovchi boshqa xususiyatlarni hisobga olgan holda, biologik jihatdan to‘g‘ri moslashishga yuqori ball qo‘yadigan ball sxemasiga ega bo‘lish maqsadga muvofiqdir. ketma-ket o'zgarishi. Shuning uchun, tekislash algoritmlariga qo'shimcha ravishda, reyting tizimini yaratish usullarini ham puxta o'ylab ko'rish kerak, natijada ular juda murakkab va ko'p omilli bo'lishi mumkin.
Optimal moslashtirish eng yuqori ball, eng ko'p o'yinlar soni va eng kam farqlarga ega bo'lgan moslama hisoblanadi. Suboptimal tekislash - bu eng yuqori ball optimal darajadan past bo'lgan shartli optimal tekislash.
Optimal tekislash bilan bir xil bo'lmagan belgilar va bo'shliqlar tekislash ustunlarida iloji boricha ko'proq bir xil yoki o'xshash belgilar bo'lishi uchun joylashtiriladi.
Optimal hizalamalar ketma-ketlik belgilarining qaysi biri bir xil tekislash ustunlarida bo'lishi va qaysi biri ketma-ketliklarning biriga qo'shilishi (yoki mos ravishda boshqasida tushish) bo'lishi haqida eng yaxshi ma'lumotni taqdim etish orqali ketma-ketliklarning evolyutsion munosabatlarini ochishga imkon beradi . Ushbu ma'lumotlar ketma-ketliklarning funktsiyalari, tuzilmalari va evolyutsion munosabatlarini ularning hizalanishidan bashorat qilish uchun kerak.
Shuni ta'kidlash kerakki, tahrirlash operatsiyalari ketma-ketligi optimal tekislashdan olingan bo'lsa-da va u haqiqiy evolyutsiya yo'liga mos kelishi mumkin bo'lsa-da , bu haqiqatan ham shunday ekanligini isbotlash mumkin emas . "Muharrir masofasi" qanchalik katta bo'lsa, ikkita ketma-ketlik orasidagi evolyutsiya yo'llari shunchalik oqilona.
3.13-rasmda papayyadan olingan bir xil protein (PAPA_CARPA) sulfgidril proteinaz papainning nuqta matritsali taqqoslashlari ko'rsatilgan, ular orasidagi masofa ortib borayotgan to'rtta gomolog:
yaqin qarindoshi bilan, kivi mevasi aktinidin (ACT N_ACTCH, 3.13 (a)-rasm);
uzoqroq qarindoshlar bilan - inson protethepsin L (CATL_HUMAN, 13-rasm (b));
inson katepsin B bilan (CATB_HUMAN, 3.13(c)-rasm);
Staphylococcus aureus dan stafopain bilan (STPA_STAAU, 3.13 (d)-rasm).

Рисунок 3.13 - Точечные матрицы выравнивания белка сульфгидрильного протеиназного папаина из папайи с родственными белками

Ketma-ketliklar asta-sekin farq qilganda, nuqta matritsasidan to'g'ri hizalanishni taxmin qilish tobora qiyinlashadi va biologik jihatdan mazmunli moslashish uchun oqsil tuzilmalari haqida qo'shimcha ma'lumotlar keltirilishi kerak .