DNA限制性圖譜的繪制(數(shù)學建模論文)

1、 DNA限制性圖譜的繪制摘要 本文是關(guān)于用SPDP法即簡化的局部消化方法來確定DNA鏈的根本的片段排列順序的問題。針對問題一，我們運用窮舉法，并根據(jù)實際DNA鏈的排列實際將窮舉法進行限定，即用簡化窮舉法。并以此為根底建立二叉樹數(shù)據(jù)結(jié)構(gòu)模型，通過MATLAB軟件計算，對問題一中的兩個實例進行求解。由于實例一，由于所給數(shù)據(jù)量非常小，我們可以通過筆算進行試值的方法或者通過MATLAB程序得出其排列順序為2-6-1-4-3。對于實例二，由于存在可能解一共有八組，我們不再在這里表示出來。 SPDP算法是基于二叉樹數(shù)據(jù)結(jié)構(gòu)的窮舉法產(chǎn)生的，首先經(jīng)過了標準化的過程，然后利用b-b表與b-c表兩個表邏輯、拓撲的

2、關(guān)系相互約束，以此對窮舉法進行限定，使窮舉的次數(shù)大大降低，到達實用的效果。但是當所給實驗數(shù)據(jù)較多是任然相當費時費力，而且SPDP所得出的結(jié)果也不唯一，所給實驗數(shù)據(jù)越多那么實驗所得可能的X也越多，還需要根據(jù)實際遺傳學DNA序列的規(guī)律進行排除，選擇最終唯一正確的值。所以該方法在實驗數(shù)據(jù)大時實用性較低。針對問題二，隨著實驗數(shù)據(jù)的增多不能分辨的元素也越來越多，使得可能的X也增多。 X的增多意味著任然需要很大的后續(xù)工作量。在誤差存在的條件下，一組數(shù)據(jù)的相互分辨能力決定于兩個因素，一是誤差限的大小，二是數(shù)據(jù)值分布的疏密程度，即數(shù)據(jù)的方差或標準差。所以，當數(shù)據(jù)的平均絕對誤差限的數(shù)量級到達與數(shù)據(jù)標準差相當?shù)幕?/p>

3、更大程度時，數(shù)據(jù)之間的分辨就會變得非常困難，問題的求解也會變得根本無法進行了。在模型建立后，我們對其進行了推廣及應(yīng)用，并取得了積極有效的成果。 一、問題重述 繪制DNA限制性圖譜restriction mapping是遺傳生物學中的重要問題。由于DNA分子很長，目前的實驗技術(shù)無法對其進行直接測量，所以生物學家們需要把DNA分子切開，一段一段的來測量。在切開的過程中，DNA片段在原先DNA分子上的排列順序喪失了，如何找回這些片段的排列順序是一個關(guān)鍵問題。為了構(gòu)造一張限制性圖譜，生物學家用不同的生化技術(shù)獲得關(guān)于圖譜的間接的信息，然后采用組合方法用這些數(shù)據(jù)重構(gòu)圖譜。一種方法是用限制性酶restric

4、tion enzyme來消化DNA分子。這些酶在限制性位點(restriction sites)把DNA鏈切開，每種酶對應(yīng)的限制性位點不一樣。對于每一種酶，每個DNA分子可能有多個限制性位點，此時可以按照需要來選擇切開某幾個位點不一定連續(xù)。DNA分子被切開后，得到的每個片段的長度就是重構(gòu)這些片段的原始順序的根本信息。在多種獲取這種信息的實驗方法中，有一種廣泛采用的方法：局部消化the partial digest, PDP方法。在PDP中，采用一種酶，通過實驗得到任意兩個限制性位點之間片段的長度。假設(shè)與使用的酶對應(yīng)的限制性位點有n個， 通過大量實驗，可得到n+2個點n個位點加上兩個端點中任意兩

5、點之間的距離，共個值。然后用這個距離來重構(gòu)n個限制性位點的位置(解不一定唯一，兩個端點對應(yīng)于最長的距離)。假設(shè)是線段上的點集中所有點之間距離的集合，PDP就是給定求。以下圖給出了一個例子。 圖1. A,B是DNA分子的兩個端點。 a，b，c和d是限制性位點。 通過實驗可以得到 =2,3,4,5,2,5,9,14,16,7,12,14,9,11,7. 再通過來求，對應(yīng)于上圖的=0,2,5,9,14,16是一種解。上述方法要把DNA分子在任意的兩個限制性位點處切開，這對于當前的實驗技術(shù)來說有相當難度，而且，還要對實驗數(shù)據(jù)進行處理，也很復(fù)雜。最近研究人員提出了一種新的方法，稱為簡化的局部消化方法SP

6、DP。這個方法與PDP的不同就在于它防止了在任意兩個位點切開DNA分子的難題和處理重復(fù)數(shù)據(jù)的困難。仍假設(shè)與使用的酶對應(yīng)的限制性位點有n個。首先DNA分子被復(fù)制成n+1份，前n個復(fù)制品中的每一個在一個限制性位點處被切開，最后一個復(fù)制品在所有的限制性位點處被切開。這樣我們分別得到2n個片段長度稱為第一組數(shù)據(jù)和n+1個片段長度稱為第二組數(shù)據(jù)。在沒有誤差的前提下，第一組數(shù)據(jù)中2n個長度可以分成n對，每對的和都等于DNA分子的總長度；第二組數(shù)據(jù)中n+1個長度的和也等于DNA分子的總長度。 SPDP問題是如何利用這兩組數(shù)據(jù)重構(gòu)出這n+1個片段在DNA分子上的排列，使得這個排列在n個位點切開后得到的2n個片

