Referati topshirdi: Otajonov. I qabul qildi: Nurmetova. M urganch-2023 Mavzu

Mavzu: Filogenetik daraxtlarni tuzish algaritmlari.
Filogenetik daraxtlar qurilishi - bu bioinformatika fanining murakkab va keng o'rganilgan muammosi. NP-Complete xususiyatlaridan kelib chiqqan holda, bu tadqiqotchilar uchun haligacha ochiq muammo. Turlar sonining ko'payishi bilan hisoblashning murakkabligi ham oshadi, uni an'anaviy usullar bilan hal qilib bo'lmaydi (masalan, arifmetik o'rtacha ko'rsatkichlar (UPGMA), Maksimal ehtimollik, Maksimal Parsimoniya). , Ba'zi metaevristik usullar bir qancha tadqiqotchilar tomonidan o'rganilmoqda va filogenetik daraxt qurildi va ba'zi istiqbolli natijalar haqida xabar berdi. Ushbu maqolada filogenetik daraxt rekonstruksiyasini optimallashtirish uchun ishlatilgan chumolilar koloniyasini optimallashtirish (ACO), zarrachalar to'dasini optimallashtirish (PSO) va genetik algoritm (GA) kabi ba'zi metauristik yondashuvlar haqida qisqacha so'rov berilgan.
Filogenetik [19] - bu turli xil tirik organizmlarning evolyutsion tarixini o'rganish usuli, bu erda turlar orasidagi farqlar filogeniya deb nomlanuvchi yo'naltirilgan grafikalar yoki daraxtlar bilan ifodalanadi. Daraxt har xil turlarning molekulyar ketma -ketligi asosida qurilgan. Molekulyar ketma -ketlikning namoyishi genlar filogeniyasi deb nomlanuvchi genlar yoki oqsillar ketma -ketligidan kelib chiqadi, filogeniya turlari esa har xil turlarning evolyutsion yo'lini ifodalovchi jarayon sifatida ta'riflanadi. Gen filogeniyasi turli genlar o'rtasidagi o'zaro bog'liqlikni, ya'ni turli genlar orasidagi genlar ketma-ketligi bir-biri bilan ko'proq yoki kamroq bog'liqligini bilishga yordam beradigan gen evolyutsiyasini va kodlangan gen ketma-ketligini tavsiflovchi mahalliy tavsiflovchi sifatida bo'lishi mumkin. Daraxtlarning asosan ikki turi bor a). ildizli daraxtlar: barcha tugunlar bitta tugundan olingan va b) ildizi yo'q daraxtlar: bitta tugundan hosil bo'lmaganlar.
Tuzilgan daraxt turlar o'rtasidagi munosabatni ifodalash uchun tugunlar turini ifodalovchi grafik nazariya standarti belgisiga amal qilishi kerak. Qolgan maqolalar quyidagicha tartibga solinadi: 2 -bo'limda genetik algoritm, so'ngra GA yordamida filogenetik daraxtni optimallashtirish bo'yicha ishlar olib boriladi. 3 -bo'limda chumolilar koloniyasini optimallashtirishning kiritilishi, 4 -bo'limda filogenetik daraxtni qurishda qo'llaniladigan GA va ACOdan boshqa usullar tasvirlangan. Oxirida 5 -bo'lim. Qog'oz yakunlanadi.
Genetik algoritm [2] - bu tabiiy evolyutsiyadan ilhomlangan texnikaga asoslangan evristik qidiruv algoritmi, irsiyat, mutatsiya, tanlash va krossover kabi. GA kodlangan tasodifiy yechimlar populyatsiyasi bilan boshlanadi. Bunday kodlangan yechimlar odatda xromosomalar deb ataladi va ularning muammoni hal qilish qobiliyati fitnes funksiyasi yordamida tavsiflanadi. Bu odamlar fitnes qiymatiga qarab tabiiy tanlanishdan o'tadilar. Har bir avlodda shaxslar mutatsiyaga va rekombinatsiyaga uchraydilar, bunda muammoning xarakteriga qarab mutatsiya va rekombinatsiya operatorlari aniqlanadi. Keyin yangi populyatsiya algoritmning keyingi iteratsiyasida ishlatiladi. Algoritm odatda natijani beradigan yechim kerakli javobga etarlicha yaqin yoki teng bo'lganda yoki aholi uchun qoniqarli moslik darajasiga erishilganda tugaydi. B bo'limida biz daraxtlarni filogenetik rekonstruksiya qilishda genetik algoritm qanday qo'llanilishini muhokama qilamiz, so'ngra C bo'limida genetik algoritm orqali filogenetik daraxtni qurish uchun bir nechta tadqiqotchilar tomonidan bajarilgan ishlarni tasvirlaymiz.
GA ko'p yillar davomida muhandislikning turli xil murakkab muammolariga qo'llanilgan, garchi ulardan biologik ma'lumotlar bilan bog'liq muammolarda qo'llanilishi bir necha yil oldin o'rganilgan bo'lsa-da, GA ning murakkab ma'lumotlar holatida tezda deyarli optimal echimlarni topish qobiliyati ularni qiladi. Filogenetik xulosa chiqarish muammosiga ideal nomzodlar, ayniqsa, ko'plab soliqlar kiritilganida yoki murakkab evolyutsion modellar (maksimal ehtimollik kabi kompyuter intensiv xulosa chiqarish usullarini qo'llashni talab qiladigan) qo'llanilganda. Filogeniya rekonstruksiya qilingan taqdirda, har bir shaxsning yagona xromosomasi bitta filogenetik daraxtni, uning shoxlari uzunligi va ishlatiladigan almashtirish modelini o'z ichiga olgan boshqa parametrlarning qiymatlari bilan kodlash uchun mo'ljallangan bo'lishi mumkin. Mutogenlik va rekombinatsiya operatorlari filogenetik daraxtlar uchun aniqlanishi mumkin va odamning jismoniy tayyorgarligi uning tabiiy balliga teng bo'lishi mumkin. LnL qiymatlari yuqori bo'lgan daraxtlar keyingi avlodga ko'proq avlod qoldirishga moyildirlar va tabiiy tanlanish simulyatsiya qilingan populyatsiyadagi odamlarning o'rtacha miqdorini oshiradi. Aholining jismoniy holati yaxshilanishni to'xtatgandan keyin eng yuqori lNLga ega bo'lgan daraxt, ehtimollik ehtimoli yuqori bo'lgan daraxtning eng yaxshi bahosi hisoblanadi
Hideo Matsuda [5] (1996) aminokislotalar ketma -ketligidan filogenetik daraxtlar yaratishni taklif qildi, bu genetik algoritmdan farq qiladi, bu kodlash sxemasi, o'zaro faoliyat va mutatsion operatori asosida oddiy genetik algoritmdan [2] farq qiladi. Dastlabki bosqichda, mavjudlar orasidamuqobil daraxtlar, ularning yaroqliligiga qarab rulet tanlash orqali belgilangan miqdordagi daraxtlar tanlangan. Shundan so'ng daraxtlarning sifatini yaxshilash uchun avloddan -avlodga krossover va mutatsion operatsiyalar qo'llanildi. Har bir avloddagi daraxtlar soni aniqlanganligi sababli, eng yaxshi ball to'plagan daraxtlar ushbu operatorlar tomonidan olib tashlanadi. Algoritm shuningdek, eng yaxshi ball bilan qurilgan daraxt har bir avlod uchun omon qolishi kerakligini tekshiradi. Algoritmning asosiy afzalligi uning tasodifiy hosil bo'lgan daraxtlardan krossover va mutatsiya operatorlari yordamida ko'proq ehtimoliy daraxt qurish qobiliyatidir. Eksperimental natijalar shuni ko'rsatadiki, taklif qilingan algoritmning ishlashi boshqa Maksimal Parsimon Maksimal ehtimoli, UPGMA usullari kabi turli xil daraxt qidirish algoritmlari bilan solishtirish mumkin.
Filogeniyani rekonstruktsiya qilish - bu qiyin hisoblash muammosi, chunki ko'p miqdordagi soliqlar (ob'ektlar) ni o'z ichiga olgan holda, mumkin bo'lgan echimlar ham ko'payadi, bu esa optimal bo'lmagan daraxtlarni baholashga sarflanadigan vaqtni oshiradi. Bu muammoni bartaraf etish uchun Paul.et.al [8] (1998) nukleotidlar ketma-ketligi ma'lumotlaridan foydalanib, maksimal ehtimollik filogenezi xulosasi uchun genetik algoritmni taklif qildi. Pavlus genetik algoritmga asoslangan evristik qidiruvni taqdim etadi, bu ko'p sonli taksonlarni o'z ichiga olgan ma'lumotlar to'plamida maksimal ehtimollik filogenetik xulosa qilish uchun zarur bo'lgan vaqtni kamaytiradi. Algoritm quyidagicha ishlaydi: Birinchidan, har bir shaxs tasodifiy daraxt topologiyasi bilan ishga tushiriladi, unda har bir filialga tasodifiy qiymat beriladi. InL ball asosida har bir zarrachaning yaroqlilik qiymati hisoblanadi. InL balining eng yuqori qiymatiga ega bo'lgan shaxs keyingi avlod uchun nasl berish uchun ishlatiladi. Nihoyat, rekombinatsiya operatsiyasi amalga oshiriladi. Bu rekombinatsiya operatsiyasi GAni boshqa an'anaviy echimlardan kamroq vaqt ichida yechim olishdan ajratib turadi. Eksperimental natijalar shuni ko'rsatadiki, bir xil Maksimal ehtimollik topologiyasini olish uchun daraxtning ikkiga bo'linishi (TBR) novdalarini almashtirishdan foydalangan holda an'anaviy evristik qidiruv uchun talab qilinadigan hisoblash harakatlarining atigi 6%.
2002 yilda Clare et. al [10] taklif qilgan "Gaphyl: organizmlar o'rtasidagi evolyutsion munosabatlarn o'rganish uchun evolyutsion algoritmlar yondashuvi". Mavjud filogenetik dasturiy paketlar optimal filogenetik daraxtni topish uchun evristik qidiruv usullaridan foydalanadi, Graphyl esa evolyutsion mexanizmlardan foydalanadi, shuning uchun qisqa vaqt ichida to'liqroq yechim topadi. Grafildagi GA qidirish jarayoni filogenetika uchun xuddi shu ish vaqtida Phylip [3] ga qaraganda bir xil darajada ishonchli daraxtlarni topishda katta foyda keltiradi. Bundan tashqari, ma'lumotlar to'plami turlar va atributlar sonining ko'payishi hisobiga kattalashib borgan sari, Gafilning Filip ustidan samaradorligi oshadi, chunki Gafil qidirish jarayoni atributlar (va atributlar-qiymatlar) soniga va qidirishning murakkabligiga bog'liq emas. daraxtdagi barg tugunlari sonini aniqlaydigan turlar soniga qarab o'zgaradi. ketma-ketliklar bo’yicha ma’lumotlar ba’zalari.