本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
推斷水平基因轉移（HGT）的幾種隱式方法集中在僅在基因所在的兩個物種分歧之後才分歧的基因對。這種情況定義了圖的邊集，即後期分歧時間（LDT）圖，其頂點對應於按其物種著色的基因。我們在寬鬆場景的設定中研究這些圖，即包含文獻中重複-轉移-遺失場景的所有常用變異體的演化場景。我們將 LDT 圖描述為正確的頂點顏色圖的子類，並提供多項式時間識別演算法以及構建解釋給定 LDT 的寬鬆場景的演算法。 LDT 圖中的一邊意味著兩個對應的基因被至少一個 HGT 事件分開。然而，反之則不然。我們證明了完整的異種關係由 rs-Fitch 圖描述，即滿足頂點著色約束的完整多部分圖。這類頂點彩色圖也可以在多項式時間內辨識。我們最終借助對各種重複、遺失和 HGT 事件的進化場景的模擬，解決了「LDT 圖中包含多少有關所有 HGT 事件的資訊」的問題。特別是，我們證明了一種簡單的貪婪圖編輯方案可用於有效檢測隱式包含在 LDT 圖中的 HGT 事件。