利用範例中斷點距離建構基因體規模的演化樹之研究

Abstract

隨著DNA定序技術的進步，越來越多物種的完整基因體序列變得更容易取得。因此，藉由比較物種基因體之間的基因次序所推測出來的基因體規模的演化樹，將有助於物種演化親屬關係的重建。在這篇論文中，我們研究如何利用兩兩物種之間基因次序的範例中斷點距離去建構出基因體規模的演化樹。給定兩組基因體之間共有基因的次序，其中每個基因出現的次數可能不只一次，對這種基因，我們可以刪除其他重複出現的地方而只保留其中一份，最後我們可以得到二組簡化的基因次序，其中每一個基因在序列中只出現一次。而所謂的範例中斷點距離被定義成在所有可能的簡化基因次序中，所得到的最小中斷點距離。 在這份研究中，我們首先改進之前計算範例中斷點距離的演算法，而這個演算法是結合分支界定與個個擊破的策略所設計出來的。接著，我們實作出這個演算法並且整合其他已有程式，例如：INPARANOID與PHYLIP等等，發展成一套網站伺服器的工具，我們稱之為EmBeDtree。除此之外，拿一些蛋白細菌與細胞的基因體來對EmBeDtree作測試，並且將畫出的基因體規模演化樹和其他的方法所畫出的演化樹視為參考樹作比較，實驗結果顯示，EmBeDtree建構出來的演化樹和參照樹之間有很高的相似度。這意味著範例中斷點距離是一個有用衡量方式，可以用來建構出物種之間的基因體規模的演化樹。

As more and more complete genomes of species are available, a genome-scale phylogenetic inference by comparing gene orders between species whole genomes can be useful for the reconstruction of the evolutionary relationships of species. In this thesis, we study the reconstruction of such genome-scale phylogenetic trees based on pairwise exemplar breakpoint distances between gene orders of species. Given the orders of multiple genes shared by two species genomes, the so-called exemplar breakpoint distance between two gene orders of two genomes is the smallest breakpoint distance between their reduced genomes that are obtained by deleting redundant copies of each gene in species genomes. In this study, we first modify a previous algorithm that is a combination of branch-and-bound and divide-and-conquer approaches to calculate the pairwise exemplar breakpoint distance. We then implement this algorithm as a web server, called EmBeDtree, by incorporating other programs, such as INPARANOID and PHYLIP. EmBeDtree takes as the input multiple species genomes and outputs a phylogenetic tree based on the pairwise exemplar breakpoint distances. In addition, we test our EmBeDtree by using some data sets of Proteobacterial genomes and cellular genomes and also compared their genome trees produced by our EmBeDtree with those reference trees created by other different approaches. The experimental results show that our genome trees are greatly consistent with the trees that were constructed by other approaches, suggesting that exemplar distance is a useful measure for the reconstruction of genome-scale phylogenetic tree.