本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
背景最佳匹配圖（BMG）是一類彩色有向圖，自然出現在數學系統發育學中，作為多個物種中成對最密切相關的基因的表示。一條弧將基因 x 與來自另一個物種（頂點顏色）Y 的基因 y 連接起來，只要它是 x 的系統發育最接近的親戚之一。 BMG 可以藉助基因序列之間的相似性測量來近似，儘管並非沒有錯誤。因此，經驗估計通常會違反 BMG 的理論特性。對應的圖形編輯問題可用於指導最佳匹配資料的糾錯。由於 BMG 的弧集修改問題是 NP 完全的，因此如果要將 BMG 用於生物序列資料的實際分析，則需要有效的啟發式方法。結果由於 BMG 具有在基因組上定義的某組有根三元組（三個頂點上的二叉樹）的一致性方面的特徵，因此我們考慮對三元組進行操作的啟發式方法。作為替代方案，我們表明與集合劃分問題存在密切聯繫，該問題導致一類類似於 Aho 超樹演算法的自頂向下遞歸演算法，並產生 BMG 編輯演算法，這些演算法在使 BMG 保持不變的意義上是一致的。廣泛的基準測試表明，分區步驟的社群檢測演算法最適合 BMG 編輯。結論 可以以足夠的精度和效率來糾正雜訊的 BMG 數據，使 BMG 成為經典系統發育方法的有吸引力的替代方法。