haku: @supervisor Janhunen, Tomi / yhteensä: 234
viite: 5 / 234
| Tekijä: | Koponen, Laura |
| Työn nimi: | Constraint-Based Optimization of Phylogenetic Supertrees |
| Evoluutiosuperpuiden rajoiteoptimointi | |
| Julkaisutyyppi: | Diplomityö |
| Julkaisuvuosi: | 2015 |
| Sivut: | vi + 60 s. + liitt. 5 Kieli: eng |
| Koulu/Laitos/Osasto: | Perustieteiden korkeakoulu |
| Oppiaine: | Tietojenkäsittelytiede (IL3010) |
| Valvoja: | Janhunen, Tomi |
| Ohjaaja: | Oikarinen, Emilia |
| Elektroninen julkaisu: | http://urn.fi/URN:NBN:fi:aalto-201506303579 |
| Sijainti: | P1 Ark Aalto 2885 | Arkisto |
| Avainsanat: | phylogenetics supertree answer set programming Felidae fylogenetiikka superpuu vastausjoukko-ohjelmointi kissaeläimet |
| Tiivistelmä (fin): | Lajien evoluutiohistoria esitetään tavallisesti evoluutiopuina eli fylogenioina. Evoluutiopuita rakennetaan esimerkiksi analysoimalla geenidataa käyttäen erilaisia heuristiikoita. Tavoitteena on selvittää kaikkien olemassaolevien lajien syntyhistoria. Tämä on laskennallisesti erittäin vaativa ongelma. Yksi ratkaisuehdotus laskennan helpottamiseen on aloittaa pienistä syötepuista ja yhdistää ne suuremmaksi evoluutiopuuksi eli superpuuksi, joka kattaa kaikki syötepuissa esiintyvät lajit. Tavoitteena on tuottaa superpuu, joka säilyttää lajien väliset suhteet niin hyvin kuin mahdollista. Parhaan superpuun löytäminen on sekin laskennallisesti vaativaa, sillä jo hyvin pienelle lajijoukolle vaihtoehtoisia puurakenteita on valtava määrä. Ongelmaan on esitetty monia eri menetelmiä, mutta nopeasti laadukkaita superpuita tuottavan menetelmän etsintä jatkuu edelleen. Yksi tapa yleisesti ratkaista laskennallisesti vaativia ongelmia on deklaratiivinen ohjelmointi, jossa määritellään vastauksen ominaisuudet sen sijaan, että määriteltäisiin algoritmiset askelet, joilla ratkaisuun päästään. Vastausjoukko-ohjelmointi eli sääntöpohjainen rajoiteohjelmointi (engl. answer set programming, ASP) on yksi deklaratiivisen ohjelmoinnin muoto. Tässä työssä esitellään kaksi menetelmää esittää superpuuongelma vastausjoukko-ohjelmoinnin keinoin. Menetelmiä yhdistää yhteinen aliohjelma, joka rakentaa mielivaltaisia järjestettyjä puita. Optimointifunktiot perustuvat kummassakin tapauksessa samalle idealle esittää syötepuut niissä esiintyvien alirakenteiden monijoukkona. Tavoite on toteuttaa mahdollisimman monta näistä alirakenteista superpuussa. Menetelmiä testattiin aiemmin julkaistuista kissaeläinten evoluutiopuista koostuneella datalla. Yksi menetelmä ei suoriutunut riittävän nopeasti edes yksinkertaistetusta syötteestä. Toinen menetelmä tuotti superpuita, joita verrattiin hiljattain samalle datalle yleisesti käytössä olevalla MRP-menetelmällä (engl. matrix representation with parsimony) laskettuihin superpuihin. Puiden laatu oli samaa luokkaa kolmella eri laatukriteerillä mitattuna. Jälkimmäisellä menetelmällä on nykyisellään rajoitteita, mistä esitetään esimerkki sekä alustava ratkaisuehdotus. Lisäksi laskennallista tehokkuutta voi olla mahdollista parantaa tulevaisuudessa. |
| Tiivistelmä (eng): | Evolutionary relationships of taxa are commonly represented as phylogenetic trees. These trees are constructed by analyzing primary data, such as DNA sequences, using different heuristics. The ultimate goal is to reconstruct the entire Tree of Life showing the evolutionary history of all known species. This is a computationally difficult problem. One suggested solution is to construct larger phylogenetic trees in parts, starting from smaller source trees and then combining those into a single output tree comprising the entire set of taxa. This is known as the supertree construction problem. The idea is to produce a supertree that best preserves the relationships of the taxa appearing in the source trees. This problem is computationally difficult in itself, as there are a large number of different tree topologies even for a very small number of taxa. Many methods for solving the supertree problem have been proposed, but the search for a quick and accurate method is still ongoing. An existing approach to solving computationally difficult problems is declarative programming, where one specifies the properties of a solution rather than the algorithm used to solve the problem. Answer set programming (ASP) is a form of declarative programming. This work presents two different ASP encodings for the supertree construction problem. Both encodings share a common subprogram to generate arbitrary ordered tree structures. Their objective functions are different, but they are both based on the principle of representing the source trees as multisets of subtree structures, and maximizing the number of such structures appearing in the supertree. The encodings were applied on a real-world dataset of phylogenetic trees of cats (Felidae). One of the encodings turned out to be too slow. The other, more promising encoding produced supertrees that were compared with recent supertrees computed for the same dataset using the field standard method, matrix representation with parsimony (MRP). The quality, assessed using three different metrics, was similar. It may be possible to improve on the computational performance. Additionally, some current limitations of the better-performing encoding are identified, with an initial suggestion for mitigating these. These provide avenues for future work. |
| ED: | 2015-08-16 |
INSSI tietueen numero: 51995
+ lisää koriin
INSSI