论文标题
2色最佳匹配图的结构
The Structure of 2-Colored Best Match Graphs
论文作者
论文摘要
计算生物学的最新研究集中在一个2色的挖掘器上，称为2色最佳匹配图，这自然来自根生系统发育树。实际上，此类图的定义特性是不寻常的，一个自然的问题是它们是否也具有非常适合结构图理论的属性。在本文中，我们证明了2色最佳匹配图的一些基本取向的二分图为无环，我们指出，可以有效地使用出现的拓扑排序来构建2色最佳匹配图的新家族。
Recent investigations in computational biology have focused on a family of 2-colored digraphs, called 2-colored best match graphs, which naturally arise from rooted phylogenetic trees. Actually the defining properties of such graphs are unusual, and a natural question is whether they also have properties which well fit in structural graph theory. In this paper, we prove that some underlying oriented bipartite graphs of a 2-colored best match graph are acyclic and we point out that the arising topological ordering can efficiently be used for constructing new families of 2-colored best match graphs.
