Abstract
比對多種生物之基因組是一種發掘新生物資訊的重要方法，在本論文中，我們討論兩個從基因比對而衍生出來的問題，一個是基因隊問題，另一個是共有連通問題。 基因隊指的是一群基因同時出現在兩個以上不同的物種，這群基因在各物種染色體上的順序雖然可能不相同，但相鄰的兩基因距離總是不超過某個限制。基因隊問題要找出複數基因組中的所有基因隊，Béal等人 [2] 對於這個問題給了一個O(kn(log n)^2)時間的演算法，其中k代表有幾組基因組，n代表有幾種不同的基因。在本論文中，我們提出了一個O(knlog d)時間的改進演算法，其中d <= n表示最後找出來的基因隊數目，這個演算法非常的簡單且實作上非常有效率，我們也討論如何在同樣的時間下把問題延伸到環狀染色體。 用F = {G1 = (V, E1), …, Gk = (V, Ek)}代表k個定義在相同點集合上的圖形，F的一個共有連通元件是V的一個最大子集合S，且由S所產生出的子圖在各個圖Gi in F中都是連通的，共有連通問題要找出F中所有的共有連通元件，這是一個廣義的基因隊問題。本論文我們考慮每個Gi都是區間圖的情況，在這情況下，Coulon和Raffinot [8]有一個O(m + knlog n)時間的演算法，其中m = sum1<=i<=k |Ei|且n = |V|。除此之外，當k個區間圖是用k組n個區間的集合來表達時，Coulon和Raffinot [8] 在O(n(log n)^2)的時間內解掉了這個問題。在本論文中，當輸入是k組n個區間的集合時，我們提出了一個O(knlog n)時間的改進演算法，並且我們也指出如何擴展此演算法好在O(min{kn(k + log n), knlog nlog d})的時間內解掉k個環弧圖上的共有連通問題，其中d <= n代表最後找出來的共有連通元件數目。