Filogenetik daraxtlar klasterlash metodlari

2.1 Tuzilgan daraxt turlar o'rtasidagi munosabat
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 [13] (2003) filogenetik daraxt qurilishi uchun yangi ketma -ketlik masofa o'lchovini taklif qildi, bunda filogenetik daraxt LZ murakkabligi [1] yordamida 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.
Chumolilar bir-biriga duch kelganda yoki o'z hamkasblarini qidirish jarayonida feromon deb ataladigan kimyoviy hidni uchitishi mumkin. Bunday hidga asoslanib, chumolilar o'ziga xos xususiyatlarga ega bo'lganlarni o'ziga jalb qiladi va boshqasini qaytaradi. Ushbu maqolada sun'iy chumolilar grafika bo'ylab sayohat qilishlari va ular o'tayotgan chekkalarga feromon yotqizishgan. ​ -rasmda ko'rsatilgandek. 1 -rasmda va 2 -rasmda, 2 -rasmda, sun'iy chumoli digagrafdagi qabul og'irligiga va ba'zi evristik ma'lumotlarga ko'ra keyingi tepalikni tanlaydi. Digrafning har bir chetidagi feromon sun'iy chumolilarning moslashuvchan harakatlari bilan yangilanadi, shuningdek, klasterlash jarayonini tezlashtirish uchun ba'zi adaptiv strategiyalar taqdim etiladi.
Kuchli komponentlar tahlili
Ob'ektlar qanchalik o'xshash bo'lsa, feromon miqdori shuncha yuqori bo'lishi mumkin. Har bir chekkadagi feromon miqdoridan to'liq foydalanish uchun biz feromon qiymati ma'lum bir chegaradan past bo'lgan ba'zi ulanishlarni o'tkazib yuboramiz va yangi digrafning kuchli bog'langan komponentlari finial klasterlarni hosil qiladi. Shunday qilib, boshlang'ich ob'ektlar chumolilar koloniyasi orqali bir nechta guruhlarga bo'linadi. Nihoyat, chumolilar tomonidan olingan bu klasterlar filogenetik daraxtlarni bosqichma -bosqich qurish uchun ishlatiladi.
Felogenetik daraxtlarni optimallashtirish
Xuddi shu kichik koloniyadagi sun'iy chumolilar o'zlarining hamkorliklari orqali muammoni hal qilish uchun mustaqil filogenetik daraxt qurishga harakat qiladilar va turli subkoloniyalar nomzodlarning xilma-xilligini saqlab qolish uchun turli xil daraxtlarni qurishadi. Ushbu daraxtlarni optimallashtirishdan so'ng, bu echimlarning ishlashi yaxshilanadi. Shu bilan birga, chumolilarning klasterlash jarayonini kuchaytirish uchun yuqori yaroqli daraxtlar chetidagi feromonlar ko'payadi.
Ushbu maqolada ko'rsatilgan filogenetik daraxtlarni qurish usuli, uning natijalarini GA bilan solishtirish uchun sinovdan o'tkazildi, tajriba natijalari shuni ko'rsatadiki, bizning algoritmni amalga oshirish osonroq va samaraliroq. GA bilan solishtirganda, u tezroq birlashishi va yuqori sifatli echimga ega bo'lishi mumkin.
Filogenetik daraxt qurish algoritmlari umumiy klasterlash algoritmlaridan farq qiadimi? - Biologiya