本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
來自標記有根樹的二元關係作為演化關係的形式模型在數學生物學中發揮重要作用。 （對稱的）Fitch 關係將異種學形式化為由至少一個水平轉移事件分隔的基因對。作為自然概括，我們考慮對稱 Fitch 圖，即對稱圖 epsilon，它為 X 中的每對頂點分配顏色子集，並且可以用帶有用顏色子集標記的邊的樹 T 來解釋，因為當且僅當 m 沿著 T 中 x 和 y 之間的唯一路徑出現在標籤中時，顏色 m 才會出現在 silonx,x。我們首先給出單色情況的替代表徵，然後給出根據一組特定四重奏的兼容性來表徵對稱 Fitch 映射。我們證明對稱 Fitch 圖的辨識是 NP 完全的。在垂直條 epsilon(x, y)垂直條 <= 1 的受限情況下，問題變成多項式，因為此類圖與單色 Fitch 圖的類別一致，其圖表示恰好形成完整多部分圖的類別。