基因組數(shù)學(xué)建模

1、封一答卷編號(hào)（參賽學(xué)校填寫）：答卷編號(hào)（競(jìng)賽組委會(huì)填寫）：論文題目： （標(biāo)明A、B、C、D之一） B 組 別：(填寫研究生、本科生、專科生或中學(xué)生) 本科生 參賽隊(duì)員信息(必填)： 姓 名學(xué) 號(hào)聯(lián)系電話參賽隊(duì)員1參賽隊(duì)員2參賽隊(duì)員3 參賽學(xué)校： 沈陽(yáng)理工大學(xué) 封二答卷編號(hào)（參賽學(xué)校填寫）： 答卷編號(hào)（競(jìng)賽組委會(huì)填寫）：評(píng)閱情況（學(xué)校評(píng)閱專家填寫）：學(xué)校評(píng)閱1.學(xué)校評(píng)閱2.學(xué)校評(píng)閱3. 評(píng)閱情況（聯(lián)賽評(píng)閱專家填寫）：聯(lián)賽評(píng)閱1.聯(lián)賽評(píng)閱2.聯(lián)賽評(píng)閱3.目錄摘要：1一、問(wèn)題重述2二、基本假設(shè)4三、符號(hào)說(shuō)明4四、模型建立與求解4五、模型的檢驗(yàn)8六、模型的評(píng)價(jià)9參考文獻(xiàn)10附錄10摘要： 在世界生物界

2、的飛速發(fā)展的今天，我國(guó)生物界對(duì)于基因組組裝也有了一定的突破。尤其是在測(cè)序技術(shù)上，我國(guó)從第一代技術(shù)發(fā)展到第二代技術(shù)，現(xiàn)在正步入第三代技術(shù)，但是目前能直接讀取的堿基對(duì)序列長(zhǎng)度遠(yuǎn)小于基因組序列長(zhǎng)度，為了讓組裝效果更完整，連續(xù)和準(zhǔn)確，我們利用概率論與數(shù)理統(tǒng)計(jì)，c語(yǔ)言，和多目標(biāo)規(guī)劃，以及c+、matlab等軟件，參考了國(guó)內(nèi)外生物界、醫(yī)學(xué)界有關(guān)基因組組裝技術(shù)，以olc技術(shù)為核心，建立了集完整、準(zhǔn)確、連續(xù)為一體的優(yōu)化模型，來(lái)解決測(cè)序中可能會(huì)出現(xiàn)的問(wèn)題。具體如下：對(duì)于問(wèn)題一： 首先利用olc技術(shù)，將附件中給出的測(cè)序之后的堿基對(duì)，建立優(yōu)化模型，該模型能夠利用多條約束條件來(lái)求質(zhì)量的最小值。利用c+軟件來(lái)進(jìn)行兩兩比

3、較，選擇出重復(fù)的部分作為結(jié)點(diǎn)，其他的部分作為有向線段，利用有向圖來(lái)選擇一條質(zhì)量最重的一條鏈，但是可能會(huì)存在測(cè)序中個(gè)別堿基對(duì)的錯(cuò)誤，所以，將所測(cè)出的的最重的這條鏈所有的結(jié)點(diǎn)全部去掉，再將剩下的堿基對(duì)重新利用olc法來(lái)組裝，重復(fù)該種實(shí)驗(yàn)3-4次，見附錄的程序，一定會(huì)有質(zhì)量相同的兩條鏈，則這兩條鏈的組成就是最完整準(zhǔn)確的。這個(gè)程序的試驗(yàn)次數(shù)少，完成組裝的時(shí)間少。 針對(duì)組裝后的基因組中可能會(huì)出現(xiàn)重復(fù)片段的問(wèn)題，我們利用c+軟件，建立了優(yōu)化模型，采取的方法是在olc技術(shù)的基礎(chǔ)上，檢測(cè)有向圖，判斷結(jié)點(diǎn)的重復(fù)次數(shù)，進(jìn)行標(biāo)記，直到檢測(cè)出同一結(jié)點(diǎn)前后兩條有向線段并不相同，才是無(wú)重復(fù)基因組的基因組裝。 對(duì)于問(wèn)題二：

