Optimizing phylogenetic supertrees using answer set programming

DOI10.1017/S1471068415000265MaRDI QIDQ4593001zbMATH OpenFDO

Authors Laura Koponen, Emilia Oikarinen, Tomi Janhunen, Laura Säilä

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05272

zbMATH Keywords

projectionsquartetsanswer set programmingfelidaephylogenetic supertree

Mathematics Subject Classification ID

Problems related to evolution (92D15) Logic programming (68N17)

Abstract: 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.

Recommendations

• Phylogenetic supertrees. Combining information to reveal the tree of life
• Constructing rooted supertrees using distances
• scientific article; zbMATH DE number 1746436
• scientific article; zbMATH DE number 1974598
• An efficient algorithm for supertrees

Cites work

• scientific article; zbMATH DE number 5914356 (Why is no real title available?)
• scientific article; zbMATH DE number 1974598 (Why is no real title available?)
• scientific article; zbMATH DE number 6747915 (Why is no real title available?)
• A few logs suffice to build (almost) all trees (I)
• A supertree method for rooted trees
• ASP at work: an ASP implementation of PhyloWS
• Advances in WASP
• Combinatorial optimization solutions for the maximum quartet consistency problem
• Constructing Camin-Sokal Phylogenies Via Answer Set Programming
• Improving the normalization of weight rules in answer set programs
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Inferring phylogenetic trees using answer set programming
• Knowledge Representation, Reasoning and Declarative Problem Solving
• New results on optimizing rooted triplets consistency
• Open-WBO: a modular MaxSAT solver
• Phylogenetic supertrees. Combining information to reveal the tree of life
• The Steiner problem in phylogeny is NP-complete
• The computational complexity of inferring rooted phylogenies by parsimony

Cited in

(11)

• Combinatorial optimization solutions for the maximum quartet consistency problem
• Stable-unstable semantics: Beyond NP with normal logic programs
• The Seventh Answer Set Programming Competition: Design and Results
• Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)
• scientific article; zbMATH DE number 7455719 (Why is no real title available?)
• Debugging non-ground ASP programs: technique and graphical tools
• Partial compilation of ASP programs
• Inferring phylogenetic trees using answer set programming
• Unsatisfiable core analysis and aggregates for optimum stable model search
• The External Interface for Extending WASP
• Constructing Camin-Sokal Phylogenies Via Answer Set Programming

Describes a project that uses

Uses Software

• Quartets MaxCut
• Open-WBO
• WASP
• PhyloWS
• Sat4j
• Potassco
• Gringo

This page was built for publication: Optimizing phylogenetic supertrees using answer set programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593001)