De afstand tussen ongewortelde fylogenetische bomen

De afstand tussen ongewortelde fylogenetische bomen

van Aken, M.

van Iersel, L.J.J. (mentor)

Electrical Engineering, Mathematics and Computer Science

Delft Institute of Applied Mathematics

2016-08-24

Een ongewortelde, binaire, fylogenetische boom is een boom waarvan de bladeren gelabeld zijn en iedere niet-gelabelde knoop graad 3 heeft. Fylogenetische bomen worden gebruikt om de ontstaansgeschiedenis van organismen te begrijpen. Twee fylogenetische bomen T1 en T2 met dezelfde gelabelde blad-verzameling L kunnen namelijk vergeleken worden. Kan het ene organisme ontstaan zijn uit het andere organisme? Zo ja, hoe groot is de vergelijkenis? Door middel van zogenoemde Subtree Transfer-operaties kan T1 omgevormd worden tot T2. De twee belangrijkste Subtree Transfer-operaties in dit verslag zijn SPR-operaties en TBRoperaties. Bij beide operaties wordt er eerst een tak verwijderd van de boom. Bij een SPR-operatie wordt een tak geknipt en aan een andere tak vastgemaakt, terwijl bij een TBR-operatie een tak volledig verwijderd wordt, waarna een nieuwe tak de verbinding zal zijn tussen de ontstane deelbomen. Hoe vaak een operatie moet worden toegepast om T1 om te vormen tot T2 heet de afstand tussen de bomen. De probleemstelling van dit verslag luidt: hoe kan de TBR-afstand tussen twee fylogenetische bomen bepaald worden? Het blijkt dat de exacte afstand tussen T1 en T2 verbonden is met het aantal componenten in een Maximum Agreement Forest van T1 en T2 [1]. EenMAF kan omschreven worden als het minimale aantal bomen, zó dat iedere boom een deelboom van T1 en T2 is; de bomen disjunct zijn; en deze bomen heelL opspannen. Aangezien voor de probleemstelling een MAF gevonden moet worden tussen twee fylogenetische bomen, wordt in hoofdstuk 2 een handig uitstapje gemaakt. Wanneer twee bomen topologisch verwant zijn, kunnen ze gereduceerd worden, zonder dat de TBR-afstand verandert [1]. In hoofdstuk 3 wordt laten zien dat bij gewortelde, binaire bomen gekeken wordt naar onverenigbare trippels om een agreement forest te vinden. Twee gewortelde, binaire bomen zijn namelijk equivalent dan en slechts dan als iedere trippel in de twee bomen topologisch equivalent is [2]. Bij twee fylogenetische bomen T1 en T2 wordt er gekeken naar onverenigbare kwartetten. In hoofdstuk 4 wordt een algoritme beschreven die de TBR-afstand berekent [3]. Deze berekening bestaat uit twee fasen. In de eerste fase worden van bepaalde onverenigbare kwartetten in T2 een tak verwijderd, zodat er een bos F0 overblijft. In de tweede fase wordt gekeken naar paden die disjunct zijn in F0, maar overlappen in T2. Weer worden er takken verwijderd, zodat na de tweede fase een agreement forest overblijft. Tot slot wordt in het laatste hoofdstuk de theorie van hoofdstuk 3 en 4 gecombineerd. Deze combinatie resulteert in een nieuwe theorie. Dit geeft een ILP-formulering waarin de grootte van een MAF tussen twee fylogenetische bomen gevonden kan worden. Er is in dit verslag gekozen om alleen de belangrijkste lemma’s en stellingen te bewijzen. De kern van dit verslag ligt in de laatste drie hoofdstukken, dus daar zullen meer bewijzen te vinden zijn dan in de eerste twee.

http://resolver.tudelft.nl/uuid:a93653f7-584e-4d0b-ba4f-661d89f2101d

Student theses

master thesis

(c) 2016 van Aken, M.