Reconstructing weighted phylogenetic trees and phylogenetic networks using answer set programming

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

[thumbnail of DuyguCakmak.pdf] PDF
DuyguCakmak.pdf

Download (1MB)

Abstract

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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 14 Feb 2013 17:20
Last Modified: 26 Apr 2022 09:57
URI: https://research.sabanciuniv.edu/id/eprint/21438

Actions (login required)

View Item
View Item