基因群組搜尋演算法

An Algorithm for Finding Gene Clusters

陳彥嘉(chen yan jia)

指導教授 ： 呂威甫

亞洲大學/資訊學院/生物資訊學系碩士班/碩士(2009年)

摘要

物種演化中大規模的演化事件，基因重組，改變了染色體上基因的順序。通常兩個親源接近的真核生物，有許多基因內容相同但順序的不同的染色體片段，稱為基因群組。基因群組可能是共同祖先演化之後的結果，也可能表現共同調控的現象。其對於演化樹的建構與基因功能的預測都扮演了重要的角色。因此基因群組的尋找，在比較基因體學的研究中，是一個重要的問題。本論文將以近似共同區間討論基因群組的尋找的問題，也就是，基因體將以字串表示，同時近似共同區間將以集合間的對稱差定義。我們提出了一個O(Ln3)的演算法尋找L條長度為n的基因體間的基因群組。

關鍵字

比較基因體學 ； 基因重組 ； 基因群組 ； 共同區間

並列摘要

Genomes evolve through large-scale events, known as genome rearrangements, that reorganize the gene order in the chromosome. Usually two closely related prokaryotes share many gene clusters, which are sets of genes in close proximity to each other, but not necessarily contiguous nor in the same order in both genomes. Gene clusters could result from evolution of common ancestors, and could represent phenomenon of co-expression. It plays an important role in the construction of phylogenetic trees and prediction of gene functions. Thus, finding gene clusters is an important problem in comparative genomics. In this paper, we will discuss gene clusters finding problem using model of approximate common intervals, that is, genomes are considered as strings and approximate common intervals are defined as set symmetric difference. We present an O(Ln3) algorithm to find gene clusters among L genomes of length n.

並列關鍵字

comparative genomics ； genome rearrangement ； gene cluster ； common interval

參考文獻

[1] Amir, A., Apostolico, A., Landau, G.M., Satta, G, Efficient text fingerprinting viaParikh mapping, J. Discrete Algorithms, 26: 1–13, 2002.

[2] Amir, A., Gasieniec, L., Shalom, R, Improved approximate common interval. Information Processing Letters, 103: 142-149, 2007.

[3] B’erard, S., Bergeron, A., Chauve, C, Conserved structures in evolution scenarios. Lecture Notes in Bioinformatics, 3388: 1–15, 2005.

[4] B’erard, S., Bergeron, A., Chauve C., Paul C, Perfect sorting by reversals is not always difficult. Lecture Notes in Bioinformatics, 3692: 228–238, 2005.

[5] Bergeron, A., Blanchette, M., Chateau, A., Chauve, C, Reconstructing ancestral gene orders using conserved intervals. Lecture Notes in Bioinformatics, 3240: 14–25, 2004.