本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
Fitch 圖 G = (X, E) 是由具有葉集 X 的 {empty set, 1}-edge-labeled root trees T 解釋的有向圖：當且僅當 T 中連接 x 和 y 的最後一個公共祖先 lca(x, y) 與 y 的唯一路徑包含至少一個帶有標籤的邊角時，存在標籤「1 角時，存在於 y 的唯一路徑。在實踐中，Fitch 圖表示異種學關係，即基因對 x 和 y 沿著從 lca(x, y) 到 y 的路徑發生水平基因轉移。在本貢獻中，我們概括了 Fitch 圖的概念，並考慮配備邊緣標記 lambda 的樹 T：E -> P(M)，為每個邊緣分配 M 種顏色的子集 M' 。給定這樣一棵樹，我們可以導出映射 epsilon((T,lambda)) （或等效地一組不一定不相交的二元）。關係），使得 i 是 ((T,lambda))(x, y) 的元素（或等效地 (x, y) 是 R-i 的元素），其中 x, y 是 X 的元素，當且僅當存在至少一條顏色為 i 從 lca(x, y) 到 y 的邊。這裡考慮的中心問題：給定的 epsilon 是 Fitch 映射嗎，即是否存在帶有邊標記的樹 (T, lambda) epsilon((T,lambda)) = epsilon，從而解釋 epsilon？ 在這裡，我們根據某些鄰域和禁止子圖提供了 Fitch 映射的表徵。此外，我們還表明解釋 Fitch 映射的最小解析樹是唯一的（直到同構）。此外，我們提供了一個多項式時間演算法來確定 epsilon 是否是 Fitch 映射，並且在肯定的情況下構造到同構）解釋 epsilon 的獨特最小解析樹（T*、lambda*） (C) 2020 Elsevier B.V. 保留所有權利。