7、段長度與實驗得到的2n個長度相等。以下圖給出了一個例子。 圖2. 這個例子對應(yīng)的位點有4個。(a) 就是我們希望重構(gòu)的順序。 (b)中的前4對為第一組數(shù)據(jù)，它通過切開一個位點得到，每對長度的和都是16，剩下的為第二組數(shù)據(jù)，含5個片段長度，它通過切開所有位點得到，它們的長度總和也是16， 但實驗結(jié)果只告知每段的長度，不知道它們在DNA分子上的排列順序?，F(xiàn)對上述SPDP問題，建立數(shù)學模型，并研究以下問題：1.設(shè)計求解該問題的算法， 并評估該算法的效率和效果。對下述2個實例給出答案：實例1： 第一組數(shù)據(jù)：2，14，8，8，9，7，13，3 第二組數(shù)據(jù)：2，1，4，3，6實例2: 第一組數(shù)據(jù)：1，14

8、，12，3，7，8，9，6，11，4，12，3，13，2，5，10第二組數(shù)據(jù)：1，1，2，1，2，2，1，2，32.討論在實驗中測量片段長度時的誤差，將在多大程度上影響算法的效果，當誤差到多大程度時，限制性圖譜的重構(gòu)將無法進行。 二、模型假設(shè)及符號說明 1、假設(shè)DNA在用限制性內(nèi)切酶剪切的時候，每一個限制性位點處被切開。 2、假設(shè)每一段DNA都能被準確順利的計數(shù)。 3、在實驗中測量片段長度時的誤差近似服從正態(tài)分布。4、記錄第一組數(shù)據(jù)時在各個限制性切點切得準確，不出現(xiàn)漏切現(xiàn)象 符號說明符號符號表示量備注L被研究的基因鏈總長度第i個被切且僅切為兩段的基因ck第k個基因片段的長度bs每對b中的較小者

9、C第二組數(shù)組成的集合cnC集合中的數(shù)bj與bi 相匹配的位于基因后半段的數(shù)第二組數(shù)中與b1相匹配的數(shù)，即基因的第一個片段長度cj基因的最后一個片段長度pc值重復(fù)的個數(shù)c中的某個元素ck每對b相減的差pk數(shù)據(jù)c中的個數(shù)c數(shù)據(jù)中最大的為兩個b數(shù)相減可以等于的所有的組合的個數(shù)三、 問題分析 SPDP 問題的目標是求出 DNA 限制性圖譜，由于 SPDP 提供的兩組數(shù)據(jù)相對于原有的 DNA 限制性圖譜已經(jīng)不完整，通常情況下有多個解，當解不唯一的情況下，必須解出所有可能解，然后利用生物學方法判斷這些可能接中哪一個是原 DNA 限制性圖譜，如果算法求出的解不全，有可能真實的 DNA 限制性圖譜沒有被求出，

10、那么對下一步的科學工作會導(dǎo)致錯誤，所以 SPDP 算法是要求出所有符合第一組和第二組數(shù)據(jù)的全部可能解。 在解決該實際問題時，我們選擇使用窮舉法來求解，再通過不斷優(yōu)化改良，得到一個高效簡明的窮舉算法 。核心思想是通過對第一組數(shù)據(jù)與第二組數(shù)據(jù)分析，不僅考慮組內(nèi)數(shù)據(jù)的關(guān)系，同時也分析組間的數(shù)據(jù)關(guān)系，得到對于SPDP解的約束，在搜索中，利用約束，可以去掉絕大局部的不可能解，只需要在極少剩余的可能解搜索即可得到全部SPDP問題的解。先從第一組數(shù)據(jù)入手，進行一定的組合，而利用第二組數(shù)據(jù)對第一組數(shù)據(jù)的組合進行檢驗。這里，我們首先要對第一組數(shù)據(jù)進行一定的處理。在第一組數(shù)據(jù)中，DNA都是被切成兩段，當DNA總長

11、度L知道的時候，其實只要知道每對b中的一個值就得到了全部的信息?，F(xiàn)在我們將每對b中較小的一個挑出來假設(shè)與相等任取一個就可以。這樣我們就得到了n個數(shù)據(jù)，再對這n個數(shù)據(jù)進行升序排列，得到一個不嚴格遞增的b序列，在這里不妨記作，它們滿足，它包含了第一組數(shù)據(jù)的所有的信息。 為了方便計算，我們不妨先對基因圖譜的起點和終點做一個規(guī)定，假設(shè)從起點算起，第一個位點到起點的距離小于或者等于從終點算起第一個位點到終點的距離，即。對于重新組織后的第一組數(shù)據(jù)，其含義為：對于某一個，它表示離這段基因起點或者終點距離的位置有一個位點。那么對于第二種窮舉方法也就由此而得出，對于每個它有兩種狀態(tài)，一種是靠近起點不妨用“0表示

