基因組的排序問題.pdf

1、對于基因組的排序問題在近幾年得到了廣泛的研究.新的斷點圖的方法被發(fā)現(xiàn)并對算法的設計起了重要的作用.在這篇論文中,主要研究了基因組排序問題中三種不同操作的排序問題的算法,這三個問題的難度有所不同.反轉操作是將一個基因序列的一個子序列的順序反轉過來.反轉排序有O(n2)的多項式時間算法.轉位操作是將一個基因序列中的兩段相鄰的子序列交換位置.轉位問題現(xiàn)在只有近似比為3/2的近似算法.移位操作是將兩個基因序列在中間斷開,在將分屬兩個基因序列的子

2、序列重新連接起來,形成兩個新的基因序列.移位排序也有多項式時間算法.本文主要對于有向基因組移位排序問題進行了研究,對于有向染色體組移位排序問題,Kececioglu與Ravi首先給出近似性能比為2的多項式時間近似算法,Hannenhalli利用斷點圖的性質,證明了一個重要的二元定理,并由此證明了該問題有多項式時間算法.Hannenhalli于1996年給出的移位排序算法的時間復雜度為O(n<'3>),2001年朱大銘,馬紹漢將Hanne

3、nhalli算法的時間復雜度改進為O(n<'2>logn).本文的主要成果和創(chuàng)新點如下:·給出了尋找斷點圖中所有最小子排列的O(n<'2>)算法.·發(fā)現(xiàn)了斷點圖中的最右灰邊并證明了其特殊性質.·給出了基于最右灰邊的線性的無用頂點刪除算法.·給出尋找有效合理移位的線性算法,并在此基礎上,最終給出了基因組移位排序問題的O(n<'2>)的快速算法,這也是目前為止,該問題的最好算法.本文本文的組織如下:第一章為背景介紹,第二章介紹有向染色體反轉