Mundarija: Kirish I bob. Biologik ketma – ketliklar

Tahrirlash-masofa. Ushbu topshiriqda biz ikkita genetik ketma-ketlikning o'xshashligini ular bilan o'lchaymiz masofani tahrirlash, birinchi marta kodlash nazariyasi kontekstida kiritilgan, ammo hozirda imloni tekshirish, nutqni aniqlash, plagiatni aniqlash, fayllarni qayta ko'rib chiqish va hisoblash lingvistikasida keng qo'llaniladigan tushuncha. Biz ikkita ketma-ketlikni tenglashtiramiz, lekin bizga ruxsat berilgan bo'shliqlarni kiriting ikkala ketma-ketlikda (masalan, ularni bir xil uzunlikka ega qilish uchun). Biz kiritgan har bir bo'shliq uchun, shuningdek, yakuniy hizalamada mos kelmaydigan har bir juft belgilar uchun jarima to'laymiz. Intuitiv ravishda, bu jazolar o'chirish/qo'shish va almashtirish natijasida yuzaga keladigan nuqta mutatsiyalarining nisbiy ehtimolini modellashtiradi. Biz biologik ilovalarda keng qo'llaniladigan quyidagi jadvalga muvofiq raqamli ball ishlab chiqaramiz:

operatsiya	xarajat
bo'shliqni kiriting	2
mos kelmaydigan ikkita belgini tekislang	1
mos keladigan ikkita belgini tekislang	0

Bu yerda satrlarning ikkita mumkin bo'lgan tekislashlari mavjud x = "AACAGTTACC" va y = "TAAGGTCA":
Birinchi hizalama 8 ballga ega, ikkinchisi esa 7 ballga ega tahrirlash masofasi barcha mumkin bo'lgan moslashuvlar bo'yicha ikkita genetik ketma-ketlik o'rtasidagi eng yaxshi moslashuv ballidir. Bu misolda ikkinchi tekislash aslida optimal, shuning uchun ikki satr orasidagi tahrirlash masofasi 7 ga teng. Tahrirlash masofasini hisoblash noaniq hisoblash muammosidir, chunki biz eksponensial jihatdan ko'p imkoniyatlar orasidan eng yaxshi moslashishni topishimiz kerak. Misol uchun, agar ikkala satr uzunligi 100 ta belgidan iborat bo'lsa, unda 10^75 dan ortiq mumkin bo'lgan tekislashlar mavjud.