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

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

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