Urganch davlat unversiteti

OʻZBEKISTON RESPUBLIKASI OLIY VA OʻRTA MAXSUS TA’LIM VAZIRLIGI

URGANCH DAVLAT UNVERSITETI
BIOLOGIYA FAKULTETI BIOLOGIYA YOʻNALISHI BIOINFORMATIKA FANIDAN

MUSTAQIL ISHI
MAVZU: Filogenetik daraxtlarni tuzish algoritmlari


BAJARDI:
TEKSHIRDI:

Urgench -2023

Mavzu: Filogenetik daraxtlarni tuzish algoritmlari
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 munosabatlarni 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.
Gafil Kler. va boshqalar. al [12] (2003) Gafilning yangi versiyasini taklif qildi, unda Gafil genetik ma'lumotlar bilan ishlash uchun kengaytirilgan. Taklif etilgan algoritmda Gafilning DNK versiyasi tuzilgan va DNK ma'lumotlari asosida Gafil va Filipni qidirish jarayoni solishtirilgan. Eksperimental natijalar shuni ko'rsatadiki, Gafilning ishlashi, ba'zi hollarda, Filipga qaraganda yaxshiroq.
Chumolilar koloniyasini optimallashtirish (ACO) M. Dorigo tomonidan ishlab chiqilgan evolyutsiya algoritmidir. va boshqalar. al [6] (1996), haqiqiy chumolilarning ovchilik xatti -harakatlaridan ilhomlangan. Chumoli ovqatni qidirganda, chumoli dastlab uyasi bilan qoplangan joyni tasodifiy ravishda siljitadi. Chumoli oziq -ovqat manbasini topgach, uning sifati va miqdorini tahlil qilib, uning bir qismini uyasiga qaytaradi. Kimyoviy feromon izi chumoli qaytib kelganida erga tushiriladi. Bu boshqa chumolilarga oziq -ovqat manbalariga etib borishiga yordam beradi. Feromon yo'llari orqali chumolilar o'rtasidagi bilvosita aloqa yordamida uya va oziq-ovqat manbai o'rtasidagi eng qisqa yo'lni topishga yordam beradi. Chumolilar koloniyalarining bu xususiyati sun'iy chumolilar koloniyalarida kombinativ optimallashtirish (CO) muammolarini hal qilish uchun ishlatiladi. Umuman olganda, ACO optimallashtirish muammolarini hal qilish uchun ikki bosqichni takrorlaydi.
1) Nomzodlik eritmasi feromonli model yordamida quriladi, ya'ni eritma maydonida ehtimollik taqsimotini parametrlangan holda ishlatish.
2) Nomzod echimlar yaxshi sifatli eritma olishda filtrlash uchun ferom qiymatlarini yangilash yoki o'zgartirish uchun ishlatiladi.
B bo'limida biz filogenetik daraxtlarni rekonstruksiya qilishda chumolilar koloniyasini optimallashtirish (ACO) qanday qo'llanilishini muhokama qilamiz, so'ngra C bo'limida bir qancha tadqiqotchilar chumolilar koloniyasini optimallashtirish orqali filogenetik daraxtni qurish uchun qilgan ishlarini tasvirlab beramiz.
Filogenetik daraxt qurilishi muammosi standart TSP (sayohatchi sotuvchi muammosi) ga juda o'xshash. Har bir taksiga bitta xayoliy shaharni bog'lash mumkin va bu mos keladigan taksilar juftligi uchun ma'lumotlar matritsasidan olingan ma'lumotlar ikki shahar orasidagi masofa sifatida belgilanadi. Muammoning bunday tuzilishi ACO kabi evristik algoritmlarni qo'llashga yo'l ochadi, vositachi tugun chumolilar tizimi tomonidan ilgari tanlangan ikkitasi orasidan tanlanadi. Vositachilik tuguniga asoslanib, qolgan tugunlarga (turlarga) bo'lgan masofalar qayta hisoblab chiqiladi. Ushbu protsedura, tashrif buyurilgan tugunlarga tegishli bo'lmagan barcha tugunlar yo'l qurilgunga qadar takrorlanadi. Yo'lning qo'shni tugunlarining o'tish ehtimoli yig'indisi feromon izini yangilashda foydalanilgan yo'lning balli deb ataladi. Amalga oshirish tsikli davomida hech bo'lmaganda bitta yo'lga tegishli bo'lgan barcha tugunlar feromon izini oshirishga yordam beradi. Bu asosiy nuqta mahalliy maksimal tuzoqqa tushmaslikka yordam beradi. Shunday qilib, TSPni echish uchun chumolilar koloniyasi algoritmiga ruhiy jihatdan yaqin bo'lgan algoritmga amal qilib, filogenetik daraxtlarni samarali rekonstruksiya qilish mumkin .
Shin Ando.et.al [11] (2002) Evolyutsion daraxt qurilishi uchun chumolilar algoritmini taklif qildi. Algoritm NP muammolarida metaevristik qidiruvni o'rganish uchun ACO algoritmini qo'llaydi. Muallif ikkita yangi mexanizmni taqdim etadi: qo'shimchani ifodalash va tepalik tanlash mexanizmi, bu chumolilar koloniyasini o'rganish qobiliyatini takomillashtirish [7] strategiyasini qo'llashda yordam beradi. Algoritm mumkin bo'lgan daraxtlar to'plamidan daraxt tanlaydi, bu ma'lum bir DNK ketma -ketligi uchun balni kamaytiradi. Taklif etilgan algoritm simulyatsiya qilingan eksperimentda va 15 turdan oqsil ketma -ketligini moslashtirishda qoniqarli natijalarni ko'rsatadi.
Pist Kumnorkaew.et.al [15] (2004) Chumolilar koloniyasiga asoslangan yangi algoritmni taklif qildi, unda evolyutsion daraxt daraxt konstruktsiyasi, novdalar uzunligini hisoblash, filial nuqtasini tanlash, yangi ACO parametri va masofani tortish parametri. Algoritm chumolilarni turli filial nuqtalariga joylashtirishdan boshlanadi va har bir chekkada feromon izining boshlang'ich qiymatini o'rnatadi. Tarmoq nuqtasi tanlash vektoridagi har bir chumolining filial nuqtasi tartiblangandan so'ng, har bir chumoli feromon izi va masofasidan kelib chiqib, keyingi bosqichga o'tish uchun shaharlarni tanlaydi. Algoritm shaharni tanlash va har bir chumolining harakatini barcha chumolilar sayohatlari va filiallarini tugatmaguncha takrorlaydi.
nuqta tanlash vektori to'ldiriladi. Umumiy filial
har bir chumolining uzunligi hisoblab chiqiladi va feromonning qiymati yangilanadi. Tarmoq nuqtasi tanlash vektorini bo'shatishdan oldin, eng qisqa umumiy tarmoq uzunligi saqlanadi. Bu jarayon tugatish shartiga erishilgunga qadar davom etadi. Algoritmning qobiliyatini yanada kuchaytirish uchun kichik uzunlikdagi manfiy qabul qilingan, chunki n ning katta qiymatlari bo'lsa (n - evolyutsion daraxt muammosidagi turlar soni), musbat novdalar uzunligini qabul qilish konvergentsiyani cheklaydi. Olingan natija chumolining eng qisqa yo'li bo'lib, evolyutsiya daraxtini qurish uchun etarli bo'lgan novdalar yorliqlari va uzunliklarini o'z ichiga oladi. Eksperimental natijalar shuni ko'rsatadiki, algoritm polinomli vaqtda evolyutsion daraxt muammosining eksponent vaqt murakkabligini ancha kamaytiradi.
Maurisio Perretto. va boshqalar. al [16] (2005) chumolilar koloniyasini optimallashtirish paradigmasi yordamida filogenetik daraxtni rekonstruksiya qilishni taklif qildi. Taklif etilgan algoritmda filogenetik daraxtlarni rekonstruksiya qilish
turlar orasidagi masofa matritsasi yordamida to'liq bog'langan grafik tuzish orqali amalga oshiriladi. Ushbu grafikada turlar orasidagi masofa va tugunlar turni ifodalaydi. Dastlab chumolilar tasodifiy tugunni tanlaydilar, keyin har bir tugunda yo'nalish o'tish funktsiyasidan kelib chiqib belgilanadi. Bu chumolining asosiy maqsadi o'tish ehtimolini maksimal darajada oshiradigan yo'lni topishdir, natijada eng kichik evolyutsion masofani hosil qiladigan turlar ketma -ketligi olingan. Taklif etilayotgan algoritm NEIGHBOR va FITCH dasturlari yordamida yaxshi ma'lum bo'lgan PHYLIP to'plami bilan taqqoslanadi. Taqqoslash ularning tuzilishi va tugunlar orasidagi umumiy masofani tahlil qilishga asoslangan. Umuman olganda, ushbu maqolada keltirilgan tajriba natijalari juda istiqbolli edi.
Ling. va boshqalar. al [18] (2006) daraxtlarning filogenetik qurilishiga stoxastik, optimallashtirish va klaster yordamida yangi yondashuvni taklif qildi, bunda chumolilar koloniyasi algoritmi ham klasterlash usuli, ham aglobal optimallashtirish texnikasi yordamida qo'llaniladi, shunda daraxtlar topologiyasi yomon bo'lsa ham optimal daraxt topiladi. . Taklif etilayotgan usul uchta komponentdan iborat, ya'ni boshlash, klasterlash va filogenetik daraxtlarni optimallashtirish orqali filogenetik daraxtlarni qurish. Boshlash bosqichida og'irlikdagi digraf quriladi, uning tepasi klasterlangan ma'lumotlarni, cheti esa ikkita ob'ekt o'rtasidagi qabul qilish tezligini ifodalaydi. Keyin chumoli digrafda sayohat qiladi va yo'lda feromonni yangilaydi va nihoyat chumolilar koloniyasi va uning feromonlari bilan aloqa tizimi ishlatiladi, bu daraxtning optimal topologiyasini olish uchun global optimallashtirish usuli sifatida ishlaydi. Taklif etilgan algoritm Genetik algoritm bilan taqqoslanadi va natijalar shuni ko'rsatadiki, u tezroq birlashadi va yuqori sifatga erishadi.
Jing Juo. va boshqalar. al [17] (2006) Filogenetik daraxt qurish uchun o'z-o'zidan moslashuvchi chumolilar koloniyasi algoritmini taklif qildi, unda filogenetik daraxt taqsimlanish muvozanati asosida qurilgan. Taklif etilayotgan usul 3 bosqichni o'z ichiga oladi, ishga tushirish, chumolilar tomonidan topilgan optimal yo'l bo'yicha filogenetik daraxtlarni qurish va optimallashtirish. Birinchi to'liq bog'langan grafik turlar orasidagi masofa matritsasi yordamida tuziladi. Filogenetik daraxtni qayta qurishni boshlash uchun chumolilar tasodifiy tugunni tanlash bilan boshlanadi. Ular tuzilgan grafik bo'ylab sayohat qilishadi va har bir tugunda chumolilar ehtimollik funktsiyasiga asoslanib o'z yo'nalishini topadi. Algoritm iz ma'lumotlarini to'g'rilaydi va yo'l tanlash taqsimotining muvozanati asosida har bir yo'lning ehtimoli aniqlanadi. Har bir chumoli protsedurani barcha tugunlar bir marta bosib o'tmaguncha takrorlaydi, ya'ni barcha tugunlar allaqachon tashrif buyurilgan tugunlar ro'yxatiga kiritiladi. Ushbu yo'lning balli yo'lda qo'shni tugunlarning ehtimollik funksiyasi yig'indisi bilan beriladi. Konvergentsiyani tezlashtirish va mahalliy konvergentsiyani oldini olish uchun algoritm har bir yo'l bo'yicha ma'lumotlarning tanlash ehtimoli va strategiyasini, olingan echimlarning sifati va taqsimlanishiga qarab sozlaydi. Taklif etilayotgan algoritm PHYLIP dasturiy ta'minot paketi va TSP-yondashuvidagi Neighbor Joining (NJ) dasturlari bilan taqqoslanadi. Tajriba natijalari shuni ko'rsatadiki, taklif qilingan algoritmni amalga oshirish va boshqa algoritmlarga qaraganda yuqori sifatli natijalarni olish osonroq.
Ling Chen.et. al [21] (2009) Chumolilar koloniyasini qismlarga ajratishga asoslangan filogenetik daraxt qurish uchun yangi algoritmni taklif qildi. Dastlab daraxtning ildizi aniqlanadi, bu genlar ketma-ketligi to'plamiga mos keladi. Keyin algoritm genlar ketma -ketligini ikkiga ajratadi, shunda bitta kichik to'plam o'xshash xususiyatga ega bo'ladi va har xil kichik guruhlar orasidagi genlar ketma -ketligi har xil xususiyatga ega. Bu jarayon barcha kichik guruhlar faqat bitta gen ketma -ketligini o'z ichiga olmaguncha takrorlanadi. Ushbu kichik to'plamlar yordamida filogenetik daraxt asta -sekin quriladi, unda barglar genlar ketma -ketligi. Bissektsiyaning har bir darajasi chumolilar koloniyasini sayohatchilar muammosini optimallashtirishga asoslangan. Tajriba natijalari shuni ko'rsatadiki, tavsiya etilgan algoritmni amalga oshirish oson, samaraliroq, tez birlashtiriladi va boshqa usullarga qaraganda yuqori sifatli natijalar olinadi.
Shuying.et.al [9](2000) Bayes usuliga asoslangan Markov zanjiri filogenetik rekonstruksiya usulini ishlab chiqdi. Usul Markov zanjiri Monte -Karlo (MCMC) texnikasi yordamida filogenetik daraxtlar ketma -ketligini hosil qiladi.Markov zanjiri metropol algoritmiga asoslangan bo'lib, uning statsionar taqsimoti filogenetik daraxtning kuzatilgan ketma -ketligini hisobga olgan holda shartli taqsimlanishi hisoblanadi. Algoritm butun dunyo bo'ylab filogeniyalar bo'ylab harakat qilish istagi va yuqori ehtimollik zonasida amalga oshirilishi mumkin bo'lgan harakatlar o'rtasidagi muvozanatni saqlaydi. Taklif etilayotgan algoritm har bir iteratsiya uchun tezdir, chunki maqsadli tugunni hisoblash mahalliy darajada saqlanadi va katta ma'lumotlar to'plami potentsial ravishda almashtirilganligi sababli, daraxtlardagi o'zgarishlar eng kam harakat bilan mumkin.
Filogenetik xulosa chiqarish uchun mavjud bo'lgan yondashuvlarning aksariyati bir nechta hizalama ketma -ketligidan foydalanadi. Ammo genlarni qayta tartibga solish, subversiya darajasida inversiya, transpozitsiya va translokatsiya, ketma -ketliklarning teng bo'lmagan uzunligi va boshqalar tufayli ko'p ketma -ketlik hizalanishi samarasiz. To'liq genomga asoslangan filogenetik tahlil jozibador, chunki bitta genlar ketma -ketligi organizmlarning evolyutsion tarixini tuzish uchun etarli ma'lumotga ega emas. Hasan bunday muammoni hal qilish uchun. va boshqalar. al (2003) filogenetik daraxt qurilishi uchun yangi ketma -ketlik masofa o'lchovini taklif qildi, bunda filogenetik daraxt LZ murakkabligi [1yordamida cheklangan ketma -ketliklar orasidagi o'lchangan masofaga asoslangan holda quriladi. S sonli ketma -ketlikning LZ murakkabligi S ni qurgan ishlab chiqarish jarayoni uchun zarur bo'lgan qadamlar soni sifatida aniqlanadi. Olingan masofa matritsasi filogenetik daraxtlarni qurish uchun ishlatiladi. Taklif etilayotgan yondashuvning asosiy afzalligi shundaki, u hech qanday ketma-ketlikni tekislash strategiyasini talab qilmaydi va butunlay avtomatikdir. Eksperiment natijalari shuni ko'rsatadiki, taklif qilingan algoritm real va simulyatsiya qilingan ma'lumotlar to'plamlari uchun samarali va izchil filogenezni muvaffaqiyatli qurdi.
Hui-Ying. va boshqalar. al [14] (2004) Filogenetik daraxtni qayta tiklash uchun yangi algoritmni taklif qildi, unda populyatsiyadan eng yaxshi daraxtni tanlash uchun Diskret zarrachalar to'dasini optimallashtirish (DPSO) qo'llaniladi. Taklif etilgan algoritmda dastlab har bir zarrachaning yaroqlilik qiymati populyatsiyada hisoblab chiqiladi va undan keyin filogenetik daraxt qurilishida maksimal yaroqlilik qiymatiga ega bo'lgan odam ishlatiladi. Daraxt qurilgandan so'ng, populyatsiyani yangilash va filiallarni sozlash amalga oshiriladi. Populyatsiyani yangilashda pozitsiya va tezlik DPSO [4] pozitsiyasi va tezligini yangilash tenglamalari yordamida yangilanadi. Daraxt shoxini sozlashning keyingi bosqichida taqqoslash amalga oshiriladi. Agar ikkita tugun orasidagi masofa 2D dan katta yoki teng bo'lsa (D ikki ketma -ketlik orasidagi masofani bildiradi), shoxni ajratib oling, aks holda filialni birlashtiring. Ushbu yangilanish filogenetik daraxt optimallashtirilmaguncha davom etadi. DPSO algoritmi boshlang'ich populyatsiya o'zgartirilsa ham optimallashtirilgan natijalar beradi. DPSO algoritmi turli xil yashil o'simliklardan rbcL xloroplast genining ketma-ketligini o'z ichiga olgan 25 ta ketma-ketlik masalasida qo'llaniladi va Eksperimental natijalar boshqa an'anaviy algoritmlarga nisbatan qoniqarli natijani ko'rsatadi.
Ushbu maqolada biz bir necha tadqiqotchilar tomonidan Filogenetik daraxtni yaratish bo'yicha yaqinda qilingan ba'zi sa'y-harakatlarni ko'rib chiqdik. Daraxtlarni filogenetik rekonstruksiya qilish muammosiga qisqacha ma'lumot berganimizdan so'ng, biz GA, PSO va ACO tomonidan filogenetik daraxtlarni qayta tiklash uchun bir nechta tadqiqotchilar tomonidan qo'llanilishi va qilgan ishlarini muhokama qildik. An'anaviy usullarning bir nechtasi e'tiroz va e'tibor bilan ko'rib chiqiladi, lekin ular eng maqbul echimga erisha olmaydi va katta hisob -kitob xarajatlaridan aziyat chekadi. Ushbu muammolarni bartaraf etish uchun GA boshqa usullar bilan birlashtirilgan. Natijalar an'anaviy usullarga qaraganda qoniqarli natijalarni ko'rsatmoqda. Biroq, SI vositalari ham istiqbolli ko'rinadi, chunki bioinformatikaning bir nechta vazifalari turli mezonlarni optimallashtirishni o'z ichiga oladi va shu bilan SI vositalarini (ACO va PSO kabi) filogenetik daraxtlarni qayta tiklash muammosini hal qilishda yanada aniqroq va mos ravishda qo'llashni o'z ichiga oladi. GA bilan solishtirganda, turli tadqiqotchilar tomonidan taklif qilingan SI asosidagi algoritm yaxshi natijalar beradi. Shu nuqtai nazardan chop etilgan maqolalar kichik hajmda bo'lishi mumkin, lekin ertangi kun tadqiqotchilari uchun juda katta ahamiyatga ega, chunki bu soha keng va hali ko'p tadqiqotlar olib borilishi kerak.