4、現(xiàn)有一個(gè)全長(zhǎng)約為120,000個(gè)堿基對(duì)的細(xì)菌人工染色體（BAC）， 采用Hiseq2000測(cè)序儀進(jìn)行測(cè)序，測(cè)序深度（sequencing depth）約為70×，即基因組每個(gè)位置平均被測(cè)到約70次。利用c+軟件，建立優(yōu)化模型，在olc技術(shù)的基礎(chǔ)上，基于問(wèn)題一所做的程序（見附錄），將附件一和附件二的堿基對(duì)輸入到程序中，組裝成完整、準(zhǔn)確、連續(xù)的基因組，所得的結(jié)果就是最完整、準(zhǔn)確、連續(xù)的基因組。關(guān)鍵字：olc技術(shù) c+ 堿基對(duì) 優(yōu)化模型 matlab 多目標(biāo)規(guī)劃一、問(wèn)題重述 快速和準(zhǔn)確地獲取生物體的遺傳信息對(duì)于生命科學(xué)研究具有重要的意義。對(duì)每個(gè)生物體來(lái)說(shuō)，基因組包含了整個(gè)生物體的遺傳信息，

5、這些信息通常由組成基因組的DNA或RNA分子中堿基對(duì)的排列順序所決定。獲得目標(biāo)生物基因組的序列信息，進(jìn)而比較全面地揭示基因組的復(fù)雜性和多樣性，成為生命科學(xué)領(lǐng)域的重要研究?jī)?nèi)容。 測(cè)序技術(shù)始于20世紀(jì)70年代，伴隨著人類基因組計(jì)劃的實(shí)施而突飛猛進(jìn)。從第一代到現(xiàn)在普遍應(yīng)用的第二代，以及近年來(lái)正在興起的第三代，測(cè)序技術(shù)正向著高通量、低成本的方向發(fā)展。盡管如此，目前能直接讀取的堿基對(duì)序列長(zhǎng)度遠(yuǎn)小于基因組序列長(zhǎng)度，因此需要利用一定的方法將測(cè)序得到的短片段序列組裝成更長(zhǎng)的序列。通常的做法是，將基因組復(fù)制若干份，無(wú)規(guī)律地分?jǐn)喑啥唐魏筮M(jìn)行測(cè)序，然后尋找測(cè)得的不同短片段序列之間的重合部分，并利用這些信息進(jìn)行組裝

6、。當(dāng)然，由于技術(shù)的限制和實(shí)際情況的復(fù)雜性，最終組裝得到的序列與真實(shí)基因組序列之間仍可能存在差異，甚至只能得到若干條無(wú)法進(jìn)一步連接起來(lái)的序列。對(duì)組裝效果的評(píng)價(jià)主要依據(jù)組裝序列的連續(xù)性、完整性和準(zhǔn)確性。連續(xù)性要求組裝得到的（多條）序列長(zhǎng)度盡可能長(zhǎng)；完整性要求組裝序列的總長(zhǎng)度占基因組序列長(zhǎng)度的比例盡可能大；準(zhǔn)確性要求組裝序列與真實(shí)序列盡可能符合。利用現(xiàn)有的測(cè)序技術(shù)，可按一定的測(cè)序策略獲得長(zhǎng)度約為50100個(gè)堿基對(duì)的序列，稱為讀長(zhǎng)（reads）?；蚪M復(fù)制份數(shù)約為50100?；蚪M組裝軟件可根據(jù)得到的所有讀長(zhǎng)組裝成基因組，這些軟件的核心是某個(gè)組裝算法。常用的組裝算法主要基于OLC（Overlap/La

7、yout/Consensus）方法、貪婪圖方法、de Bruijn圖方法等。一個(gè)好的算法應(yīng)具備組裝效果好、時(shí)間短、內(nèi)存小等特點(diǎn)。新一代測(cè)序技術(shù)在高通量、低成本的同時(shí)也帶來(lái)了錯(cuò)誤率略有增加、讀長(zhǎng)較短等缺點(diǎn)，現(xiàn)有算法的性能還有較大的改善空間。問(wèn)題一：試建立數(shù)學(xué)模型，設(shè)計(jì)算法并編制程序，將讀長(zhǎng)序列組裝成基因組。你的算法和程序應(yīng)能較好地解決測(cè)序中可能出現(xiàn)的個(gè)別堿基對(duì)識(shí)別錯(cuò)誤、基因組中存在重復(fù)片段等復(fù)雜情況。問(wèn)題二：現(xiàn)有一個(gè)全長(zhǎng)約為120,000個(gè)堿基對(duì)的細(xì)菌人工染色體（BAC）， 采用Hiseq2000測(cè)序儀進(jìn)行測(cè)序，測(cè)序策略以及數(shù)據(jù)格式的簡(jiǎn)要說(shuō)明見附錄一和附錄二，測(cè)得的讀長(zhǎng)數(shù)據(jù)見附錄三，測(cè)序深度（s