12、，另一種是靠近終點不妨用“1來表示。而當全部的的狀態(tài)確定后，DNA的順序也就確定了，但此時要對這個順序的合理性進行檢驗，即檢驗這個順序是否符合第二組數(shù)據(jù)c的要求。具體措施如下：將“0狀態(tài)的全部挑出來按照升序排列。再將“1狀態(tài)的全部挑出來按照升序排列。記第二組數(shù)據(jù)c組成的集合為。然后檢驗是否滿足以下條件：當全部檢驗條件符合的時候，這組組合即為合理的順序，從DNA的起點算起，在前半段的基因中，第i段長度為 (其中)，而對于后半段那么有相同的處理，其示意圖如圖5表示。流程圖如圖4表示。這里值得說明一下的就是對與這個循環(huán)的結(jié)束條件，因為對于基因的排序問題，必須要求出所有的可能解，因此對于這個循環(huán)就必須

13、要把所有的可能組合全部進行一遍以后才可以停止，即需要循環(huán)次。 不合條件符合條件輸出答案用c檢驗組合b圖4圖5 四、模型建立與求解方法問題一 通過查找文獻，我們發(fā)現(xiàn)SPDP問題有它其中的一些特有的性質(zhì)與規(guī)律，我們希望能找到這樣的性質(zhì)與規(guī)律來減少循環(huán)的次數(shù)，并且將復(fù)雜的問題化約為標準的情形便于算法的實現(xiàn)?；谏鲜鲞@種考慮，我們尋找了一些性質(zhì)，并將比擬重要的總結(jié)為一些根本的定理，以便后面進行算法設(shè)計與優(yōu)化。在給出定理之前，先對一些術(shù)語做一定的規(guī)定。首先規(guī)定“同側(cè)與“異側(cè)。我們將整段基因分為前半段與后半段，以基因正中為分界。在第二種模型中，稱為同側(cè)，如果所表示的位點的位置在同一段中同屬于前半段或后半段

14、。稱為異側(cè)，如果所表示的位點不在同一段中。而對于整段基因的每個片段我們都將認為它是一個元素。那么從起點開始的第一個片段我們稱之為“首元素。而從終點開始的第一個片段我們稱之為“尾元素。而包含基因中點位置的基因片段我們稱之為“中間元素。下面我們給出SPDP問題的一些根本定理定理一首元素定理 在模型中，對于第二組數(shù)據(jù)滿足。那么為首元素片段的長度，。即在中存在與相等，并且從起點算起第一個基因片段的長度就為，或者說該片段就是。定理一說明：此定理唯一確實定了首元素，節(jié)省了排列這個元素的時間，它更重要的意義在于把問題進行標準化。定理二尾元素定理 在確定了首元素之后，我們把第二組數(shù)據(jù)中的除去，把與其對應(yīng)的除去

15、。在剩下的b與c中，我們尋找相等的b與c，比方，那么這個就是可能的尾元素，為它的對應(yīng)元。即從整段基因的終點算起，第一個片段實際上是這段基因最后一個片段的長度為，或者說最后一段基因就是。定理二說明：此定理給出了尾元素最后一個片段可能的情況，與首元素一起可以將整段基因的首尾確定下來。當尾元素的可能性超過一個是我們每次只考慮其中一種首、尾元素的情況，然后對首、尾元素的組合進行窮舉。可以看出這個循環(huán)最多是n-1次。定理三首尾排序定理 當首、尾元素確定后，假設(shè)首元素長度為，尾元素長度為，那么所表示的位點的位置必在同側(cè)并且在前半段，并且它們所確定的位點在整段基因中彼此相鄰，即所確定的兩個同側(cè)位點之間沒有別

16、的位點，其中i=2,3,4s-1。定理三說明：首先，對尾元素要進行一個補充，實際問題中有可能出現(xiàn)的情況，此時我們的腳標s選取兩者腳表較大的一個，取而不取。而且對于相等的情況，與一定在異側(cè)，表示在與中點對稱的兩個位置有兩個位點。而且由此觀點我們還可以知道如果，那么必然有。因此嚴格大于，嚴格小于。其實這個結(jié)論也非常重要，但很直觀，就不在這里做為定理。而定理三一方面可以節(jié)省在組合中的狀態(tài)選擇，更主要的是當首尾元素確定后，它可以將SPDP問題進行標準化，即通過首尾排序定理后，我們可以把最靠近起點的s-1段基因看作一個整體因為這s-1段的順序已經(jīng)知道了，當作一個基因片段，它的長度為，并且。而b 中剩下的

17、元素都比首尾元素大。定理四尾元素約束定理 在定理三的說明中，我們知道b中的元素有可能兩兩相等。如果，我們記錄為重值代表。我們找出所有的重值的情況并記錄其重值代表，其中角標滿足。假設(shè)尾元素長度為，那么有約束，即。定理四說明：此定理是對尾元素定理的一個補充，通過這個約束限制了尾元素的可能情況，降低計算的復(fù)雜程度。定理五中間元素對偶定理 由前面的定義知道中間元素是包含中點的片段。那么此片段的兩端有一端的位置必在所確定的位點，而另一段的位置假設(shè)為所確定的位點，那么一定有在第二組數(shù)據(jù)c中有元素與相等。那么這類就為另一端點。并且假設(shè)將視為從整段基因中點往兩端算起的首位點首元素，它是距離中點最近的位點，而將

