基因排列的中端標記部分剪切問題

Abstract

部分剪切問題(PDP)是在重組DNA的酵素切位中一個重要的問題。從組合學的角度來看，我們把部分剪切問題定義為以下的形式。令 X = { x1, x2, ..., xn }為一段DNA上的酵素切位，且 0 = x1 < x2 < ... < xn為n個整數，則 ∆X = { xj – xi | 1≤ j ≤ n }是任兩個不同酵素切位的距離。部分剪切問題就是已知 ∆X，要重建DNA上的酵素切位X。

雖然部分剪切問題看起來不難，但是它在演算法上的時間複雜度還是未知的。以我們的觀點來看，我們認為部分剪切問題是個NP困難的題目。在這篇論文中，我們參考尾端標記部分剪切(end-labeled partial digest)，標記部分剪切(labeled partial digest)，和探針部分剪切(probed partial digest)等問題，提出一個中端標記部分剪切(mid-labeled partial digest)的想法。如果在其中標記了k個位置，則我們給出一個O(n^(3/2) 2^(2n/(k+1)) lg n)的演算法。

In DNA sequencing, the partial digest problem (PDP) plays an important role on reconstructing the locations of restriction sites in DNA. From combinatorial point of view, we can model PDP as follow. Let X = { x1, x2, ..., xn } be the set of restriction sites with x1 = 0, and x1 < x2 < ... < xn be positive integers, and ∆X = { xj – xi |1≤ j ≤ n } be the multi-set of distances between every two distinct restriction sites. Then, the PDP is to find the solutions X by knowing ∆X.

Though the model looks simple, so far, the hardness of PDP is still unknown. It seems to us, the PDP is a NP-hard problem. In this thesis, motivated by the approach of end-labeled partial digest, labeled partial digest and the idea of probed partial digest, we propose an idea called mid-labeled partial digest. As a consequence, if k mid-labels are added, then we obtain an algorithm with running time O(n^(3/2) 2^(2n/(k+1)) lg n) in the worst case.