Optimizing Phylogenetic Supertrees Using Answer Set Programming

Laura Koponen, Emilia Oikarinen, Tomi Janhunen, Laura Kristina Säilä-Corfe

Forskningsoutput: TidskriftsbidragArtikelVetenskapligPeer review

Sammanfattning

The supertree construction problem is about combining several phylogenetic
trees with possibly conflicting information into a single tree that has all the
leaves of the source trees as its leaves and the relationships between the
leaves are as consistent with the source trees as possible. This leads to an
optimization problem that is computationally challenging and typically
heuristic methods, such as matrix representation with parsimony (MRP), are
used. In this paper we consider the use of answer set programming to solve the
supertree construction problem in terms of two alternative encodings. The first
is based on an existing encoding of trees using substructures known as
quartets, while the other novel encoding captures the relationships present in
trees through direct projections. We use these encodings to compute a
genus-level supertree for the family of cats (Felidae). Furthermore, we compare
our results to recent supertrees obtained by the MRP method.
Originalspråkengelska
TidskriftTheory and Practice of Logic Programming
Volym15
Utgåva4-5
Sidor (från-till)604-619
Antal sidor16
ISSN1471-0684
DOI
StatusPublicerad - jul 2015
MoE-publikationstypA1 Tidskriftsartikel-refererad

Vetenskapsgrenar

  • 1171 Geovetenskaper

Citera det här

@article{23bf2dfb213e43f980f92fad5d20c67b,
title = "Optimizing Phylogenetic Supertrees Using Answer Set Programming",
abstract = "The supertree construction problem is about combining several phylogenetictrees with possibly conflicting information into a single tree that has all theleaves of the source trees as its leaves and the relationships between theleaves are as consistent with the source trees as possible. This leads to anoptimization problem that is computationally challenging and typicallyheuristic methods, such as matrix representation with parsimony (MRP), areused. In this paper we consider the use of answer set programming to solve thesupertree construction problem in terms of two alternative encodings. The firstis based on an existing encoding of trees using substructures known asquartets, while the other novel encoding captures the relationships present intrees through direct projections. We use these encodings to compute agenus-level supertree for the family of cats (Felidae). Furthermore, we compareour results to recent supertrees obtained by the MRP method.",
keywords = "1171 Geosciences",
author = "Laura Koponen and Emilia Oikarinen and Tomi Janhunen and S{\"a}il{\"a}-Corfe, {Laura Kristina}",
year = "2015",
month = "7",
doi = "10.1017/S1471068415000265",
language = "English",
volume = "15",
pages = "604--619",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "4-5",

}

Optimizing Phylogenetic Supertrees Using Answer Set Programming. / Koponen, Laura; Oikarinen, Emilia; Janhunen, Tomi; Säilä-Corfe, Laura Kristina.

I: Theory and Practice of Logic Programming, Vol. 15, Nr. 4-5, 07.2015, s. 604-619.

Forskningsoutput: TidskriftsbidragArtikelVetenskapligPeer review

TY - JOUR

T1 - Optimizing Phylogenetic Supertrees Using Answer Set Programming

AU - Koponen, Laura

AU - Oikarinen, Emilia

AU - Janhunen, Tomi

AU - Säilä-Corfe, Laura Kristina

PY - 2015/7

Y1 - 2015/7

N2 - The supertree construction problem is about combining several phylogenetictrees with possibly conflicting information into a single tree that has all theleaves of the source trees as its leaves and the relationships between theleaves are as consistent with the source trees as possible. This leads to anoptimization problem that is computationally challenging and typicallyheuristic methods, such as matrix representation with parsimony (MRP), areused. In this paper we consider the use of answer set programming to solve thesupertree construction problem in terms of two alternative encodings. The firstis based on an existing encoding of trees using substructures known asquartets, while the other novel encoding captures the relationships present intrees through direct projections. We use these encodings to compute agenus-level supertree for the family of cats (Felidae). Furthermore, we compareour results to recent supertrees obtained by the MRP method.

AB - The supertree construction problem is about combining several phylogenetictrees with possibly conflicting information into a single tree that has all theleaves of the source trees as its leaves and the relationships between theleaves are as consistent with the source trees as possible. This leads to anoptimization problem that is computationally challenging and typicallyheuristic methods, such as matrix representation with parsimony (MRP), areused. In this paper we consider the use of answer set programming to solve thesupertree construction problem in terms of two alternative encodings. The firstis based on an existing encoding of trees using substructures known asquartets, while the other novel encoding captures the relationships present intrees through direct projections. We use these encodings to compute agenus-level supertree for the family of cats (Felidae). Furthermore, we compareour results to recent supertrees obtained by the MRP method.

KW - 1171 Geosciences

U2 - 10.1017/S1471068415000265

DO - 10.1017/S1471068415000265

M3 - Article

VL - 15

SP - 604

EP - 619

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 4-5

ER -