18、視為中點另一側(cè)的第一個出現(xiàn)的位點，那么中間元素的兩端可以等效為基因的起點和終點，等效為首元素，等效為尾元素，那么定理一到定理四的性質(zhì)在此處都將成立，這就是中間元素的兩端與起點、終點的對偶性質(zhì)。定理五說明：前四個定理實際上是從基因的兩端出發(fā)并不斷的向中間考察，而定理五剛好相反，是先確定最中間的情況，再想兩邊考察。對于定理五的應(yīng)用在3.5進行討論。圖6定理六相鄰重值等效方法 假設(shè)均為重值代表，即。那么在第二組數(shù)據(jù)c中一定有兩個相等的，并且在整段基因中，它們的位置如圖6所示。因此這兩段基因片段的位置就已經(jīng)確定下來，因此我們可以將A點與B點接起來，C點與D點接起來。這樣，原來的基因長度就縮短了。在數(shù)據(jù)

19、中除去上述幾個元素，在剩余的b中我們要對進行一定的處理，對每個數(shù)處理后的值為，其中k=i+4, i+5n，為處理后的值。當如果有更多的重值代表兩兩相鄰，我們可以用同樣的方法在一開始就把這些位置已經(jīng)確定的片段去除，等效出新的一整段基因以及它的初始數(shù)據(jù)。當最后計算出全部的結(jié)果之后再將這些的片段插回去。定理六說明：此定理最重要的作用就是可以將問題進行標準化，使要解決的問題不含有那些已經(jīng)知道基因片段位置的這些特殊情況，從另一個角度看這也是通過對數(shù)據(jù)特征的觀察降低計算的復(fù)雜度。標準化SPDP問題的建立 有了上面一些根本規(guī)律、定理的準備，我們就可以建立標準化的SPDP問題。建立過程如下：第一步：利用定理六

20、相鄰重值等效方法去除由于相鄰對稱的位點所確定的基因片段，調(diào)整兩組數(shù)據(jù)b與c的值。第二步：利用定理一首元素定理確定首元素，除去b中的首元素元與c中的對應(yīng)元。第三步：利用定理二尾元素定理與定理四尾元素約束定理確定尾元素的可能值。并在計算中對每個有可能的尾元素進行循環(huán)，當確定其中一個可能值作為尾元素時，去除b中的尾元素元與c中的對應(yīng)元。第四步：利用定理三首尾排序定理，并將前s-1個片段看為等效首元素尾元素為。這里要注意：假設(shè)發(fā)現(xiàn)前s-1個片段中存在一個片段的長度在c中沒有對應(yīng)相等的值時，說明所選的尾元素并非真正的尾元素，此時返回第二步。 經(jīng)過上述四步處理后，SPDP的原模型已被標準化。對此時的第一組

21、數(shù)據(jù)b重新按遞增排序，并重新給予腳標，將重值賦予同樣的腳標。這樣就可以得到新的，并記錄有重值的b，仍用這樣一組數(shù)來表示。由定理三說明中的分析知道b假設(shè)有重值最多只有兩個元素等相等。而對于第二組數(shù)據(jù)c也同樣重新賦予腳標并排序得到，并用記錄每一個c值重復(fù)的個數(shù)。通過上面五步的操作，我們得到標準化的SPDP問題。為了保持定理的習慣，以及后面算法設(shè)計的方便。我們對于第一組數(shù)據(jù)b不去處首尾元素，那么為首元素， 為尾元素，b數(shù)據(jù)滿足.而在c數(shù)據(jù)中我們卻已經(jīng)把首尾元素對應(yīng)相等的值已經(jīng)去除。那么對于標準化問題，我們要做的事情就是要確定的狀態(tài)組合判定每個屬于前半段還是后半段。而我們的數(shù)據(jù)結(jié)構(gòu)與算法就需要針對這樣

22、的標準SPDP問題進行選取與設(shè)計。SPDP數(shù)據(jù)結(jié)構(gòu)的選取利用二叉樹圖7 當我們已經(jīng)將原模型轉(zhuǎn)化為SPDP的標準問題后，我們就開始需要對的狀態(tài)進行確定。因為在確定它們的狀態(tài)的時候是逐一進行的，因此每輪到確定某個，它就有兩個可能的選擇屬于前半段或者屬于后半段。根據(jù)這樣的一個特點我們選取二叉樹作為SPDP標準問題的主體數(shù)據(jù)結(jié)構(gòu)。接下來的問題就是要確定我們?nèi)绾蔚闹鹨坏膶M行選擇和建樹。這里，我們選擇的順序是從開始從小到大的對b數(shù)據(jù)進行判定并建立二叉樹。我們以為例來看下如何建樹。如圖7否判斷該段b能否放入后半段DNA圖譜判斷該段b能否放入前半段DNA圖譜否開始是進入下一個節(jié)點進行搜索是該節(jié)點子樹沒有解，

23、搜索其他節(jié)點圖8所示，要不然在前半段，要不然在后半段，并且我們考察與,這兩個差值之中至少有一個可以與c中的某個元素相等。其原因為：是首元素，為尾元素，并且是數(shù)據(jù)b中除了、最小的元素，它所決定的位點應(yīng)該是距離前半段第一個位點或者后半段第一個位點距離最近的點，一定是c中假設(shè)干片段中的一個，不然在這種首尾元素組合下沒有合理解。這樣，我們就可以通過判定能否在c中找到=或者=而判定狀態(tài)的可能性。倘假設(shè)=，那么就有可能在前半段，建立二叉樹時現(xiàn)在所處在的結(jié)點就有左樹枝，而左樹枝結(jié)點的數(shù)據(jù)中，c中的數(shù)據(jù)就要去除。當=，那么現(xiàn)在所處的結(jié)點有右樹枝，并且對右樹枝所在的結(jié)點做同樣的處理。如果，那么右樹枝為空，并且不

