论文标题
绘制基于树的系统发育网络，交叉数量最少
Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings
论文作者
论文摘要
在系统发育学中，基于树木的网络用于建模和可视化物种的进化史，其中发生了网状事件（例如水平基因转移）。正式地，基于树的网络$ n $由系统发育树$ t $（一个生根，二进制，叶子标记的树）和所谓的网状边缘组成，跨越$ t $的边缘。通常，通过将$ t $向下绘制$ t $和平面边缘以及具有几种不同样式之一的网状边缘来可视化。一种美学标准是最大程度地减少树边缘和网状边缘之间的交叉数量。此优化问题尚未研究。我们表明，如果绘制网状边缘的X-孔酮，则该问题是NP完整的，但可以在网状边缘数量中进行固定参数。另一方面，如果绘制了网状边缘，则像“耳朵”一样，可以在二次时间内解决交叉最小化问题。
In phylogenetics, tree-based networks are used to model and visualize the evolutionary history of species where reticulate events such as horizontal gene transfer have occurred. Formally, a tree-based network $N$ consists of a phylogenetic tree $T$ (a rooted, binary, leaf-labeled tree) and so-called reticulation edges that span between edges of $T$. The network $N$ is typically visualized by drawing $T$ downward and planar and reticulation edges with one of several different styles. One aesthetic criteria is to minimize the number of crossings between tree edges and reticulation edges. This optimization problem has not yet been researched. We show that, if reticulation edges are drawn x-monotone, the problem is NP-complete, but fixed-parameter tractable in the number of reticulation edges. If, on the other hand, reticulation edges are drawn like "ears", the crossing minimization problem can be solved in quadratic time.
