论文标题
广义惠誉图III：对称的惠誉图和一组对称二进制关系，这些关系由未根的边缘标记树解释
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
论文作者
论文摘要
从标记的植根树中得出的二进制关系在数学生物学中起着进化关系的形式模型，在数学生物学中起着导入作用。 （对称的）惠誉关系正式将Xenology作为基因对成对，至少是一个水平转移事件。 As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps $\varepsilon$ that assign a subset of colors to each pair of vertices in $X$ and that can be explained by a tree $T$ with edges that are labeled with subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$ if and only if $m$ appears in a label along the unique path $ x $和$ y $之间的$ t $。我们首先给出单色案例的替代表征，然后根据一组四重奏组的兼容性给出对称惠誉地图的表征。我们表明对对称的惠誉地图的识别是NP完整的。在有限的情况下，$ | \ varepsilon（x，y）| \ leq 1 $问题变成多项式，因为这样的地图与单色fitch映射类别相吻合，其图形表述的绘制形式精确形成了一类完整的多目标图。
Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps $\varepsilon$ that assign a subset of colors to each pair of vertices in $X$ and that can be explained by a tree $T$ with edges that are labeled with subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$ if and only if $m$ appears in a label along the unique path between $x$ and $y$ in $T$. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where $|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.