8、equencing depth）約為70×，即基因組每個(gè)位置平均被測(cè)到約70次。試?yán)媚愕乃惴ê统绦蜻M(jìn)行組裝，并使之具有良好的組裝效果。二、基本假設(shè)假設(shè)read1均為500bp片段的前88個(gè)，read2為后88個(gè)假設(shè)只有個(gè)別堿基對(duì)錯(cuò)誤、基因組中存在重復(fù)片段的情況三、符號(hào)說(shuō)明Ann表示DNA的第一條鏈；Bnn表示與之相對(duì)應(yīng)的第二條鏈；Cnn表示結(jié)點(diǎn)；AAnn表示第一條鏈質(zhì)量；BBnn 表示第二條鏈質(zhì)量；CCnn 表示節(jié)點(diǎn)鏈質(zhì)量；Pathnn表示路徑節(jié)點(diǎn)；Distancenn表示鏈的質(zhì)量；Read1表示測(cè)序后該片段的第一條鏈的前88個(gè)堿基對(duì)；Read2表示測(cè)序后該片段的第一條鏈的后88個(gè)

9、堿基對(duì)；四、模型建立與求解問(wèn)題一：優(yōu)化模型：4.1解決個(gè)別堿基對(duì)識(shí)別錯(cuò)誤的問(wèn)題（一）將所給的讀長(zhǎng)組成基因組方法一：OLC（Overlap/Layout/Consensus）方法1含義： 當(dāng)前流行的很多序列拼接算法，包括PHRAP7,TIGR8等，都廣泛的采用OLC（Overlap/Layout/Consensus）方法。先對(duì)所有shotgun小片段進(jìn)行兩兩比對(duì)，獲取重疊部分，并且對(duì)這些重疊進(jìn)行衡量，再將重疊的片段相互連接，得到DNA目標(biāo)序列的一個(gè)大致輪廓；最后構(gòu)建所求的DNA目標(biāo)序列。其實(shí)就是以每個(gè)shotgun片段為頂點(diǎn)，以重疊關(guān)系為邊，構(gòu)造一個(gè)有向圖，并在圖中找出找出一條經(jīng)過(guò)每個(gè)頂點(diǎn)一次且

10、僅一次的最佳路徑。2 OLC（Overlap/Layout/Consensus）方法對(duì)重疊序列的處理采用OLC（Overlap/Layout/Consensus）方式的拼接算法一直伴隨著鳥槍測(cè)序 ，如PHRAP7,TIGR8等，這也是最傳統(tǒng)和最經(jīng)典的方式，利用計(jì)算機(jī)圖論的知識(shí)，將shotgun集合中的所有片段fragments看做一個(gè)個(gè)結(jié)點(diǎn)如果兩個(gè)片段之間重疊，那么就在這兩個(gè)結(jié)點(diǎn)之間畫上一邊，構(gòu)成一個(gè)有向圖G，然后在圖G中找每一個(gè)結(jié)點(diǎn)一次且僅一次的一條路徑，就將DNA序列拼接問(wèn)題轉(zhuǎn)化成了一個(gè)圖論中的hamilton路徑問(wèn)題。3 主要步驟 以附錄一中的read1，read2，read3，read

11、4為例a) 將read集合中所有片段fragments兩兩比對(duì)，獲得存在的重疊部分信息;b) 以片段為頂點(diǎn)，重疊的片段相互連接，形成有向圖如圖；在這一步中，phrap算法根據(jù)上一步得到的重疊信息將存在重疊的片段組合起來(lái)形成一個(gè)稱為contig20的結(jié)構(gòu)。c) 在有向圖找出一條路徑，經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次，順序抽取出改路徑上的fragments，重疊拼接成“consensus”序列。OLC（Overlap/Layout/Consensus）方式構(gòu)建的read示意圖通過(guò)在有向圖G中查找路徑進(jìn)行DNA序列拼接的時(shí)候，TIGR算法在shotgun集合中對(duì)repats采取如下方法進(jìn)行處理1） 含rep

