本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
相互最佳匹配圖 (RBMG) 是頂點彩色圖，其頂點代表基因以及基因所在物種的顏色。邊緣識別與潛在進化樹最密切相關的基因對。在實際應用中，這棵樹是未知的，RBMG 的邊緣是透過量化序列相似性來推斷的。由於數據中存在噪聲，這些經驗確定的圖通常違反了「生物學上可行」RBMG 的條件。因此，校正初始估計值在計算生物學中具有實際意義。這裡我們考慮刪除（最多刪除k條邊）和編輯（最多新增或刪除k條邊）問題。我們證明了從頂點彩色圖中獲取 RBMG 的刪除和編輯問題的決策版本是 NP 困難的。使用所謂的雙簇編輯的已知結果，我們表明 2 色圖的 RBMG 編輯問題是固定參數易於處理的。受限的 RBMG 類別出現在直系同源偵測。這些是具有特定類型頂點著色（稱為分層著色）的座標圖。我們證明，將頂點彩色圖（透過邊緣刪除或編輯）修改為具有 cograph 結構的 RBMG 或等效地，修改為分層彩色 cograph 的決策問題是 NP 完全的。