Reconstructing weighted phylogenetic trees and phylogenetic networks using answer set programming

Warning The system is temporarily closed to updates for reporting purpose.

Çakmak, Duygu (2010) Reconstructing weighted phylogenetic trees and phylogenetic networks using answer set programming. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: (Table of Contents)


Evolutionary relationships between species can be modeled as a tree (called a phylogeny) whose nodes represent the species, internal vertices represent their ancestors and edges represent genetic relationships. If there are borrowings between species, then a small number of edges that denote such borrowings can be added to phylogenies turning them into (phylogenetic) networks. However, there are too many such trees/networks for a given family of species but no phylogenetic system to automatically analyze them. This thesis fulfills this need in phylogenetics, by introducing novel computational methods and tools for computing weighted phylogenies/networks, using Answer Set Programming (ASP). The main idea is to define a weight function for phylogenies/networks that characterizes their plausibility, and to reconstruct phylogenies/networks whose weights are over a given threshold using ASP solvers. We have studied computational problems related to reconstructing weighted phylogenies/networks based on the compatibility criterion, analyzed their computational complexity, and introduced two sorts of ASP-based methods (representation-based and search-based) for computing weighted phylogenies/networks. Utilizing these methods, we have introduced a novel divide-and-conquer algorithm for computing large weighted phylogenies, and implemented a phylogenetic system (Phylo-ASP) based on it. We have also implemented a phylogenetic system (PhyloNet-ASP) for reconstructing weighted networks. We have shown the applicability and the effectiveness of our methods by performing experiments on two real datasets: Indo European languages, and Quercus species in Turkey. Moreover, we have extended our methods to computing weighted solutions in ASP and modified an ASP solver accordingly, providing a useful tool (CLASP-W) for various ASP applications.

Item Type:Thesis
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
ID Code:21438
Deposited By:IC-Cataloging
Deposited On:14 Feb 2013 17:20
Last Modified:25 Mar 2019 17:05

Repository Staff Only: item control page