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

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

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

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