基因組的排序問(wèn)題.pdf

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

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

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