Wotzlaw, Andreas, Speckenmeyer, Ewald and Porschen, Stefan (2012). A Satisfiability-based Approach for Generalized Tanglegrams on Level Graphs. In: Dagstuhl Seminar ”SAT Interactions”, 18. - 23.11.2012, Dagstuhl. Speech. (["eprint_fieldopt_ispublished_unpub" not defined])
|
PDF
Dagstuhl2012.pdf Download (287kB) | Preview |
Abstract
A tanglegram is a pair of (not necessarily binary) trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this work we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as the planar embedding and the second as the crossing minimization problem. We show that our satisfiability-based encoding of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts. Furthermore, we present an experimental comparison of our technique and several known heuristics for solving generalized binary tanglegrams, showing its competitive performance and efficiency and thus proving its practical usability.
Item Type: | Conference or Workshop Item (Speech) | ||||||||||||||||
Creators: |
|
||||||||||||||||
URN: | urn:nbn:de:hbz:38-550390 | ||||||||||||||||
Date: | November 2012 | ||||||||||||||||
Publisher: | Leibniz-Zentrum für Informatik GmbH | ||||||||||||||||
Place of Publication: | Schloss Dagstuhl | ||||||||||||||||
Language: | English | ||||||||||||||||
Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||||||||||
Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||||||||||
Subjects: | Data processing Computer science | ||||||||||||||||
Event Type: | Conference | ||||||||||||||||
Refereed: | No | ||||||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/55039 |
Downloads
Downloads per month over past year
Export
Actions (login required)
View Item |