24、再被考慮，因為那是一條不可能的路徑。依次類推，我們從小到大依次考慮每一個，并通過上述的判定來建立二叉樹。最后需要對重值的b做一個解釋。如果有重值，當考慮到時，應(yīng)該對兩邊同時進行判斷，是否兩個能同時在兩段都成立，假設(shè)有其中一邊不成立那么說明這條支路無解。如此運行，直到所有的都被考慮完，循環(huán)停止并將最后合理的組合所確定的DNA順序輸出。關(guān)于這個數(shù)據(jù)結(jié)構(gòu)的流程如圖對SPDP算法進行進一步的優(yōu)化，建立b-b表與b-c表 我們建立二叉樹數(shù)據(jù)結(jié)構(gòu)的思想來源于上面建立的數(shù)學模型，而這個數(shù)學模型建立的立足點是通過對第一組數(shù)據(jù)b進行組合，而拿第二組數(shù)據(jù)c來進行檢驗。不管是最初的窮舉法還是二叉樹數(shù)據(jù)結(jié)構(gòu)的算法都表

25、達了第一組數(shù)據(jù)與第二組數(shù)據(jù)這樣的一種關(guān)系。然而這樣的關(guān)系并非完美，因為盡管c數(shù)據(jù)比b數(shù)據(jù)包含的信息要少，但對b進行組合的時候，數(shù)據(jù)c仍然是非常重要的一個約束，并且時刻的在約束著b的每一步組合?；谶@樣的想法，我們希望在二叉樹的結(jié)點計算時可以參加c對b的約束。為了實現(xiàn)這樣的想法，我們在SPDP的標準問題中建立了b-b表與b-c表。b-b表的建立首先我們建立b-b表。在二叉樹數(shù)據(jù)結(jié)構(gòu)算法中，我們每步對結(jié)點樹枝的是否存在的判斷都是通過兩個b數(shù)的差是否在這個結(jié)點中數(shù)據(jù)c可以將它看作一個集合中。因此判斷是否等于至關(guān)重要。由此，我們就對數(shù)據(jù)b的所有元素兩兩作差，建立b-b表。我們可以讓橫坐標表示被減數(shù)的腳

26、標i,而縱坐標表示減數(shù)j，j，那么在i,j的位置記為-1，這樣區(qū)分的好處在后面的算法里可以表達。那么，二叉樹結(jié)構(gòu)中每步=的判斷就轉(zhuǎn)變成為判斷b-b表i,j位置上的值。b-c表的建立與b-c表約束b-b表是等式=中i與j之間的關(guān)系，而下面我們建立的b-c表是j與k之間的關(guān)系。如表3所示，表3是最根本b-c表，橫坐標為c的腳標k，而縱坐標是被減數(shù)的腳標j。如果=，那么在k,j的位置記i，假設(shè)，那么在k,j的位置記0。這樣，這張b-c表就有了它自身的含義，它表示著對于每一個，有可能組合出這個的兩個b數(shù)的差的所有可能情況。這里就有一個非常重要的約束，對于每一個，兩個b數(shù)相減可以等于的所有的組合的個數(shù)與

27、數(shù)據(jù)c中的個數(shù)滿足+1。這里要注意，之所以要加1是因為“中間元素并非為兩個b值相減而得到的，所以有可能在這里的個數(shù)比可以小1。但一旦在出現(xiàn)了這種情況，在別的c數(shù)據(jù)的列中就不能出現(xiàn)這種情況，即對于其它的c數(shù)據(jù)要求。倘假設(shè)出現(xiàn)了與約束相矛盾的情況時，再往后計算肯定得不到合理解了，需要換下一個可能的尾元素。得到了b-c表的這個約束后，下一步需要解決的就是如何在二叉樹建立的過程中在不改變開始時候做的b-c表而對每個結(jié)點的進行計算并與該節(jié)點的相比擬。首先，我們發(fā)現(xiàn)在每次節(jié)點中的變化是因為每次計算需要除去c數(shù)據(jù)中的一個值而導(dǎo)致的變化。對于每個節(jié)點，都需要記錄所有的的值。然而，對于,我們并不需要每次都改變b

28、-c表，而是直接從b-c表中計算出當前情況的值。這樣，我們就需要對b-c表進行一個補充。如表4所示，對于每一列,我們又增加了兩個子列，一列為狀態(tài)數(shù)J函數(shù)，另一列為排序R函數(shù)。我們現(xiàn)在來考察二叉樹在建立過程中其中的一個節(jié)點的情況，如表4所示，假設(shè)該節(jié)點的前半段已經(jīng)考慮到，后半段已經(jīng)考慮到。當前需要考慮到底屬于前半段還是屬于后半段。倘假設(shè)被放到了前半段，生成該節(jié)點的左樹枝及其節(jié)點，我們發(fā)現(xiàn)，對于這個新生成的節(jié)點，對于任何，-在這里已經(jīng)是不可能的組合，同理我們發(fā)現(xiàn)，縱坐標比i小的與i,j之間的那些可能與c相等的b的差值的組合在這里已經(jīng)沒有意義了，需要在所有初始時b的差的組合總數(shù)中減去這些在這個狀態(tài)下

