本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
背景：最大配對問題 (MPP) 是生物資訊學中備受關注的一類組合優化問題的原型：給定任意兩對葉子 (x, y) 之間的路徑的任意系統發育樹 T 和權重 omega(xy)，最大化總權重的葉子對之間的邊不相交路徑的集合是什麼？前面已經描述了二元樹和相等權重的 MPP 的特殊情況；然而，解決通用 MPP 的演算法仍然缺失。結果：我們針對二元樹的特殊情況描述了一種相對簡單的動態規劃演算法。然後，我們表明，可以透過對某些輔助最大加權匹配問題的交錯解決方案以及這種動態規劃方法的擴展來處理多叉樹的一般情況，從而產生複雜性的總體多項式時間解決方案。 (n(4) log n) w.r.t.葉子的數量n。 C 實作的原始碼可以根據 GNU 公共授權從 取得。對於二元樹，我們也討論了 MPP 的幾種約束變體以及 MPP 機率版本的分區函數方法。結論：這裡介紹的演算法使得求解具有高度頂點的大樹的 MPP 成為可能。這在比較系統發育學領域具有實際意義，例如，在系統發育目標的背景下，即在資源有限的情況下收集資料。