Applications of heuristic search on phylogeny reconstruction problems

Abstract

Verilen bir tür ailesi için oluşturulan filojeniler veya evrim ağaçları bu türler arasındaki evrimsel ilişkileri gösterir. Ağacın yaprakları verilen türleri, ara düğümleri ortak ataları ve ayrıtları da genetik ilişkileri belirtir. Türler genom bilgileriyle tanımlanabilir ve türler arasındaki evrimsel ilişkiler bir genomu diğerine dönüştüren genom yeniden düzenleme olayları (mesela mutasyonlar) ile ölçülebilir. Genom verisinden filojeni çıkarımı yapmak için kullanılan yaklaşımlardan biri, türler arasındaki toplam evrimsel mesafeyi en aza indirgemeye çalışırken genom üçlüleri için ortanca genom problemi çözmek veya genom çiftleri için genom yeniden düzenleme problemi çözmektir.Bu tezde, yeniden filojeni kurma problemini çözmek amacıyla, gen tekrarı içermeyen aynı uzunluktaki dairesel genomlar için ortanca genom problemi çözümüne dayanan iki tane arama tabanlı algoritma geliştirdik ve gerçekledik.Algoritmalarımızın uygulanabilir ve etkili olduğunu gösterebilmek adına rastgele üretilmiş örnekler ve Metazoa'ya ait türlerin mitokondri genomlarını ve Campanulaceae ailesine ait türlerin kloroplast genomlarını içeren iki gerçek veri kümesiyle algoritmalarımızı sınadık.

Phylogenies or evolutionary trees for a given family of species show the evolutionary relationships between these species. The leaves denote the given species, the internal nodes denote their common ancestors and the edges denote the genetic relationships. Species can be identified by their whole genomes and the evolutionary relations between species can be measured by the number of rearrangement events (i.e. mutations) that transform one genome into another. One approach to infer phylogeny from genomic data is by solving median genome problems for three genomes, or the genomerearrangement problem for pairs of genomes, while trying to minimize the total evolutionary distance among the given species.In this thesis, we have developed and implemented three search based algorithms for phylogeny reconstruction problem based on solving median genome problems for circular genomes of the same length without gene duplication.In order to show applicability and effectiveness of our algorithms, we have tested them with randomly generated instances and two real data sets: mitochondrial genomes of Metazoa and chloroplast genomes of Campanulaceae.