Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation
Generalized k-ary tanglegrams on level graphs: A satisfiability-based approach and its evaluation
复制标题
DOI：
10.1016/j.dam.2012.05.028
复制
发表时间：
2012-11-01
影响因子：
1.1
通讯作者：
Porschen, Stefan
中科院分区：
文献类型：
--
作者：
Wotzlaw, Andreas;Speckenmeyer, Ewald;Porschen, Stefan
缠结图是同一组叶子上的一对（不一定是二叉）树，这两棵树的叶子由一条边连接起来。缠结图在计算生物学中被广泛用于比较物种的进化史。在这项工作中，我们提出了两个相关的关于缠结图的组合嵌入问题的cnf公式。第一个问题称为平面嵌入问题，第二个问题称为交叉最小化问题。我们表明，我们基于可满足性的编码可以处理更一般的情况，有两个以上的树，不一定是二叉树或完全树，树定义在任意的叶子集合上，并允许改变它们的布局。此外，我们将我们的技术与几种已知的求解广义二元缠结图的启发式方法进行了实验比较，显示了其具有竞争力的性能和效率，从而证明了其实际可用性。(C) 2012 Elsevier B.V.版权所有
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. (C) 2012 Elsevier B.V. All rights reserved.