29、沒有意義的組合個數(shù)。因此我們這樣來定義我們的J函數(shù)與R函數(shù)：由于在3.3.1標準化SPDP問題的過程中應(yīng)用了定理六相鄰重值等效方法，如果對于某個所對應(yīng)的一列，假設(shè)j,k上的值不為0即=，那么J(j)=1，否那么為0。而R(j)=。那么R(j)表示以從到中為被減數(shù)的所有有可能被別的b相減等于這個的個數(shù)。那么很容易，對于新生成的節(jié)點，=。對這個公式舉一個具體的實例加以說明，如表4，當我們已經(jīng)計算到前半段考慮到b4后半段考慮到b3時，這表示當前情況下只有一種情況可以得到c1,即b5-b4=c1。 經(jīng)過上述的改良，我們就可以通過一個靜態(tài)的b-c表對c中所有的元素在建立樹的過程中方便的檢查它的約束。如果

30、與約束矛盾的情形前面已經(jīng)討論過，而b-c表還有非常好的一個特性就是它在某些情況會有“臨界發(fā)生。比方對于所對應(yīng)的一列，當在某個計算過程中，發(fā)現(xiàn)或者中間元素的情況說明可以組合出的b的差值的個數(shù)已經(jīng)和的個數(shù)相等，那么這時已經(jīng)發(fā)生了“臨界的情況，要求對于當前考慮建立樹的節(jié)點以及它以后的中但凡滿足J(s)=1 s,與s,k所對應(yīng)的一定要在同側(cè)，而一定要在與的另一側(cè)。這樣大大的提高了計算的速度。我們稱這個約束為b-c表約束，它的本質(zhì)是數(shù)據(jù)c對數(shù)據(jù)b組合的約束。對b-b表、b-c表的進一步討論圖9在上文中我們分別建立了b-b表，b-c表這兩張非常有用的表。對于b-c表的約束與作用在3.4.1中已經(jīng)做了詳細的

31、說明。我們發(fā)現(xiàn)，其實b-b表，b-c表本質(zhì)上是等價的，它們都來自于是否等于的問題分析中所舉出的那么一組合理解具有指數(shù)個數(shù)的特例也是通過對b-b表的圖的關(guān)系分析所構(gòu)造出來的。下面就先著重對b-b表的圖的邏輯關(guān)系進行一個分析。 圖10ADEG 在b-b表中。每一個點i,j都表示一個的操作，而i,j上所記錄的值是這個操作與的邏輯關(guān)系。而這于前面我們所講的二叉樹結(jié)構(gòu)的建立是完全一樣的。那么我們就嘗試將二叉樹建立的過程就放到b-b表中，使b-b表中的每一個路徑都對應(yīng)二叉樹中的一個分支。下面我們就以一個簡單的例子來看看b-b表中的路徑是如何的與二叉樹中的分支相對應(yīng)。如圖9與圖10,首先為了看兩個圖的對應(yīng)關(guān)

32、系，我們先不考慮二叉樹建立過程中每步對c的判斷，也不考慮b-b表中每個點i,j上記錄的值。那么在圖9中，我們可以看到二叉樹的一個分支A-D-E-G,而b-b表中的A-D-E-G剛好與之完全對應(yīng)。我們來看這個過程：在初始狀態(tài)分別是首元素與尾元素。有兩個選擇，一個是放在一邊，而另一個選擇是放在一邊，在b-b表中，它的選擇就是A點A點在圖中表示3，1點與B點。而對于我們這個分支它選擇了A點。下一個考慮的是，同樣道理它也有兩個選擇D點與F點，容易的看出，每次選擇時，b-b表中的圖的這一列的最上面的點如點B、D、F、G都是可以選擇的一個路徑，而對于另一個路徑在取決于前面的形成過程。比方考慮時，由于B點是

33、上一次的一個選擇確沒有選擇，那么將B點平移到了C點，成為了這次考慮的一個路徑的選擇。同樣的，在這個分支選擇了D點，當考慮時，它的選擇就有E與F；圖11當考慮時，它的選擇有G與H，而最后選擇了G，最后形成了A-D-E-G這個路徑。而在實際建立二叉樹時的每一步都需要檢驗是否等于，那么在b-b表中就需要經(jīng)過的點i,j上記錄的值不能是0，必須為某一個k，并且還要要求這個在已經(jīng)到達這個點時仍然在數(shù)據(jù)c之中c中的元素是不斷減少的。這樣一來，建立二叉樹的過程就全部可以在b-b表的圖的關(guān)系中得以表現(xiàn)。下面我們再來觀察b-b表具有的更多的特性。首先，如果b-b表中每一點的值均記為，那么我們發(fā)現(xiàn)在同一列中，下面的

34、點的值比上面的大；同一行中，右邊的點的值比左邊的大，那么我們用箭頭表示值增大的方向，我們可以得出圖11，這是點的值的大小分布圖。下面我們就用這樣的關(guān)系來構(gòu)造一組合理解的個數(shù)在個以上的數(shù)據(jù)即問題分析中所舉出的實例。首先我們希望構(gòu)造一組數(shù)據(jù)，使得為首元素一定在前半段，為尾元素一定在后半段，而一定可以既能在前半段也能在后半段；在前半段，在后半段，一定既能在前半段又能在后半段，如此一直類推下去。如果能構(gòu)造出這樣的解，它解的個數(shù)一定不少于，而我們現(xiàn)在將剛剛所說的規(guī)律所要求經(jīng)過的點畫在b-b圖上，得到圖12，這樣我們就發(fā)現(xiàn)了規(guī)律，它很有規(guī)律的六個一組的進行重復(fù)?，F(xiàn)在的任務(wù)就是需要對這些點賦上c的值，使上述

