论文标题
平面根源系统发育网络
Planar Rooted Phylogenetic Networks
论文作者
论文摘要
根源的系统发育网络是带有单根根的定向无环图，其水槽对应于一组物种。由于此类网络对于表示经历了网状演化的物种的演变很有用，因此人们对开发构造它们背后的理论和算法引起了极大的兴趣。但是，与进化树不同，这些网络可以是高度非平面的，这可能会使它们难以可视化和解释。在这里，我们研究了平面生根的系统发育网络和算法的性质，以决定是否具有某些特殊的平面性能。特别是，我们引入了平面生根系统发育网络的三个自然子类，并表明它们形成了层次结构。此外，对于众所周知的K级网络，我们表明级别1，-2，-3网络始终是外部，终端和向上平面的，而该级别4网络不一定是平面。最后，我们表明，当且仅当它是金字塔时，常规网络是终端平面。我们的结果利用了高度发达的平面挖掘领域，我们认为系统发育网络和平面图之间的联系应在将来对开发新方法来构建和可视化系统发育网络的未来有用。
A rooted phylogenetic network is a directed acyclic graph with a single root, whose sinks correspond to a set of species. As such networks are useful for representing the evolution of species that have undergone reticulate evolution, there has been great interest in developing the theory behind and algorithms for constructing them. However, unlike evolutionary trees, these networks can be highly non-planar, which can make them difficult to visualise and interpret. Here we investigate properties of planar rooted phylogenetic networks and algorithms for deciding whether or not rooted networks have certain special planarity properties. In particular, we introduce three natural subclasses of planar rooted phylogenetic networks and show that they form a hierarchy. In addition, for the well-known level-k networks, we show that level-1, -2, -3 networks are always outer, terminal, and upward planar, respectively, and that level-4 networks are not necessarily planar. Finally, we show that a regular network is terminal planar if and only if it is pyramidal. Our results make use of the highly developed field of planar digraphs, and we believe that the link between phylogenetic networks and planar graphs should prove useful in future for developing new approaches to both construct and visualise phylogenetic networks.