12、eats的fragments留到最后再進(jìn)行拼接，以最大限度的利用不含repeats的fragments中的信息。2） 碰上含repeats的fragments時(shí)，相應(yīng)的提高序列匹配的標(biāo)準(zhǔn)，如果repeats的測(cè)序精度上和正常fragments相比有特別大的差異的話那么就可以排除掉含低測(cè)序精度repeats的fragments3） 比f(wàn)ragments平均長(zhǎng)度的一半還短的repeats通常不是問(wèn)題因?yàn)檫@種repeats通常會(huì)被一個(gè)fragments所覆蓋，不會(huì)影響到拼接4） 對(duì)repeats的兩端進(jìn)行測(cè)序是很有幫助的這樣能夠幫助那些包含repeats的fragments依據(jù)其兩端來(lái)定位。方法二：

13、 貪婪算法1. 含義： 貪婪算法（又稱貪心算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解2 貪婪算法的基本處理： 貪婪算法（Greedy algorithm）是一種對(duì)某些求最優(yōu)解問(wèn)題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)。用貪婪法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不考慮各種可能的整體情況，它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間，它采用自頂向下，以迭代的

14、方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。貪婪算法是一種改進(jìn)了的分級(jí)處理方法。其核心是根據(jù)題意選取一種量度標(biāo)準(zhǔn)。然后將這多個(gè)輸入排成這種量度標(biāo)準(zhǔn)所要求的順序，按這種順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最佳解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優(yōu)解的分級(jí)處理方法稱為貪婪算法。對(duì)于一個(gè)給定的問(wèn)題，往往可能有好幾種量度標(biāo)準(zhǔn)。初看起來(lái)，這些量度標(biāo)準(zhǔn)似

15、乎都是可取的，但實(shí)際上，用其中的大多數(shù)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不是問(wèn)題的最優(yōu)解，而是次優(yōu)解。因此，選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪婪算法的核心。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對(duì)某問(wèn)題能選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪婪算法求解則特別有效。最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇即貪婪選擇來(lái)達(dá)到，根據(jù)當(dāng)前狀態(tài)做出在當(dāng)前看來(lái)是最好的選擇，即局部最優(yōu)解選擇，然后再去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。每做一次貪婪選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。3. 基本思路：A）建立數(shù)學(xué)模型來(lái)描述問(wèn)題。B）把求解的問(wèn)題分成若干個(gè)子

16、問(wèn)題。C）對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。D）把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。實(shí)現(xiàn)該算法的過(guò)程：從問(wèn)題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進(jìn)一步 do求出可行解的一個(gè)解元素；由所有解元素組合成問(wèn)題的一個(gè)可行解。方法三：De Bruijn法：在 組合數(shù)學(xué) a k- ary de Bruijn序列B(k, n)秩序 n以荷蘭數(shù)學(xué)家命名 nicolaas Govert de Bruijn是a 循環(huán)序列 指定的 字母表A 以大小 k 為哪些每可能 subsequence 長(zhǎng)度&#

17、160;n 在 A 一次確切地出現(xiàn)作為連貫字符序列。這樣序列有以下物產(chǎn)：其中每一 B(k, n)有長(zhǎng)度 k有 k!/k 分明De Bruijn序列 B(k, n).de Bruijn序列可以通過(guò)采取a修建 漢密爾頓的道路n-尺寸 de Bruijn圖表k 標(biāo)志(或等效地， a Eulerian周期 a (n − 1) -尺寸de Bruijn圖表)，或者通過(guò) 有限領(lǐng)域.例子 每個(gè)邊緣在這張三維的de Bruijn圖表對(duì)應(yīng)于四個(gè)數(shù)字序列： 標(biāo)記端點(diǎn)邊緣離開的

18、三個(gè)數(shù)字被標(biāo)記邊緣的那個(gè)跟隨了。 如果你橫斷被標(biāo)記的邊緣1從000，你到達(dá)在001，從而表明subsequence 0001的出現(xiàn)在de Bruijn序列。 要橫斷每個(gè)邊緣確切地一次是確切使用每一個(gè)16個(gè)四位數(shù)序列一次。例如，假設(shè)我們走以下Eulerian道路：000， 000， 001， 011， 111， 111， 110， 101， 011， 110， 100， 001， 010， 101， 010， 100， 000。這對(duì)應(yīng)于以下de Bruijn序列：0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1八個(gè)端點(diǎn)接下來(lái)出現(xiàn)于序列：0 0 0 0 1 1 1 1 0 1 1 0

19、 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0

