O’zbekiston respublikasi

Landau-Vishkin algoritmining modifikatsiyasi
Ikki satrning optimal moslashuvining vaqt va xotira murakkabligi kvadratik bo'lib, uzunroq satrlar uchun juda uzoq bajarilish vaqtiga olib keladi. Biroq, bizda ko'pincha satrlar o'xshash va ular orasidagi farq qancha bo'lishini oldindan cheklashi mumkinligi haqida ma'lumotga egamiz. Bunday holda, biz tekislash matritsasida faqat asosiy diagonalni va ma'lum miqdordagi qo'shnilarni hisoblaydigan algoritmlardan foydalanamiz. Bunday eng tezkor algoritmlardan biri "Nukleotidlar va aminokislotalar ketma-ketligi uchun k farqli samarali string mos algoritmi" maqolasida tasvirlangan

Taxminan satrlarni moslashtirish ko'pchilik uchun muhim muammodir

Informatika bilan bog'liq sohalar, shu jumladan biologik ketma-ketlikni qayta ishlash. Bu muammoning standart yechimi O(mn) ish vaqti va m va uzunlikdagi ikkita satr uchun kosmik dinamik dasturlash algoritmi n. Landau va Vishkin qo'shimcha daraxtlardan foydalanadigan algoritmni ishlab chiqdilar dinamik dasturlash jadvali bo'yicha hisoblashni tezlashtirish uchun va O(nk) da fazoga erishish va ish vaqti, bu erda n > m va k ruxsat etilgan farqlarning maksimal soni. Suffiks daraxtlari ketma-ketlikni oldindan qayta ishlash uchun ishlatiladi, bu esa O (1) ish vaqtini hisoblash imkonini beradi. Pastki satrlar orasidagi eng uzun kengaytmalar. Amaliylardan biri Landau-Vishkin algoritmining kamchiliklari bo'sh joydan ortiqcha foydalanishdir qo'shimcha daraxtlardan foydalanishga xosdir. Darhaqiqat, qo'shimcha daraxtlar bo'lishi mumkin bo'lsa-da chiziqli makonda ishlov berilganda, ularning qurilishi va manipulyatsiyasi yuqori darajada bo'lishini nazarda tutadi bu chiziqli xatti-harakatlarga ko'paytiruvchi omillarning bir variantini taqdim etamiz Landau-Vishkin algoritmi, qo'shimcha daraxtlar o'rniga qo'shimchali massivlardan foydalanadi. eng uzun keng tarqalgan kengaytmalarni hisoblash uchun, shu bilan haqiqiyni yaxshilaydi kosmik foydalanish.
Abstrakt
Motivatsiyaning taxminiy satrini moslashtirish kompyuter fanlari sohasidagi asosiy muammodir. U ko'plab string algoritmlari uchun ajralmas komponent bo'lib xizmat qiladi, eng muhimi, DNKni o'qish xaritalash va tekislash. Takomillashtirilgan LV algoritmi tarmoqli Smit-Waterman algoritmiga nisbatan takomillashtirilgan dinamik dasturlash strategiyasini taklif qiladi, ammo ball sxemalarining cheklangan tanlovini qo'llab-quvvatlashdan aziyat chekadi. Ushbu maqolada biz sakrab yuruvchi qurbaqa muammosini, taxminiy satrlarni moslashtirish masalasini umumlashtirishni, shuning-dek, LEAPni, skorlama sxemalarining kengroq tanlovi ostida sakrab yuruvchi qurbaqa muammosini hal qiladigan Landau-Vishkin algoritmining umumlash-tirilishini taklif qilamiz.
Ushbu hujjat quyidagi hissa qo'shadi:
U sakrab yuruvchi qurbaqa muammosini taklif qiladi, ya'ni ijobiy penalti ballari bilan barcha tarmoqli global yoki yarim global taxminiy simlarni mos keladigan muammolarni umumlashtirish. Keyin u Levenshtein masofaviy penalti ballari va affin-bo'shliq penalti ballari bilan taxminiy satrlarni moslashtirish muammolarini Leaping Toad muammosiga aylantirishning batafsil tartibini ko'rsatadi.
U umumiy Leaping Toad muammosini hal qiladigan LandauVishkin algoritmining kengaytmasi bo'lgan LEAP yangi algoritmini taqdim etadi.
U LEAP orqali bit vektorlashtirilgan, de Bruijn ketma-ketligiga asoslangan optimallashtirishni ta'minlaydi, bu oddiy bit-vektor operatsiyalari bilan bit-vektordagi eng muhim "1" o'rnini topish uchun de Bruijn ketma-ketliklarining xususiyatlaridan foydalanadigan mukammal xesh funktsiyasidan foydalanadi. .
Bu shuni ko'rsatadiki, bit-vektorlashtirilgan LEAP eng so'nggi Levenshtein taxminiy string moslamalariga qaraganda 7,4 baravar tezroq va eng so'nggi affin bo'shliqlari taxminiy satrlarni moslashtirish ilovalariga qaraganda 32 baravar tezroq.
Qog'ozning qolgan qismi quyidagicha tashkil etilgan; "Fon" bo'limi taxminiy satrlarni moslashtirish muammosini batafsil tushuntirishni, shuningdek, o'tgan ishlar va umumiy echimlarning tahlillarini taqdim etadi; Metods bo'limida Leaping Toad muammosi, shuningdek, uning umumiy yechimi, LEAP va LEAP bo'yicha bit-vektor optimallashtirish tasvirlangan; Natijalar bo'limi LEAPni Levenshteinning eng zamonaviy masofaviy tatbiqlari bilan bir qatorda affin-bo'shliqni amalga oshirish bilan solishtiradi; Muhokama bo'limida LEAP ning afzalliklari va cheklovlari muhokama qilinadi; va nihoyat, Xulosa bo'limi maqolani umumlashtiradi.
Global va yarim global tarmoqli Levenshteyn masofa muammosi (BLDP) va tarmoqli affin bo'shliq masofasi muammosi (BAGDP) yo'naltirilgan asiklik grafikda cheklangan optimal yo'lni topish muammosi sifatida umumlashtirilishi mumkin. Biz buni Leaping Toad muammosi (LTP) deb ataymiz. Ushbu bo'limda biz birinchi navbatda Leaping Toad muammosini taklif qilamiz va biz umumiy tahrirlash masofasi muammosini LTP misoliga qanday aylantirish mumkinligini ko'rsatamiz. Keyinchalik biz yechim sifatida takomillashtirilgan dinamik dasturlash algoritmi LEAPni taklif qilamiz , so'ngra uning optimalligini isbotlaymiz. Biz LEAPning orqaga qaytish jarayonini muhokama qilamiz. Bundan tashqari, biz LEAP orqali de Bruijn ketma-ketligiga asoslangan bit-vektor optimallashtirishni taqdim etamiz. Nihoyat, biz affin-bo'shliq jazolari algoritmini optimallashtirishni muhokama qilamiz.