35、對b-b表的點的值的分布可以看出，如果我們規(guī)定了，那么對于這個問題最好的構(gòu)造如圖12所示。圖12 在這張圖的指導(dǎo)下我們得到了我們構(gòu)造的數(shù)據(jù)的遞歸式：比方我們可以利用這個遞歸公式得到這樣的初始條件：圖12 問題分析中的數(shù)據(jù)測試就是以這組特殊的實例來說明了由于SPDP問題要求要把所有的合理解都要計算出來，而這組數(shù)的合理解就已經(jīng)有指數(shù)個，因此不管如何優(yōu)化算法都不可能得到多項式的計算方法。圖14 b-b表中對在二叉樹的建立過程中也可以起到與3.4.2類似的效果。根據(jù)前面所述的b-b表中路徑選取的規(guī)律有圖13-16這幾個圖中任何一個情況發(fā)生，該圖沒有一個合理解。其中，圖13是圖14的特殊情況。有了以上的

36、結(jié)論，我們又發(fā)現(xiàn)，當圖13-16這些圖中有一個點并非0或者-1時，不管采取何種路徑，在這個圖中這個點必然要被經(jīng)過，比方圖17-18所示的情況。這個情況實際上是與b-c表中臨界后的點的情況是一樣的，統(tǒng)稱這些為臨界點注：但它們臨界的原因不同。而在b-b表中，倘假設(shè)A點為臨界點，那么A點所在的行與列上其它所有的點都不可能被經(jīng)過，此時將這些本來不為0的點改為0，稱這樣的操作為b-b表的約束。這樣，我們就可以成功的將b-c表約束與b-b表約束結(jié)合在一起，大大優(yōu)化算法的復(fù)雜度，具體過程如下：建立b-b表，進行b-b表約束，如果出現(xiàn)了無解狀態(tài)就停止。通過b-b表建立b-c表，再進行b-c表約束。如果出現(xiàn)了無

37、解狀態(tài)就停止。b-c表約束后產(chǎn)生的臨界點再帶入b-b表進行b-b表約束。b-b表約束后修改b-c表，如果b-c表沒有產(chǎn)生新的臨界點，將進入計算；否那么繼續(xù)進行3。下面我們將討論一下b-b表能否也如b-c表的約束一樣，在二叉樹的建立過程中也進行約束。理論上說是可以的，只要將b-b表中未考慮的元素的區(qū)域取出來，根據(jù)已經(jīng)到達的這一步的實際的c數(shù)據(jù)修改b-b表或重新建立b-b表，再進行上述的算法優(yōu)化。然而對于每一步都做這樣的事情，實際上也在增加了時間復(fù)雜度。b-c表約束也存在這樣的問題，只是它的復(fù)雜度比b-b表約束要小的多。而我們在這里就可以采取一個策略，就是并不是在每一步都進行b-c表約束與b-b表

38、約束，而是在某些步的時候進行抽查，比方說當樹支多到一定的程度的時候就采取一次優(yōu)化。這兩個表在實際的算法中起到了巨大的作用。最后，在這里想討論一下對于這個問題的終極算法設(shè)計的可能性。首先解釋終極算法：終極算法就是在建立二叉樹的過程中可以在最早的時間預(yù)測到某個支路繼續(xù)走下去將是“死胡同。這種想法與b-b表約束的道理類似，然而，b-b表只是用了局部的信息，它并沒有將c所包含的所有的信息用完全。如圖19所示，A、B、C、D點的值同為，然而，如果的個數(shù)只有兩個的時候，就相當于在路徑的選擇過程中A、B、C、D四個點選擇兩個點經(jīng)過。然而如果將這樣的約束引入到b-b表約束，實現(xiàn)這個約束的復(fù)雜度就已經(jīng)到達了指數(shù)

39、的難度。因此終極算法的實現(xiàn)幾乎是不可能的。然而幸運的是對于實際的數(shù)據(jù)，利用已有的兩個約束已經(jīng)可以大大的降低了復(fù)雜度，使它相當接近終極算法。 最終SPDP問題算法 經(jīng)過了以上的準備，我們可以得到了最終對SPDP的算法。 1.對具體的數(shù)據(jù)進行標準化處理，得到SPDP的標準問題 2.建立b-b表與b-c表進行3.4.3中b-b表、b-c表共同約束，如果出現(xiàn)無解情況返回1的循環(huán)中；否那么進入3 3.建立二叉樹數(shù)據(jù)結(jié)構(gòu)，并在b-b表、b-c表約束及其共同約束的操作下進行有效窮舉，輸出答案。之否再返回到1的循環(huán)，直到1的循環(huán)結(jié)束為止。 最后在本節(jié)小結(jié)SPDP問題算法：SPDP算法是基于二叉樹數(shù)據(jù)結(jié)構(gòu)的窮舉

40、法產(chǎn)生的，首先經(jīng)過了標準化的過程，然后利用b-b表與b-c表兩個表邏輯、拓撲的關(guān)系相互約束，使窮舉的次數(shù)大大降低，到達實用的效果。問題二 顯而易見，實際的SPDP問題中因為生物化學手段的限制，實際測量中不可能得到準確的DNA片斷長度，測量時的誤差是不可防止的。所以我們必須考慮在有誤差的情況下，如何在原算法的根底上實現(xiàn)SPDP的算法：確定b-b 表和b-c表 b-b 表和b-c表b-b表在程序的匹配判斷當中起到了相當重要的作用。所以我們應(yīng)該首先在誤差存在的條件下將b-b 表和b-c表確定下來，這樣在這種情況下程序的算法也就相對確定了。為了確定這兩張表, 我們需要了解誤差對確定變量值之間的關(guān)系。于

