基因體重組問題---理論與應用

Abstract

隨著大量基因體序列的出現，基因體重組的研究在計算生物及生物資訊的領域上愈來愈受到重視。研究基因體重組的主要目的是藉由比較基因體上的基因次序以衡量出兩個物種之間的演化差異。目前有許多會改變基因次序的重組已被提出，如翻轉(Reversals)、移位(Transpositions)、區段互換(Block-Interchange)、分裂(Fissions)、融合(Fusions)、易位(Translocations)等等。給定二個基因體上基因次序的排列，『基因重組問題』是要去計算出一條最短的重組序列可以把其中一組基因體上的基因次序轉換成另外一組基因體的基因次序，其中所需用到的最少重組個數就被稱為『重組距離』。先前有關這個問題的大部份研究與成果都把焦點放在如何利用圖論的(graph-based)方法與分析設計出有效率的(近似)演算法。然而，大部份這些研究所設計出來的演算法與所需的資料結構都太過複雜故不易寫成程式。過去這二、三年來，我們成功地利用代數排列群(Permutation Groups)的特性與方法設計出較簡單且有效率的演算法解決區段互換的基因重組問題及融合+分裂+區段互換的基因重組問題。因此在這個計劃提案中，我們將繼續去研究如何把這個代數方法應用到其它的基因重組問題如翻轉、移位(可被視為區段互換的特例)、易位(可被視為融合與分裂的延伸)以及他們之間可能的組合。值得注意的是上述基因重組問題的研究皆需要一個前提，即參與比較的基因得是基因體之間相同且唯一(不重複)的基因(即1-1的直系同源基因；1-1 Orthologs)才行；然而一個基因在物種的基因體上可能會出現好幾份(即共生同源基因；Paralogs)。在這個情況之下，生物學家為了要能夠繼續使用現有且針對1-1直系同源基因的基因體所設計出來的演算法，他們經常被逼不得不刪除掉在基因體上一些重複的共生同源基因。這樣妥協對於小型基因體(如病毒和粒腺體)的演化樹建構還能行得通，但不可必免地對於一些較複雜的基因體(如原核與真核生物)其正確性便會因為資料的刪除而所有失真。Sankoff (1999)最先探討這個問題並定義出一個稱之為『廣義的基因重組問題』，其目的是要去刪除每一個基因家族中重複的基因直到只剩一個，並且使得經過刪除後剩餘的二個基因體之間的重組距離為最小。目前這部份的研究成果還很少，除了已經知這個問題在考量斷點(Breakpoint)距離或翻轉距離最佳化的時候是一個NP-hard的問題。因此在本計劃提案中我們也要去研究與探討要最佳化移位、區段互換或是易位距離的情況下，廣義的基因重組問題是否仍是一個NP-hard的問題？或是可在多項式時間內被解決的問題？最後，我們也將對本計劃未來執行中所設計出來的演算法給予程式化，並整合我們之前已發展出來的程式(如ROBIN, SPRING和FFBI)成為一個網路伺服器以協助生物學家能依據基因重組的分析去建構出一些物種之間的演化關係。