有向基因組的反轉(zhuǎn)和轉(zhuǎn)位排序算法.pdf

1、隨著快速測序技術(shù)的發(fā)展，基因組重組排序已經(jīng)成為計算生物學(xué)的一個重要研究領(lǐng)域。其研究的目標(biāo)是尋找最短的重組操作序列，將一種基因組轉(zhuǎn)變?yōu)榱硪环N基因組?；诜肿由飳W(xué)家的實驗數(shù)據(jù)表明，基因組重組是生物進(jìn)化的一種普遍模式，也是衡量不同生物之間親緣關(guān)系的一種重要手段。 存在三種典型的基因組重組操作：反轉(zhuǎn)（reversal）、轉(zhuǎn)位（transposition）和移位（translocation）。其中，反轉(zhuǎn)與轉(zhuǎn)位操作作用在單條染色體上，而移

2、位操作則作用在兩條染色體上。 過去，人們主要關(guān)注于單一重組操作的基因組重組排序問題，而對于多種混合重組操作的基因組重組排序問題的研究則相對較為緩慢。目前，對于無符號排列的反轉(zhuǎn)和轉(zhuǎn)位排序問題，婁曉文和朱大銘給出了一個2.25近似度的算法；對于有向基因組的反轉(zhuǎn)和轉(zhuǎn)位排序問題，Hartman和Sharan給出了一個1.5近似度的算法。 本文首先討論了經(jīng)典的有向基因組的反轉(zhuǎn)和轉(zhuǎn)位排序問題，并介紹了Hartman的1.5近似度算法

3、。此外，本文考慮重組操作的所花費(fèi)的費(fèi)用，引入了有向基因組重組排序的最小權(quán)重問題。其目標(biāo)為求解花費(fèi)最少費(fèi)用的重組操作序列，使一個基因組轉(zhuǎn)變成另一個基因組。對于該問題，本文給出了一個1.5k近似度的算法。 本文的創(chuàng)新點(diǎn)主要有4個： 1.考慮了重組操作的所花費(fèi)的費(fèi)用，提出了有向基因組反轉(zhuǎn)和轉(zhuǎn)位排序的最小權(quán)重問題，并分析了該問題的背景和研究價值； 2.對于該問題，證明了一個下界； 3.基于這個下界，給出了該問題的