Abstract
次世代定序技術以日益漸低的成本快速地產生大量的基因體草圖。然而，這些基因體草圖通常只被部份定序成為一群未組裝好的基因體連續片段，這些未組裝好的連續片段是無法直接被現存研究基因重組與種族樹重建的演算法所使用。在本論文中，我們使用加權的反轉與區塊互換距離來研究單邊區塊排序的問題：給予一個部分組裝的基因體 π 與一個完全組裝的基因體 σ，該問題的目的是要找到一個最佳次序來組裝（即排序與決定方向）π 中的連續片段，使得 π 的組裝好的連續片斷與 σ 之間利用加權的反轉與區塊互換所衡量出來的基因體重組距離為最小，其中反轉與區塊互換的權重比為 1:2。除了基因體重組與種族樹重建之外，單邊區塊排序問題特別地在基因體重新定序上有很好的應用，因為根據一個參考基因體 σ 他的演算法就能夠被用來組裝一個基因體草圖 π 的連續片段。利用排列群，我們設計出一個有效率的演算法能夠在 O(δn) 的時間內解決單邊區塊排序的問題，其中 n 是基因的個數，δ 是把組裝好的基因體 π 轉換成基因體 σ 所需的反轉與區塊轉換的個數。除此之外，我們也證明出基因草圖的組裝在 O(n) 的時間內完成，而且組裝好的基因體與另一個完全組裝的基因體之間的加權基因體重組距離也能夠在 O(n) 的時間內被事先計算出來。最後，我們將我們的演算法實作成程式，並且利用模擬的資料去比較它與現存相似功能的工具 SIS 在利用參考基因體去組裝基因草圖連續片斷的準確度表現，其中SIS是根據一個只考慮反轉的啟發式演算法所實作出來的工具。我們的實驗結果顯示出當在 π 的完整基因體與 σ 之間參與基因體重組事件的反轉與易位個數增加時，我們的程式在準確度的表現是比 SIS 好。特別地，如果有更多的易位參與在基因重組事件中，那麼我們的程式與SIS之間在準確度表現上的差距就會逐漸增大。