一個解決最小斷點全序化問題的貪婪演算法

Abstract

基因或是標記在基因體上的全序關係對於大多數比較基因學的研究是非常重要的。然而除了少數的模式基因體之外，大多數的基因體尚未被完全的定序出來。目前的基因定位技術常常產生一些基因圖譜，裡頭有好幾個基因或標記會被放在同一個位置，或者會因為解析度不足的關係而遺失掉一些基因或標記，因此這些基因定位的技術只能提供基因在圖譜的偏序關係而不是全序關係。所以近年來，從一個偏序關係的基因體中推論出其全序關係的議題越來越受到關注。在本篇論文中，我們研究所謂的最小斷點全序化問題，其目的是要在一個偏序關係的基因體上找到一種可能的全序關係，使得該基因體跟另一個參考的全序關係基因體的斷點距離為最小。過去的研究已經證實了最小斷點全序化問題是NP-hard，因此目前被提出的非指數時間演算法只是一些啟發式的或近似的演算法。在這個研究中，我們提出一個線性時間的貪婪演算法來解決一個最小斷點全序化問題的特例，即在給定的偏序關係基因圖譜上沒有基因或標記被遺失。

The total order of the genes or markers on a genome is very important for most comparative genomics studies. However, except for a few model genomes, most genomes have not been completely sequenced yet. Current genetic mapping techniques often generate gene maps that have several genes or markers at the same position and/or are missing some other genes due to the lack of resolution in maps. They thus only suffice to produce partial orders, rather than total orders, in the gene maps. Therefore, there has been a growing interest recently in inferring the total order of genes or markers on a genome whose genes or markers are ordered partially. In this thesis, we study the so-called minimum breakpoint linearization (MBL) problem, which is to find the total order of a partially ordered genome that minimizes its breakpoint distance to a reference genome whose genes are already totally ordered (i.e., a completely sequenced genome). It was previously showed to be NP-hard and therefore the non-exponential time algorithms proposed currently are just heuristic or approximate. In this study, we present a greedy algorithm in O(n) running time for a special case of the MBL problem in which there are no missing genes in the given partially ordered gene maps.