20、 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 . 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 . 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1我們?nèi)缓蠡氐匠霭l(fā)點(diǎn)。 每一個(gè)八個(gè)3數(shù)字序列(對(duì)應(yīng)于八個(gè)端點(diǎn))兩次確切地出現(xiàn)和四位數(shù)字的序列的每一十六(對(duì)應(yīng)于16個(gè)邊緣)一次確切地出現(xiàn)。序列可以用于縮短對(duì)a的強(qiáng)力攻擊 PIN-象沒有Enter鍵并且不接受的

21、代碼鎖持續(xù) n 數(shù)字進(jìn)入。 例如，一把數(shù)字式門鎖以一個(gè)四位數(shù)字的代碼將有 B(10， 4)解答，以長(zhǎng)度10000。 所以，只10000則+ 3則= 10003則(作為解答循環(huán))新聞是需要的打開鎖。 嘗試所有代碼將分開地要求4 × 10000 = 40000新聞。De Bruijn的標(biāo)志程序化在通報(bào)對(duì)象附近寫(例如a輪子 機(jī)器人)能使用辨認(rèn)它 角度 通過(guò)審查 n 面對(duì)定點(diǎn)的連貫標(biāo)志。 灰色代碼 能使用作為相似的轉(zhuǎn)臺(tái)式位置內(nèi)碼機(jī)制。（二）將所測(cè)出的的最重的這條鏈所有的結(jié)點(diǎn)全部去掉，再將剩下的堿基對(duì)重新利用ol

22、c法來(lái)組裝。（三）重復(fù)該種實(shí)驗(yàn)3-4次，一定會(huì)有質(zhì)量相同的兩條鏈，則這兩條鏈的組成就是最完整準(zhǔn)確的。42解決基因組中存在重復(fù)片段的問(wèn)題（一）OLC（Overlap/Layout/Consensus）方法 以附錄一中的read1，read2，read3，read4為例d) 將read集合中所有片段fragments兩兩比對(duì)，獲得存在的重疊部分信息;e) 以片段為頂點(diǎn)，重疊的片段相互連接，形成有向圖如圖；在這一步中，phrap算法根據(jù)上一步得到的重疊信息將存在重疊的片段組合起來(lái)形成一個(gè)稱為contig20的結(jié)構(gòu)。f) 在有向圖找出一條路徑，經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次，順序抽取出改路徑上的fragme

23、nts，重疊拼接成“consensus”序列。OLC（Overlap/Layout/Consensus）方式構(gòu)建的read示意圖通過(guò)在有向圖G中查找路徑進(jìn)行DNA序列拼接的時(shí)候，TIGR算法在shotgun集合中對(duì)repats采取如下方法進(jìn)行處理5） 含repeats的fragments留到最后再進(jìn)行拼接，以最大限度的利用不含repeats的fragments中的信息。6） 碰上含repeats的fragments時(shí)，相應(yīng)的提高序列匹配的標(biāo)準(zhǔn)，如果repeats的測(cè)序精度上和正常fragments相比有特別大的差異的話那么就可以排除掉含低測(cè)序精度repeats的fragments7） 比f(wàn)ra

24、gments平均長(zhǎng)度的一半還短的repeats通常不是問(wèn)題因?yàn)檫@種repeats通常會(huì)被一個(gè)fragments所覆蓋，不會(huì)影響到拼接8） 對(duì)repeats的兩端進(jìn)行測(cè)序是很有幫助的這樣能夠幫助那些包含repeats的fragments依據(jù)其兩端來(lái)定位。（二）判斷結(jié)點(diǎn)的重復(fù)次數(shù)，進(jìn)行標(biāo)記，直到檢測(cè)出同一結(jié)點(diǎn)前后兩條有向線段并不相同，才是無(wú)重復(fù)基因組的基因組裝。問(wèn)題二： 基于問(wèn)題一所做的程序，組裝成完整、準(zhǔn)確、連續(xù)的基因組。五、模型的檢驗(yàn)為了檢驗(yàn)我們的模型是否具有較強(qiáng)的適用性，我們利用現(xiàn)有算法和程序，在olc技術(shù)的基礎(chǔ)上，檢測(cè)有向圖并找出測(cè)序中可能出現(xiàn)的個(gè)別堿基對(duì)識(shí)別錯(cuò)誤、基因組中存在重復(fù)片段等復(fù)

