標題: 利用融合、分裂及區段互換探討基因重組之研究
On the Study of Genome Rearrangements using Fusions, Fissions and Block-Interchanges
作者: 王璻菁
Tsui Ching Wang
盧錦隆
Chin Lung Lu
生物資訊及系統生物研究所
關鍵字: 區段互換;融合;分裂;基因重組;block-interchange;fusion;fission;genome rearrangement
公開日期: 2004
摘要: 最近的研究顯示區段互換的基因體分析可用來衡量兩物種之間的演化距離。所謂的區段互換是一種新的全域型基因體重組,它的作用是把染色體上兩段不相交且任意長度的基因/標記區段做互換。這方面的研究導致需要去解決一種叫做區段互換排序的組合最佳化數學問題, 其目的是要去找出最少區段互換的次序把一條染色體的基因/標記次序轉成另一條染色體的基因/標記次序。之前,我們的研究團隊已設計出有效率的演算法可分別解決線性和環狀染色體之間的區段互換排序問題。在本論文中,我們利用這些演算法實作出一個叫做ROBIN的網站來分析兩條染色體之間區段互換的基因/標記的次序重組。使用者可輸入兩條或多條線性/環狀且細菌大小的染色體,輸入的染色體可為基因體的序列或是代表同源基因或相同標記無正負號的整數序列。為了測試ROBIN的實用性,我們利用它來偵測三種感染人類的弧菌病原體之間的演化距離關係。結果,我們的實驗跟先前其它研究團隊利用比較基因體的方法所得到的結果一致,這項研究成果顯示在弧菌物種間的演化過程中,區段互換的突變事件扮演著一個重要的角色。然而,對於含有多條染色體的基因體而言,它們之間的演化歷史必須還要考慮另外兩種染色體之間的突變事件即融合及分裂。所謂的融合事件是把兩條染色體融合成一條,而分裂事件是把一條染色體分裂成兩條。在本論文中,我們進一步的去研究含有區段互換、融合和分裂這三種突變事件的基因體重組問題,最後提出一個時間複雜度為O(n^2)的演算法,其可有效的計算出兩組環狀且多染色體的基因體之間所需最少上述三種突變次數,其中n表示兩組基因體之間共有的基因/標記的個數。
Analysis of genomes evolving block-interchanges has been studied recently for measuring the evolutionary distance between two organisms, where the block-interchanges are new kind of global rearrangement events that affect on a chromosome by swapping two non-intersecting intervals of gene/landmark orders of any length. Such a study leads to a combinatorial problem, called sorting by block-interchanges, which is to find to a minimum of block-interchanges needed to transform one chromosome into another. Lin et al. [Lin et al., 2005] have designed an efficient algorithm to solve the sorting by block-interchange problem on both cases of linear and circular chromosomes. In this thesis, we implement this algorithm into a web server, called ROBIN, for analyzing rearrangements of gene/landmark orders between two linear/circular chromosomal genomes via the block-interchange events. ROBIN takes two or more linear/circular bacterial-size chromosomes as an input, which can be either genomic sequences or unsigned integer sequences with each representing a homologous gene or identical landmark on all input chromosomes. For testing the applicability of ROBIN, we apply it to genomes of three human Vibrio pathogens for detecting the evolutionary relationships. Consequently, our experimental results coincide with the previous ones obtained by other communities using a comparative genomic approach, which implies that the block-interchange events seem to play a significant role in the evolution of Vibrio species. However, in the case of genomes consisting of multiple chromosomes, the evolutionary history must also consider chromosomal fusions and fissions, where a fusion event merges two chromosomes into one and a fission event splits a chromosome into two. Hence, in the thesis, we further study the genome rearrangement problem by fusions, fissions and block-interchanges between two circular multichromosomal genomes. Consequently, we propose an O(n2) time algorithm to efficiently compute a minimum series of fusions, fissions and block-interchanges required to transform one genome into another, where n is the number of genes/landmarks shared by the two genomes.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009251510
http://hdl.handle.net/11536/77492
Appears in Collections:Thesis


Files in This Item:

  1. 151001.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.