Reconstructing weighted phylogenetic trees and phylogenetic networks using answer set programming

Abstract

Türlerin tarihsel evrim ilişkileri filogenetik ağaç olarak modellenebilir. Buağacların yaprakları türleri, aradaki düğümleri ataları ve kenarları genetik ilişkileri temsil eder. Türler arasında ödünç alma olduğu durumda, filogenetikağaçlara bu tür ilişkileri gösteren az sayıda kenar eklenerek, filogenetik ağlaradönuştürülebilirler. Ancak verilen bir tür ailesi için oldukça fazla olası ağaçve ağ olabilir ve bu ağaçları otomatik olarak analiz edebilecek bir sistemmevcut değil. Bu tez, çözüm kümesi programlama (ASP) kullanarak ağırlıklıfilojeni ve filogenetik ağ hesaplamak amacıyla yeni hesaplama yöntemlerive yazılım sistemleri geliştirerek filogenetik çalışmalarındaki bu ihtiyacıkarşılamaktadır. Ağırlıklı filojeni hesaplamasının arkasındaki genel fikir, birfilojeninin ve filogenetik ağin ne kadar makul olduğunu gösteren bir ağırlıkfonksiyonu kullanarak belirli bir ağırlığın üzerindeki filojenileri ve filogenetikağları ASP çözücülerini kullanarak hesaplamak.Bu tez kapsamında, uyumluluk kriterine göre ağırlıklı filojeni ve filogenetikağaç çıkarımı ile ilgili hesaplama problemlerini inceledik, bu problemlerinhesaplama karmaşıklığını analiz ettik. Ağırlıklı filojenileri ve filogenetikağları hesaplamak için iki tip (gösterime dayalı ve aramaya dayalı) ASP'ye dayalı hesaplama yöntemi geliştirdik. Bu yöntemlerden yararlanarak,büyük veriler üzerinde filojeni çıkarımı yapmak için böl-ve-yönet yönteminedayanan yeni bir algoritma geliştirdik. Bu algoritmaya dayalı yazılım sistemlerigeliştirdik: ağırlıklı filojeni çıkarımı ve analizi yapan Phylo-ASP,ve ağırlıklı filogenetik ağ çıkarımı yapan PhyloNet-ASP. İki gerçek veriüzerinden (Hint Avrupa dilleri ve Türkiye'deki meşe ağaçları) yaptığımıztestler ile yöntemlerimizin ve yazılım sistemlerimizin etkinliğini gösterdik.Bunların yanında, yöntemlerimizi ASP'de ağırlıklı çözümler bulacak şekildegenelleştirdik ve bir ASP çözücüyü (clasp-w) bu yöntemlere uygun bir şekildedeğiştirerek birçok ASP uygulaması için yararlı bir araç sağladık.

Evolutionary relationships between species can be modeled as a tree(called a phylogeny) whose nodes represent the species, internal vertices representtheir ancestors and edges represent genetic relationships. If there areborrowings between species, then a small number of edges that denote suchborrowings can be added to phylogenies turning them into (phylogenetic)networks. However, there are too many such trees/networks for a given familyof species but no phylogenetic system to automatically analyze them. Thisthesis fulfills this need in phylogenetics, by introducing novel computationalmethods and tools for computing weighted phylogenies/networks, using AnswerSet Programming (ASP). The main idea is to define a weight functionfor phylogenies/networks that characterizes their plausibility, and to reconstructphylogenies/networks whose weights are over a given threshold usingASP solvers.We have studied computational problems related to reconstructing weightedphylogenies/networks based on the compatibility criterion, analyzed theircomputational complexity, and introduced two sorts of ASP-based methods(representation-based and search-based) for computing weighted phyloiiigenies/networks. Utilizing these methods, we have introduced a novel divideand-conquer algorithm for computing large weighted phylogenies, and implementeda phylogenetic system (Phylo-ASP) based on it. We have alsoimplemented a phylogenetic system (PhyloNet-ASP) for reconstructingweighted networks. We have shown the applicability and the efectiveness ofour methods by performing experiments on two real datasets: Indo Europeanlanguages, and Quercus species in Turkey. Moreover, we have extended ourmethods to computing weighted solutions in ASP and modified an ASP solveraccordingly, providing a useful tool (clasp-w) for various ASP applications.