25、雜情況。首先兩兩比較，找出重復(fù)片段如圖一，然后將重復(fù)片段作為點(diǎn)，其他的作為線，連成有向圖接著找出質(zhì)量最重的一條線最后扔掉該線所有堿基如圖二，剩下的重復(fù)實(shí)驗(yàn)3-4次，確定正確的序列。隨后將一個(gè)全長(zhǎng)約為120,000個(gè)堿基對(duì)的細(xì)菌人工染色體（BAC）， 采用Hiseq2000測(cè)序儀進(jìn)行測(cè)序，測(cè)序策略以及數(shù)據(jù)格式的簡(jiǎn)要說(shuō)明見附錄一和附錄二，測(cè)得的讀長(zhǎng)數(shù)據(jù)見附錄三，測(cè)序深度（sequencing depth）約為70×，即基因組每個(gè)位置平均被測(cè)到約70次。使之具有良好的組裝效果。以此來(lái)檢驗(yàn)算法的正確性經(jīng)過(guò)與原序列進(jìn)行比較，可以得出我們的模型算法對(duì)于普遍的情況具有一定的適用性。 圖一 圖二隨后

26、利用復(fù)原算法對(duì)其進(jìn)行復(fù)原，以此來(lái)檢驗(yàn)算法。其步驟如下： 我們首先利用PDF XChange Viewer軟件將下列所示PDF文檔轉(zhuǎn)換為bmp圖像，然后利用Photoshop圖像處理軟件利用基準(zhǔn)線和裁剪工具，將其劃分為196*2145像素點(diǎn)的10個(gè)碎紙片，然后隨機(jī)編碼這些碎紙片，利用碎紙片復(fù)原的中文算法對(duì)這些隨機(jī)編碼的碎紙片進(jìn)行復(fù)原。六、模型的評(píng)價(jià)（一）模型的優(yōu)點(diǎn)本文采用優(yōu)化模型。線性規(guī)劃作為一種比較古老的優(yōu)化和決策模型，它發(fā)展的已經(jīng)比較完善，他可以解決很多實(shí)際的問(wèn)題，對(duì)于各種問(wèn)題都是有用，而且解題的過(guò)程簡(jiǎn)單明了，并且對(duì)于不同的問(wèn)題有多種方法進(jìn)行求解，是一種比較實(shí)用

27、且簡(jiǎn)單的方法。它有與問(wèn)題領(lǐng)域無(wú)關(guān)切快速隨機(jī)的搜索能力，搜索從群體出發(fā)，具有潛在的并行性，使用概率機(jī)制進(jìn)行迭代，具有隨機(jī)性，具有可擴(kuò)展性，容易與其他算法結(jié)合。試驗(yàn)次數(shù)較少，可以更快速地組成基因組。（二）模型的缺點(diǎn)但是在實(shí)際應(yīng)用中如果出現(xiàn)大量的數(shù)據(jù)，他就必須借助其他的方法進(jìn)行結(jié)合求解。計(jì)算量也比較大。編程實(shí)現(xiàn)比較復(fù)雜,首先需要對(duì)問(wèn)題進(jìn)行編碼,找到最優(yōu)解之后還需要對(duì)問(wèn)題進(jìn)行解碼，另外三個(gè)算子的實(shí)現(xiàn)也有許多參數(shù),如交叉率和變異率,并且這些參數(shù)的選擇嚴(yán)重影響解的品質(zhì),而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn)。附件一和附件二數(shù)據(jù)龐大，一一輸入程序中，會(huì)比較復(fù)雜。參考文獻(xiàn)1、貪心算法在系統(tǒng)故障診斷策略生成中的應(yīng)

28、用-計(jì)算機(jī)系統(tǒng)應(yīng)用-2011年 第1期2、基于分類樹和貪心算法的測(cè)試數(shù)據(jù)自動(dòng)生成方法-計(jì)算機(jī)工程與設(shè)計(jì)-2011年 第8期 (32)3、淺談貪心算法在排課系統(tǒng)中的應(yīng)用-電腦與電信-2011年 第7期4、許寧；基于OLC算法的軟件可靠性預(yù)測(cè)分析D;西安理工大學(xué);2007年5、張博峰；全基因組DNA測(cè)序中的片段拼接方法及其并行處理D；長(zhǎng)沙；國(guó)防科學(xué)技術(shù)大學(xué)；2003附錄#include<iostream>using namespace std;const int W=88;const int L=46847;class QYpublic: QY() int i,j; for(i=0;i<L;i+)for(j=0;j<w;j+)Aij=0；;OLC();Show();input();private:int N;int n; int ALW; int BLW; int CLW;int AALW; int BBLW; int CCLW;int pathLL;int distanceLL; ;QY:input() int a,b,c,n,i,j,k=0,p,q;int MM=20000000;int allMM;int bllM