41、是我們首先需要明確以下問題：長度測量值的概率分布 由于片斷長度的測量值誤差是由很多微小的因素引起的分量疊加而形成的，在統(tǒng)計學上我們認為這些微小的分量滿足李雅普諾夫Liapunov定理的條件。于是由該定理可知：同一個物理量的測量值的誤差近似服從正態(tài)分布其數(shù)學期望為0。2也就是說，每個物理量的測量值滿足數(shù)學期望為其真值的正態(tài)分布。 記為，其中和分別為第一組數(shù)據(jù)和第二組數(shù)據(jù)中的長度測量值。由3原理可知，其絕對誤差限可以認為注是： 測量量的誤差限可以由儀器精度和方法精度進行估計，也可以通過樣本方差進行估計，所以可以當作是量。兩個片段長度的不可分辨判據(jù) 由概率論原理可知， 故可以認為 故當時，即的真值相

42、等時，其測量值之差的可能范圍滿足 所以一旦其測量值之差滿足了這個條件，我們就不能判定這兩個值的真值是否相等。于是我們稱這兩個測量值不可分辨。上式的條件稱為不可分辨判據(jù)。b-b表確實定 由于b-b表和b-c表是完全等價的，故我們只需確定b-b表，就可以推算出b-c表。 如前面所述，b-b表的某個域Tij的值決定于是否等于某一個。在無誤差的計算中，需要嚴格等于。但是在包含誤差的計算當中，很可能沒有一個能夠嚴格的等于，而我們需要判定是否他們可以相等。 由于 故當和的真值相等時，可以認為 當滿足上式條件時, 和的真值就可能相等。在這種情況下，為了不漏掉可行解，我們就認為他們在誤差允許條件下相等。于是就

43、有可能出現(xiàn)多于一個的和 相等。這些也是不可相互分辨的，即單憑長度的信息不能將他們區(qū)分開在DNA鏈上位置互易后但從長度上講仍然滿足所取得的數(shù)據(jù)要求,這跟他們相等的情況是等效的。所以認為這些等效相等，所有滿足和 相等的的集合記為,稱為等效集合。記(其中N為限制性定位點的個數(shù))，故易知,其中為上面的算法中最后出現(xiàn)在中間的元素。我們需要將這個并集進行劃分，但是并不一定兩兩交集為空。所以我們要對這個并集進行如下處理： eq oac(,1)與任意其他集合相交為空的集合不變。 eq oac(,2)如果,去除集合。 eq oac(,3)除 eq oac(,2)的情況外，如果，那么A.如果 滿足不可分辨判據(jù)，那

44、么令，而去除集合。B.否那么，不妨設(shè), 那么必有。令 為原集合的元素中，與不滿足不可分辨判據(jù)的元素的集合。令 為原集合的元素中，與不滿足不可分辨判據(jù)的元素的集合。其他中元素的集合可以作劃分，,使。令 = ， = 任意滿足條件的劃分都要考慮，因為每一種劃分將對應(yīng)不同的c向量，也就將對應(yīng)不同的解。 eq oac(,4)在 eq oac(,3)情況中將和劃分開后，如果各自仍與其他集合有非空交集，那么繼續(xù)按照 eq oac(,2)和 eq oac(,3)的原那么進行劃分。 這樣確定下來的集合就形成了原并集的一個劃分，每個集合內(nèi)的元素在程序判斷時當作相等處理，將它們歸并在一起，元素的值取劃分當中元素的均

45、值。 每一種c集合劃分，表中域Tij的值那么為離最近的新值的下標。下面以下表數(shù)據(jù)為例對上述方法進行說明。(假設(shè)所有數(shù)據(jù)相對誤差限為1%,并且為了形式統(tǒng)一和算法設(shè)計方便設(shè)b0 = 0 ，無誤差) 按照 eq oac(,1) eq oac(,2) eq oac(,3) eq oac(,4)的原那么進行劃分，最終得到c的兩組劃分1、 2、 所對應(yīng)的b-b表均為：從這組數(shù)據(jù)可以看出，當誤差限相對于數(shù)據(jù)的標準差來說較大的時候，會產(chǎn)生很多不可分辨元素，對問題的求解帶來了很壞的影響。計算機結(jié)果及分析問題1 根據(jù)上文中的模型和算法，運用Matble軟件編程計算除了結(jié)果，結(jié)果如下：實例1第一組數(shù)據(jù)：2，14，8

46、，8，9，7，13，3第二組數(shù)據(jù)：2，1，4，3，6利用上述算法：計算出相應(yīng)的可能DNA限制性圖譜： 2，6，1，4，3實例2第一組數(shù)據(jù)：1，14，12，3，7，8，9，6，11，4，12，3，13，2，5，10第二組數(shù)據(jù)：1，1，2，1，2，2，1，2，3利用上述算法：計算出相應(yīng)的可能DNA限制性圖譜：第一組： 1，1，1，1，2，2，2，2，3第二組： 1，1，1，2，2，2，2，1，3第三組： 1，2，1，1，2，2，3，1，2第四組： 1，2，3，2，2，1，1，1，2第五組： 1，2，1，2，1，3，2，1，2第六組： 1，2，2，1，2，3，1，1，2第七組： 1，2，2，3，1，2，1