基因組Reversal-Transposition排序的快速計算研究.pdf

1、基因組重組是基因組改變基因排列順序的生化過程?；蚪M重組排序問題來源于基因組中基因排列順序的比較。其目標(biāo)是找到最短的重組操作序列，將一個基因組轉(zhuǎn)變?yōu)榱硪粋€基因組?；蚪M重組排序用于推斷生命因重組而演化的過程，基因組重組排序計算有助于確切分析疾病的致病原理，有助于快速診斷疾病以有效治療疾病，有助于精確設(shè)計醫(yī)藥的分子結(jié)構(gòu)，提高藥物療效。 一條染色體由一個基因序列組成，基因組是染色體的集合。可以將一次基因組重組看做改變基因排列順序的

2、一次操作。假設(shè)自然界總是選擇最省力的方式或以最快方式完成生命演化的，因此人們以重組操作次數(shù)最少為目標(biāo)，來計算一個基因組轉(zhuǎn)化為另一個基因組的重組操作序列作為基因組間的重組演化過程。Sankoff等人最早設(shè)計了基因組的翻轉(zhuǎn)（Reversal）和移位（Translocation）排序算法。 給定兩個基因組A，B，在規(guī)定了可以使用的操作之后，A，B之間的距離為從A轉(zhuǎn)換到B的最少變換操作次數(shù)。將求這些基因組之間的變換距離及變換序列的問題

3、稱為基因組重組排序問題。最基本的重組操作有三種：翻轉(zhuǎn)（reversal），移位（translocation）和轉(zhuǎn)位（transposition）。為了簡單，在討論基因組重排距離時，人們往往只考慮一種或兩種操作。本文研究使用翻轉(zhuǎn)和轉(zhuǎn)位操作對有符號基因組進(jìn)行排序的問題。其中每個基因組均為一個有符號整數(shù)序列，一個整數(shù)符號表示一個基因。 基因組翻轉(zhuǎn)/轉(zhuǎn)位排序要求尋找一個翻轉(zhuǎn)或轉(zhuǎn)位操作序列，將一個給定的有符號整數(shù)排列轉(zhuǎn)化為另一個有符號整

4、數(shù)排列。Gu Q P給出該問題的一個近似性能比為2的多項式時間近似算法，但未見該算法的實現(xiàn)程序和算法計算性能的實際測試結(jié)果。 本文主要討論基因組翻轉(zhuǎn)/轉(zhuǎn)位排序算法的實現(xiàn)方法。首先介紹近似性能比為2的算法思想，然后討論該算法的C程序?qū)崿F(xiàn)方法，并以實際數(shù)據(jù)測試程序的求解性能。在算法的實現(xiàn)中，采用一維數(shù)組和鏈表存儲整數(shù)排列，從而使子序列的翻轉(zhuǎn)和轉(zhuǎn)位操作可在常數(shù)時間內(nèi)完成。在第四章中，根據(jù)少量數(shù)據(jù)手工測試和大量數(shù)據(jù)實際執(zhí)行的結(jié)果，找到