@mastersthesis{duyguCakmak10,
  author = {Duygu Cakmak},
  title = {{Reconstructing Weighted Phylogenetic Trees
and Phylogenetic Networks Using Answer Set Programming}},
  school = {Sabanci University},
  address = {Istanbul, Turkey},
  year = {2010},
  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.}
}

{"_id":{"_str":"53424e050e946d920a000683"},"__v":8,"authorIDs":["545eb6896aaec20d23000936"],"author_short":["Cakmak, D."],"bibbaseid":"cakmak-reconstructingweightedphylogenetictreesandphylogeneticnetworksusinganswersetprogramming-2010","bibdata":{"bibtype":"mastersthesis","type":"mastersthesis","author":[{"firstnames":["Duygu"],"propositions":[],"lastnames":["Cakmak"],"suffixes":[]}],"title":"Reconstructing Weighted Phylogenetic Trees and Phylogenetic Networks Using Answer Set Programming","school":"Sabanci University","address":"Istanbul, Turkey","year":"2010","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.","bibtex":"@mastersthesis{duyguCakmak10,\n author = {Duygu Cakmak},\n title = {{Reconstructing Weighted Phylogenetic Trees\nand Phylogenetic Networks Using Answer Set Programming}},\n school = {Sabanci University},\n address = {Istanbul, Turkey},\n year = {2010},\n abstract = {Evolutionary relationships between species can be modeled as a tree\n(called a phylogeny) whose nodes represent the species, internal\nvertices represent their ancestors and edges represent genetic\nrelationships. If there are borrowings between species, then a small\nnumber of edges that denote such borrowings can be added to\nphylogenies turning them into (phylogenetic) networks. However,\nthere are too many such trees/networks for a given family of species\nbut no phylogenetic system to automatically analyze them. This\nthesis fulfills this need in phylogenetics, by introducing novel\ncomputational methods and tools for computing weighted\nphylogenies/networks, using Answer Set Programming (ASP). The main\nidea is to define a weight function for phylogenies/networks that\ncharacterizes their plausibility, and to reconstruct\nphylogenies/networks whose weights are over a given threshold using\nASP solvers.\n\nWe have studied computational problems related to reconstructing\nweighted phylogenies/networks based on the compatibility criterion,\nanalyzed their computational complexity, and introduced two sorts of\nASP-based methods (representation-based and search-based) for\ncomputing weighted phylogenies/networks. Utilizing these methods, we\nhave introduced a novel divide-and-conquer algorithm for computing\nlarge weighted phylogenies, and implemented a phylogenetic system\n(Phylo-ASP) based on it. We have also implemented a\nphylogenetic system (PhyloNet-ASP) for reconstructing weighted\nnetworks. We have shown the applicability and the effectiveness of\nour methods by performing experiments on two real datasets: Indo\nEuropean languages, and Quercus species in Turkey. Moreover, we have\nextended our methods to computing weighted solutions in ASP and\nmodified an ASP solver accordingly, providing a useful tool (Clasp-W)\nfor various ASP applications.}\n}\n\n\n","author_short":["Cakmak, D."],"key":"duyguCakmak10","id":"duyguCakmak10","bibbaseid":"cakmak-reconstructingweightedphylogenetictreesandphylogeneticnetworksusinganswersetprogramming-2010","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"mastersthesis","biburl":"http://cogrobo.sabanciuniv.edu/krrpublicationsnew.bib","downloads":0,"keywords":[],"search_terms":["reconstructing","weighted","phylogenetic","trees","phylogenetic","networks","using","answer","set","programming","cakmak"],"title":"Reconstructing Weighted Phylogenetic Trees and Phylogenetic Networks Using Answer Set Programming","year":2010,"dataSources":["tGZRHJKguQssAob5Z"]}