Mundarija: Kirish I bob. Biologik ketma – ketliklar

Amaliy matematika bo'yicha SIAM jurnali
Cheklangan alifbodagi belgilar ketma-ketligini o'rganish va taqqoslash fanning turli sohalari, xususan molekulyar biologiya uchun dolzarbdir. Ketma-ketlik o'xshashligini o'lchash ketma-ketliklar orasidagi "masofa" minimal bo'lgan optimalni topish uchun turli xil mumkin bo'lgan ketma-ketliklarni ko'rib chiqishni o'z ichiga oladi. Panjaradagi yo'lni har bir tekislash bilan bog'lash orqali optimal tekislashni topish muammosiga geometrik tushuncha keltirilishi mumkin. Keyinchalik bu muammoni dinamik dasturlash algoritmini qo'llash orqali hal qilish mumkin. Biroq, hisoblash harakatlari raqam bilan tez o'sib boradi N taqqoslanadigan ketma-ketliklar $(O(l^N ))$, bu yyerda l - taqqoslanadigan ketma-ketliklarning o'rtacha uzunligi).
Bu yerda isbotlanganki, o'zboshimchalik bilan tanlangan tekislashning o'lchovi haqidagi bilimlar ko'rib chiqilayotgan panjara mintaqasining o'lchamini sezilarli darajada cheklash uchun juft tekislashlar ma'lumotlari bilan birgalikda ishlatilishi mumkin. Bu qisqartirish dinamik dasturlashni optimallashtirish jarayonini amalga oshirish uchun kamroq hisob-kitoblarni va kamroq xotira maydonini talab qiladi. Kuzatishlar, shuningdek, bir nechta hizalama muammosining yangi variantlarini taklif qiladi.
Ketma-ketlikni tekislash/tahlil qilish uchun cheklash dasturlashni qo'llash - Biologiya
Ikki DNK qatorining optimal ketma-ketligini hisoblash dasturini yozing. Ushbu dastur sizni soha bilan tanishtiradi hisoblash biologiyasi unda kompyuterlar biologik tizimlar bo'yicha tadqiqotlar olib borish uchun ishlatiladi. Bundan tashqari, siz deb nomlanuvchi kuchli algoritmik dizayn paradigmasi bilan tanishasiz dinamik dasturlash.
Biologiya sharhi. A genetik ketma-ketlik toʻrt harfli alifbodan tuzilgan qatordir DNK asoslari deb ataladigan biologik makromolekulalar. A gen oqsilni yaratish uchun zarur bo'lgan ma'lumotlarni o'z ichiga olgan genetik ketma-ketlikdir. Birgalikda olingan barcha genlaringiz inson genomi deb ataladi, bu sizning hujayralarni hosil qiluvchi oqsillarni yaratish uchun zarur bo'lgan qismlarning rejasi. Tanangiz tomonidan ishlab chiqarilgan har bir yangi hujayra genomning nusxasini oladi. Ushbu nusxa ko'chirish jarayoni, shuningdek, tabiiy eskirish, ko'plab genlarning ketma-ketligiga ozgina o'zgarishlar kiritadi. Eng keng tarqalgan o'zgarishlar qatoriga bir bazani boshqasiga almashtirish va asoslar qatorini o'chirish kiradi, bunday o'zgarishlar odatda shunday deyiladi. nuqta mutatsiyalari. Ushbu nuqta mutatsiyalari natijasida bir-biriga yaqin bo'lgan organizmlardan olingan bir xil gen kichik farqlarga ega bo'ladi.
Ushbu gen kodlaydigan oqsil qanday vazifani bajaradi? Ushbu gen qanday rol o'ynashini aniqlash uchun laboratoriyada bir qator ma'lumotsiz tajribalarni boshlashingiz mumkin. Biroq, u ilgari o'rganilgan organizmdagi ma'lum genning varianti bo'lishi uchun yaxshi imkoniyat mavjud. Biologlar va kompyuter olimlari ko'plab organizmlarning (shu jumladan odamlarning) genetik ketma-ketligini mashaqqatli tarzda aniqlagan (va nashr etgan) bo'lgani uchun, siz ushbu ma'lumotdan o'z manfaatingiz uchun foydalanmoqchisiz. Biz yuqoridagi genetik ketma-ketlikni allaqachon ketma-ketlashtirilgan va funktsiyasi yaxshi tushunilgan bilan solishtiramiz.