Filogenetik daraxtlar klasterlash metodlari

Sharhlar
"Daraxtlar emas, balki tarmoqlar - tez evolyutsiya murakkabligini va genom ma'lumotlarida ziddiyatli signallarni tushunishning asosiy vositasiga aylanmoqda. Filogenetik tarmoqlar tarmoqqa asoslangan usullar, ulardan foydalanish mumkin bo'lgan va amaliy dasturiy ta'minot bo'yicha batafsil ma'lumotni uzoq vaqtdan beri taqdim etadi. Tarmoqlarning ko'p turlarini batafsil va birlashtirilgan ko'rib chiqish asosiy nazariyaning aniq konspekti bilan to'ldiriladi. Ko'p sonli misollar va rasmlar matnni bajarishni osonlashtiradi. Bu kitob biologlarning evolyutsiyani o'rganish uchun genom ma'lumotlaridan foydalanish usulini yanada o'zgartiradi. Tubingen guruhi filogenetik tarmoq algoritmlarini ishlab chiqishga rahbarlik qildi va bu kitobda so'nggi usullarning ko'pligidan hayratga tushgan biologlar, shuningdek, bu sohani yanada rivojlantirishni maqsad qilgan bioinformatistlar uchun aniq ko'rsatma berilgan. Genomik ma'lumotlarning "hayot to'rini" ifodalash va o'rganish uchun qanday ishlatilishini tushunishni istagan har bir olim yoki talaba uchun bu o'qish juda muhim. " Mayk Stil, Kenterberi universiteti.
“Bu soha yetakchilaridan biri (Daniel Huson) va uning hammualliflari tomonidan tayyorlangan ushbu darslik hisoblash biologiyasining eng qiziqarli va goʻzal tadqiqot yoʻnalishlaridan biri: filogenetik tarmoqlarga matematik jihatdan jiddiy kirishni taqdim etadi. Matn aniq va barcha zarur biologik ma'lumotlarga ega bo'lib, u matematika, informatika yoki statistikaning aspirantlari (yoki yuqori kurs talabalari) uchun ochiq bo'lishi kerak. Tandi Varnov, Texas universiteti.
"Bu ajoyib kitob-filogenetik tarmoqlarni davolashning eng puxta va dolzarb kitobidir. Tabiatdagi ko'plab evolyutsion jarayonlar filogenetik daraxtlarning oddiy modeliga mos kelmaydi, masalan, duragaylar, simbiozlar va genlarning lateral o'tkazilishi. Tabiatni genomika bilan qanchalik ko'p o'rgansak, bu misollar shunchalik ahamiyatli va ko'p bo'ladi, shuning uchun filogenetikada tarmoqlardan foydalanishga haqiqiy ehtiyoj bor. Bu jild filogenetik tarmoqlar bilan ishlaydigan tadqiqotchilar uchun majburiydir. Bu ilg'or kollej auditoriyasi uchun. Chiroyli tashkil etilgan va aniq yozilgan, bu bo'shliqni to'ldiradi. Bill Martin, Dyusseldorf universiteti.
Filogenez (yun. phylon — avlod, qabila va ... genez), filogeneya — tirik organizmlar hamda ular taksonomik guruxlari: olam, tip (boʻlim), sinf, turkum (tartib), oila, avlod (turkum, urugʻ) va turlarning tarixiy taraqqiyoti. "F." termini nemis olimi E. Gekkel tomonidan fanga kiritilgan (1866). Biologiyaning F. vauning qonuniyatlarini oʻrganadigan boʻlimi filogenetika deyiladi. F.ni tadqiq qilish evolyutsiyaning umumiy nazariyasini rivojlantirish, organizmlarning tabiiy sistemasini tuzish uchun zarur. Filogenetikaning xulos ari tarixiy geologlar uchun ham juda muhim. Gekkel F.ni tadqiq qilish uchun p eontologiya, solishtirma anatomiya va embriologiya d illarini taqqoslovchi uchlik par lelizm metodini taklif etgan. Filogenetikada genetika, biokimyo, molekulyar biologiya, etologiya, biogeogr., fiziologiya, parazitologiya d illaridan keng foyd anilmoqda. Bu d illar turdan yuqori boʻlgan har qanday taksonlar evolyutsiyasi borishini katta aniklik bilan tiklash imkonini beradi. Muhit sharoiti bir xil boʻlmagan, har xil biotik va abiotik omillar qurshovida turli guruxdardagi evolyutsion jarayonning borishini taqqoslash tarixiy taraqqiyotda katta guruhlarga xos umumiy xoss arni aniklash imkonini beradi. Guruhlar evolyutsiyasining barcha xususiyatlari individlarning morfofiziologik tomonlarini oʻrganish asosida aniqlanadi. Aksariyat guruxlar F.i adaptiv radiatsiyaga, yaʼni belgilarning dastlabki umumiy formadan raduis boʻylab har tomonga tarq ish xarakteriga ega. Oʻsimlik va hayvonlar F.i shajara daraxtini chizish yordamida tasvirlab beriladi. Shajara daraxti oʻsimlik va hayvonlarning umumiy bir ildizdan kelib chiqqanligi; turli xil form ar Yerdagi hayot tarixining har xil davrlarda shoxlanish orq i astasekin taraqqiy etganligini aks ettiradi. Organizmlar filogenetik qayta tuzilishlarining adaptiv xarakterini belgilovchi asosiy kuch tabiiy tanlanish hisoblanadi. Filogenetik shajara barcha oʻzgarishlarning birlamchi negizida divergensiya va filetik evolyutsiya, soʻng esa par lelizm va konvergensiya yotadi.
Organizm har xil guruhlarining F.i bir xilda oʻrganilmagan, bu qazilma qoldiklarning har xil darajada saqlanganligi va mazkur guruxlarning qanch ik qadimiyligi bilan bogʻliq. Umurtq i hayvonlar (ayniqsa, yuksak guruhlari) va yuksak oʻsimliklar F.i, umurtqasiz hayvonlardan esa mollyusk ar, ignaterililar, boʻgʻimoyoqlilar F.i nisbatan yaxshi, prokariotlar va tuban oʻsimliklar F. i kamroq oʻrganilgan.
Filogenetik daraxtlar qurilishi - bu bioinformatika fanining murakkab va keng o'rganilgan muammosi. NP-Complete xususiyatlaridan kelib chiqqan holda, bu tadqiqotchilar uchun h igacha ochiq muammo. Turlar sonining ko'payishi bilan hisoblashning murakkabligi ham oshadi, uni an'anaviy usullar bilan h qilib bo'lmaydi (mas an, arifmetik o'rtacha ko'rsatkichlar (UPGMA), Maksim ehtimollik, Maksim Parsimoniya). , Ba'zi metaevristik usullar bir qancha tadqiqotchilar tomonidan o'rganilmoqda va filogenetik daraxt qurildi va ba'zi istiqbolli natij ar haqida xabar berdi. Ushbu maqolada filogenetik daraxt rekonstruksiyasini optim lashtirish uchun ishlatilgan chumolilar koloniyasini optim lashtirish (ACO), zarrach ar to'dasini optim lashtirish (PSO) va genetik goritm (GA) kabi ba'zi metauristik yondashuvlar haqida qisqacha so'rov berilgan.
Filogenetik - bu turli xil tirik organizmlarning evolyutsion tarixini o'rganish usuli, bu erda turlar orasidagi farqlar filogeniya deb nomlanuvchi yo'n tirilgan grafik ar yoki daraxtlar bilan ifod anadi. 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 ifod ovchi 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 mah liy 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'lmaganl
Tuzilgan daraxt turlar o'rtasidagi munosabatni ifod ash uchun tugunlar turini ifod ovchi grafik nazariya standarti belgisiga am qilishi kerak. Qolgan maqol ar quyidagicha tartibga solinadi: 2 -bo'limda genetik goritm, so'ngra GA yordamida filogenetik daraxtni optim lashtirish bo'yicha ishlar olib boriladi. 3 -bo'limda chumolilar koloniyasini optim lashtirishning kiritilishi, 4 -bo'limda filogenetik daraxtni qurishda qo'llaniladigan GA va ACOdan boshqa usullar tasvirlangan. Oxirida 5 -bo'lim. Qog'oz yakunlanadi.
Genetik goritm - bu tabiiy evolyutsiyadan ilhomlangan texnikaga asoslangan evristik qidiruv goritmi, irsiyat, mutatsiya, tanlash va krossover kabi. GA kodlangan tasodifiy yechimlar populyatsiyasi bilan boshlanadi. Bunday kodlangan yechimlar odatda xromosom ar deb at adi va ularning muammoni h qilish qobiliyati fitnes funksiyasi yordamida tavsiflanadi. Bu odamlar fitnes qiymatiga qarab tabiiy tanlanishdan o'tadil Har bir avlodda shaxslar mutatsiyaga va rekombinatsiyaga uchraydilar, bunda muammoning xarakteriga qarab mutatsiya va rekombinatsiya operatorlari aniqlanadi. Keyin yangi populyatsiya goritmning keyingi iteratsiyasida ishlatiladi. goritm 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 goritm qanday qo'llanilishini muhokama qilamiz, so'ngra C bo'limida genetik goritm orq i 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 optim echimlarni topish qobiliyati ularni qiladi. Filogenetik xulosa chiqarish muammosiga ide nomzodlar, ayniqsa, ko'plab soliqlar kiritilganida yoki murakkab evolyutsion modellar (maksim ehtimollik kabi kompyuter intensiv xulosa chiqarish usullarini qo'llashni t ab qiladigan) qo'llanilganda. Filogeniya rekonstruksiya qilingan taqdirda, har bir shaxsning yagona xromosomasi bitta filogenetik daraxtni, uning shoxlari uzunligi va ishlatiladigan mashtirish modelini o'z ichiga olgan boshqa parametrlarning qiymatlari bilan kodlash uchun mo'lj langan bo'lishi mumkin. Mutogenlik va rekombinatsiya operatorlari filogenetik daraxtlar uchun aniqlanishi mumkin va odamning jismoniy tayyorgarligi uning tabiiy b liga 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 (1996) aminokislot ar ketma -ketligidan filogenetik daraxtlar yaratishni taklif qildi, bu genetik goritmdan farq qiladi, bu kodlash sxemasi, o'zaro faoliyat va mutatsion operatori asosida oddiy genetik goritmdan farq qiladi. Dastlabki bosqichda, mavjudlar orasidamuqobil daraxtlar, ularning yaroqliligiga qarab rulet tanlash orq i belgilangan miqdordagi daraxtlar tanlangan. Shundan so'ng daraxtlarning sifatini yaxshilash uchun avloddan -avlodga krossover va mutatsion operatsiy ar qo'llanildi. Har bir avloddagi daraxtlar soni aniqlanganligi sababli, eng yaxshi b l to'plagan daraxtlar ushbu operatorlar tomonidan olib tashlanadi. goritm shuningdek, eng yaxshi b l bilan qurilgan daraxt har bir avlod uchun omon qolishi kerakligini tekshiradi. goritmning asosiy afz ligi uning tasodifiy hosil bo'lgan daraxtlardan krossover va mutatsiya operatorlari yordamida ko'proq ehtimoliy daraxt qurish qobiliyatidir. Eksperiment natij ar shuni ko'rsatadiki, taklif qilingan goritmning ishlashi boshqa Maksim Parsimon Maksim ehtimoli, UPGMA usullari kabi turli xil daraxt qidirish goritmlari 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 optim bo'lmagan daraxtlarni baholashga sarflanadigan vaqtni oshiradi. Bu muammoni bartaraf etish uchun Paul.et. (1998) nukleotidlar ketma-ketligi ma'lumotlaridan foyd anib, maksim ehtimollik filogenezi xulosasi uchun genetik goritmni taklif qildi. Pavlus genetik goritmga asoslangan evristik qidiruvni taqdim etadi, bu ko'p sonli taksonlarni o'z ichiga olgan ma'lumotlar to'plamida maksim ehtimollik filogenetik xulosa qilish uchun zarur bo'lgan vaqtni kamaytiradi. goritm quyidagicha ishlaydi: Birinchidan, har bir shaxs tasodifiy daraxt topologiyasi bilan ishga tushiriladi, unda har bir fili ga tasodifiy qiymat beriladi. InL b l asosida har bir zarrachaning yaroqlilik qiymati hisoblanadi. InL b ining eng yuqori qiymatiga ega bo'lgan shaxs keyingi avlod uchun nasl berish uchun ishlatiladi. Nihoyat, rekombinatsiya operatsiyasi am ga oshiriladi. Bu rekombinatsiya operatsiyasi GAni boshqa an'anaviy echimlardan kamroq vaqt ichida yechim olishdan ajratib turadi. Eksperiment natij ar shuni ko'rsatadiki, bir xil Maksim ehtimollik topologiyasini olish uchun daraxtning ikkiga bo'linishi (TBR) novd arini mashtirishdan foyd angan holda an'anaviy evristik qidiruv uchun t ab qilinadigan hisoblash harakatlarining atigi 6%.
2002 yilda Clare taklif qilgan "Gaphyl: organizmlar o'rtasidagi evolyutsion munosabatlarni o'rganish uchun evolyutsion goritmlar yondashuvi". Mavjud filogenetik dasturiy paketlar optim filogenetik daraxtni topish uchun evristik qidiruv usullaridan foyd anadi, Graphyl esa evolyutsion mexanizmlardan foyd anadi, shuning uchun qisqa vaqt ichida to'liqroq yechim topadi. Grafildagi GA qidirish jarayoni filogenetika uchun xuddi shu ish vaqtida Phylip ga qaraganda bir xil darajada ishonchli daraxtlarni topishda katta foyda keltiradi. Bundan tashqari, ma'lumotlar to'plami turlar va atributlar sonining ko'payishi hisobiga katt ashib 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 (2003) Gafilning yangi versiyasini taklif qildi, unda Gafil genetik ma'lumotlar bilan ishlash uchun kengaytirilgan. Taklif etilgan goritmda Gafilning DNK versiyasi tuzilgan va DNK ma'lumotlari asosida Gafil va Filipni qidirish jarayoni solishtirilgan. Eksperiment natij ar shuni ko'rsatadiki, Gafilning ishlashi, ba'zi hollarda, Filipga qaraganda yaxshiroq.
Chumolilar koloniyasini optim lashtirish (ACO) M. Dorigo tomonidan ishlab chiqilgan evolyutsiya goritmidir (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 manb ariga etib borishiga yordam beradi. Feromon yo'llari orq i chumolilar o'rtasidagi bilvosita oqa yordamida uya va oziq-ovqat manbai o'rtasidagi eng qisqa yo'lni topishga yordam beradi. Chumolilar koloniy arining bu xususiyati sun'iy chumolilar koloniy arida kombinativ optim lashtirish (CO) muammolarini h qilish uchun ishlatiladi. Umuman olganda, ACO optim lashtirish muammolarini h 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 optim lashtirish (ACO) qanday qo'llanilishini muhokama qilamiz, so'ngra C bo'limida bir qancha tadqiqotchilar chumolilar koloniyasini optim lashtirish orq i 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 goritmlarni qo'llashga yo'l ochadi, vositachi tugun chumolilar tizimi tomonidan ilgari tanlangan ikkitasi orasidan tanlanadi. Vositachilik tuguniga asoslanib, qolgan tugunlarga (turlarga) bo'lgan masof ar 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 foyd anilgan yo'lning b li deb at adi. Am ga oshirish tsikli davomida hech bo'lmaganda bitta yo'lga tegishli bo'lgan barcha tugunlar feromon izini oshirishga yordam beradi. Bu asosiy nuqta mah liy maksim tuzoqqa tushmaslikka yordam beradi. Shunday qilib, TSPni echish uchun chumolilar koloniyasi goritmiga ruhiy jihatdan yaqin bo'lgan goritmga am qilib, filogenetik daraxtlarni samar i rekonstruksiya qilish mumkin .
Shin Ando.et (2002) Evolyutsion daraxt qurilishi uchun chumolilar goritmini taklif qildi. goritm NP muammolarida metaevristik qidiruvni o'rganish uchun ACO goritmini qo'llaydi. Mu lif ikkita yangi mexanizmni taqdim etadi: qo'shimchani ifod ash va tep ik tanlash mexanizmi, bu chumolilar koloniyasini o'rganish qobiliyatini takomillashtirish strategiyasini qo'llashda yordam beradi. goritm mumkin bo'lgan daraxtlar to'plamidan daraxt tanlaydi, bu ma'lum bir DNK ketma -ketligi uchun b ni kamaytiradi. Taklif etilgan goritm simulyatsiya qilingan eksperimentda va 15 turdan oqsil ketma -ketligini moslashtirishda qoniqarli natij arni ko'rsatadi.

Xulosa
Ushbu kurs ishi 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. Natij ar an'anaviy usullarga qaraganda qoniqarli natij arni ko'rsatmoqda. Biroq, SI vosit ari ham istiqbolli ko'rinadi, chunki bioinformatikaning bir nechta vazif ari turli mezonlarni optim lashtirishni o'z ichiga oladi va shu bilan SI vosit arini (ACO va PSO kabi) filogenetik daraxtlarni qayta tiklash muammosini h qilishda yanada aniqroq va mos ravishda qo'llashni o'z ichiga oladi. GA bilan solishtirganda, turli tadqiqotchilar tomonidan taklif qilingan SI asosidagi goritm yaxshi natij ar beradi. Shu nuqtai nazardan chop etilgan maqol ar kichik hajmda bo'lishi mumkin, lekin ertangi kun tadqiqotchilari uchun juda katta ahamiyatga ega, chunki bu soha keng va h i ko'p tadqiqotlar olib borilishi kerak.