Molekulyar biologiya fanidan tayyorlagan

2.2 Cheklangan haroratli so'zlarni tekislash

Bizning yondashuvimiz yaqinda ishlab chiqilgan protein-oqsil o'zaro ta'siri (PPI) uchun juft o'xshashlik (PS) [ 40 ] yordamida juda kuchli ekanligi isbotlangan usulga o'xshaydi. PPI-PSda mualliflar X ketma-ketligi uchun xususiyatlarni ajratib olish uchun Smit-Waterman algoritmidan [ 41 ] foydalanganlar . Bunday holda, xususiyat vektorining har bir komponenti siljish oynasi tomonidan yaratilgan t - kichik ketma-ketlikka nisbatan X ketma-ketlikning mahalliy tekislash balli bilan aniqlanadi .

Smit-Waterman algoritmi qidiruv maydonida yuqori o'xshashlikka ega bo'lgan bitta mintaqa kutilgan muammolar uchun javob beradi. Bunday holat rasmda ko'rsatilgan1(a). Kichkina o'zgarishlardan tashqari, har bir siljigan keyingi ketma-ketlikda katta ballga ega bo'lgan bir tekislash ustunlik qiladi. Biroq, bizning holatlarimizda bu ikki sababga ko'ra biz o'lchamoqchi bo'lgan o'xshashlik emas. Birinchidan, birlashtirilgan ma'lumotlar bazasi bo'ylab o'zgaruvchan oynadan foydalanish, X ketma-ketligining dastlabki ma'lumotlar bazasidagi alohida yozuvlarga o'xshashligi tufayli bir oyna ichida bir nechta yuqori ball mintaqalariga olib kelishi mumkin . Ikkinchidan, agar homologiya zaif bo'lsa, X ni ma'lumotlar bazasidagi bitta yozuvga solishtirishda ham deyarli optimal moslashuvlar bo'lishi mumkin . HMMlarda oldinga siljish deb ataladigan ball bunday vaziyatlarni hisobga olishi mumkin [ 42]. Biroq, HMMlar odatda ballga asoslangan tekislashdan ko'ra kattaroq parametrlar to'plamiga tayanadi. Shu sababli, biz klassik ballga asoslangan tekislashni to'g'ridan-to'g'ri umumlashtirish bo'lgan chekli haroratli hizalama bilan tajriba o'tkazdik [ 43 , 44 ].

Optimal hizalama va chekli haroratli hizalama . (a) Qidiruv maydonida bitta juda o'xshash mintaqa (b) Har bir oynadagi qidiruv maydonida raqobatbardosh o'xshash ko'plab mintaqalar. Ushbu doirada biz nafaqat optimal tekislashni, balki X va W t kirish ketma-ketligini mumkin bo'lgan tekislashlarning to'liq to'plamini ko'rib chiqdik . Har bir hizalamaga uning balli va bitta erkin parametr, "harorat" T ga qarab eksponensial og'irlik berildi . Bal odatiy tarzda hisoblab chiqilgan va bo'shliqlar uchun salbiy hissa (bo'shliq ochish uchun -11, kengaytmalar uchun -1) hisobga olingan holda barcha moslashtirilgan pozitsiyalar uchun ball matritsasi (bu erda BLOSUM62) yozuvlarini jamlash yo'li bilan hisoblab chiqilgan. Bunday taqsimot Boltsman taqsimoti deb ataladi. Samarali algoritm normalizatsiya koeffitsientini (yoki bo'lim funktsiyasini ) hisoblash imkonini beradi. Barcha tekislashlarni sanab o'tishga hojat qoldirmasdan (cheklangan o'lchamdagi so'zlarni tekislash uchun ushbu algoritmlarning variantini quyida ko'ring). Statistik fizikadan shartlarni olib. Bu qiymatlar SVM tasniflagichidagi xususiyat vektorlarining komponentlarini tashkil qiladi. Qisqacha aytganda, f quyidagi xususiyatlarga ega:

• T → 0 uchun f optimal ballga teng (optimal barcha vazn berilgan)

• T → ∞ uchun har bir tekislash bir xil vaznga ega.

• Bo'sh ball ketma-ketlik uzunliklari bilan chiziqli (logarifmik o'rniga) o'sadigan muhim TC mavjud [ 39 , 45 - 47 ]. Shuningdek, hizalanish uzunligi uzunligi bilan chegaralanmagan holda o'sadi. Bu shuni anglatadiki , T kontrast parametr sifatida qaralishi mumkin, bu suboptimal tekislashlarda ko'proq yoki kamroq massa qo'yish imkonini beradi. Tc dan yuqori haroratlardan qochish kerak , chunki o'zaro bog'liq va bog'liq bo'lmagan ketma-ketlik juftlarini endi ajratib bo'lmaydi va hizalanishlar ma'nosiz bo'ladi. Biroq, bizning birinchi tajribalarimiz SVM bepul ball bilan birgalikda yaxshi ishlashini ko'rsatdi, ammo biz kutilmagan katta optimal haroratni oldik, hatto T css ≈ 2,5 [ 39 ] dan kattaroq, bu erda SVM tasnifi eng yaxshi ishladi. Buni yaxshiroq tushunish uchun biz tasniflashdan oldin ketma-ketlikni aralashtirdik va deyarli bir xil ko'rsatkichlarga erishdik. Demak, aminokislotalarning to'g'ri kelishi emas, balki ko'proq aminokislotalarning ketma-ketligi kabi eksponentsial omil bilan og'irlikdagi aminokislotalarning tarkibi muhimroqdir. Bu yerda s ball matritsasi va h X ( a ), h W ( b ) ketma-ketlikda a va b aminokislotalarning paydo boʻlish chastotalarini bildiradi .

Ketma-ket tartib effektlari bilan ko'plab muqobil tekislashlarni ko'rib chiqish g'oyasidan voz kechmaslik uchun biz mumkin bo'lgan tekislashlar to'plamini quyidagi tarzda chekladik. O'zboshimchalik bilan uzun tekislashlarga ruxsat berish o'rniga, faqat maksimal uzunlikdagi k max so'z juftlari orasidagi barcha bo'shliqsiz tekislashlar ko'rib chiqildi.

Z T ni polinom vaqtida hisoblaydigan dinamik dasturlash algoritmini shakllantirish to'g'ridan-to'g'ri . Shuning uchun, X 1 ... X i kichik muammosi bo'yicha barcha so'zlar bo'yicha yig'indisi va i va j pozitsiyalarida tugaydigan k uzunlikdagi so'z bo'ladigan tarzda aniqlangan yordamchi bo'linish funktsiyasini belgilaymiz . Bu miqdorlarni rekursiya munosabati orqali hisoblash mumkin. Shuning uchun i = 1 ... | X |, j = 1 ... | W t | va k = 1 ... k max . Jami bo'linish funktsiyasi Z T tomonidan berilgan . Erkin ball T → 0 va T → ∞ uchun cheklovsiz tekislash uchun tegishli chegaralovchi xususiyatlarga ega, ammo T C dan yuqori o'zboshimchalik bilan uzun tekislash imkonsiz bo'ladi.