最小連通圖問(wèn)題dna表面計(jì)算

《最小連通圖問(wèn)題dna表面計(jì)算》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、最小連通圖問(wèn)題DNA表面計(jì)算　　摘要：現(xiàn)在探討一種基于芯片的DNA表面計(jì)算與電子計(jì)算機(jī)雜合計(jì)算的方法，用于完全問(wèn)題的計(jì)算.該芯片模型通過(guò)相應(yīng)數(shù)據(jù)庫(kù)的設(shè)計(jì)來(lái)排布數(shù)據(jù)，依據(jù)不同的問(wèn)題進(jìn)行算法設(shè)計(jì)，在通用的計(jì)算芯片表面進(jìn)行計(jì)算反應(yīng)，計(jì)算所得芯片圖像，通過(guò)專(zhuān)門(mén)設(shè)計(jì)的圖像處理計(jì)算軟件利用計(jì)算機(jī)進(jìn)行進(jìn)一步計(jì)算，可以直接得到相應(yīng)問(wèn)題的完全解.與以往的DNA計(jì)算方法相比，DNA表面計(jì)算芯片方法可以將問(wèn)題的指數(shù)運(yùn)算轉(zhuǎn)化成單項(xiàng)式運(yùn)算，具有操作簡(jiǎn)單，不依靠酶反應(yīng)過(guò)程，假陽(yáng)性率低等優(yōu)點(diǎn)，并可通過(guò)軟件與電子計(jì)算機(jī)相結(jié)合，充分發(fā)揮DNA計(jì)算的并行計(jì)算優(yōu)勢(shì)和電子計(jì)算機(jī)的快速數(shù)據(jù)

2、處理能力的優(yōu)勢(shì)，實(shí)現(xiàn)良好的雜合.關(guān)鍵詞：最小連通問(wèn)題Adleman-Lipton模型DNA表面計(jì)算中圖分類(lèi)號(hào)：Q811.211文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1007-9416（2013）01-0216-028目前，DNA計(jì)算機(jī)相對(duì)于電子計(jì)算機(jī)有兩點(diǎn)不足：（1）DNA計(jì)算需要以指數(shù)級(jí)增長(zhǎng)的DNA分子數(shù)。但事實(shí)上如此之大的DNA鏈數(shù)日難以被滿足；（2）DNA計(jì)算中的平均錯(cuò)誤率的存在。比如不正確的雜交、可能發(fā)生的寡核苷酸的內(nèi)部二次結(jié)構(gòu)等都會(huì)降低最后結(jié)果的可靠性。這兩個(gè)缺點(diǎn)限制了DNA計(jì)算解決大型復(fù)雜問(wèn)題的能力。而DNA表面計(jì)算是克服這上述缺點(diǎn)的一種有效辦法。它

3、具有方便樣本處理、減少了樣本處理中的丟失、減少了寡核苷酸間的干擾、方便了實(shí)驗(yàn)中每一步中的DNA分子的純化。通過(guò)化學(xué)反應(yīng)用不同的活化試劑在載體表面鍵合上各種各樣的活性基團(tuán)，以便與配基共價(jià)結(jié)合，形成具有不同生物特異性的親和載體，用來(lái)固定不同的活性生物分子，如蛋自質(zhì)、核酸等。通過(guò)這種方法固定在載體表面上的DNA分子，具有能夠承受在表面上進(jìn)行的各種加熱、清洗及其它生化反應(yīng)操作的能力。DNA表面計(jì)算方法具體描述如下：（1）分析完全問(wèn)題，其完全數(shù)據(jù)池中的數(shù)據(jù)轉(zhuǎn)化可用0和1按序表達(dá)的方式。（2）將完全問(wèn)題的完全數(shù)據(jù)池轉(zhuǎn)化為序列數(shù)據(jù)庫(kù)。個(gè)變量的完全問(wèn)題，其完全數(shù)據(jù)

4、池包含個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)由個(gè)變量的0或1兩種狀態(tài)按序組成。將這樣的完全數(shù)據(jù)池制作成陣列數(shù)據(jù)庫(kù)，將數(shù)據(jù)庫(kù)中的每個(gè)陣列由個(gè)分單元構(gòu)成，每個(gè)分單元代表完全數(shù)據(jù)池中的一個(gè)數(shù)據(jù)，即分單元與數(shù)據(jù)之間可尋址，每個(gè)分單元由4個(gè)點(diǎn)組成，則整個(gè)陣列包含64個(gè)取值為0或1的點(diǎn)，則排布為點(diǎn)陣。6個(gè)變量的完全問(wèn)題的陣列由64個(gè)分單元構(gòu)成，每個(gè)分單元由6個(gè)點(diǎn)組成，則整個(gè)陣列包含384個(gè)取值為0或1的點(diǎn)，可排布為點(diǎn)陣。8（3）將陣列數(shù)據(jù)庫(kù)中的陣列轉(zhuǎn)化為DNA計(jì)算芯片。將完全問(wèn)題陣列中的數(shù)據(jù)映射為寡核苷酸序列并排布在芯片上，映射關(guān)系如下：1）個(gè)變量，每個(gè)變量有0和1兩種狀態(tài)，則共有

5、中狀態(tài)，分別一一對(duì)應(yīng)為種不同的寡核苷酸序列。例如三個(gè)變量，則，，，，，六種狀態(tài)分別一一對(duì)應(yīng)為6種不同的寡核苷酸序列。2）陣列中每個(gè)分單元由個(gè)0或1按序構(gòu)成，則按序索引中規(guī)定的對(duì)應(yīng)關(guān)系，從而將每個(gè)分單元對(duì)應(yīng)于依序排列的個(gè)寡核苷酸序列，每個(gè)序列成為芯片上的一個(gè)點(diǎn)；（4）根據(jù)完全問(wèn)題的類(lèi)型，設(shè)計(jì)相應(yīng)的DNA芯片計(jì)算算法，編寫(xiě)專(zhuān)用的圖像處理和后續(xù)計(jì)算軟件。（5）對(duì)給定的芯片算法，將預(yù)定合成的有標(biāo)記的寡核苷酸鏈混合，與DNA計(jì)算芯片發(fā)生雜交反應(yīng)，得到雜交圖像。標(biāo)記物可以是熒光，同位素，化學(xué)反應(yīng)的底物等等，輸出的雜交圖像可以是熒光圖像，同位素圖像，化學(xué)發(fā)光圖像

6、等等，也可以是電學(xué)信號(hào)。（6）采用針對(duì)一類(lèi)問(wèn)題算法設(shè)計(jì)的專(zhuān)用軟件處理得到的雜交圖像，進(jìn)行計(jì)算，尋址，得到該類(lèi)問(wèn)題的全解。8如果一個(gè)圖中任意兩個(gè)頂點(diǎn)都可以用一條道路把這兩個(gè)點(diǎn)連接，則這樣的圖稱為連通圖。用電子計(jì)算機(jī)判斷一個(gè)圖是不是連通的并且把能連接所有頂點(diǎn)并且包含最少邊的最小連通圖迅速找出來(lái)，在頂點(diǎn)和邊數(shù)比較多的情況下，并不是件容易的事情；這就是一個(gè)典型的問(wèn)題。而現(xiàn)在我們就可以用新的表面計(jì)算快速地來(lái)解決這個(gè)問(wèn)題。而若是一個(gè)圖是連通的，必須能滿足三點(diǎn)：（1）對(duì)于交于同一點(diǎn)的幾條邊來(lái)說(shuō)，應(yīng)保證其中至少一條在連通圖中存在，才能使這點(diǎn)在連通圖中存在。（2）對(duì)

7、于最小的連通圖，不能有環(huán)出現(xiàn)，因此要把存在環(huán)的情況剔除。（3）對(duì)于個(gè)點(diǎn)的圖來(lái)說(shuō)，其連通圖連接的邊數(shù)應(yīng)為條邊。因此要選出邊為的鏈。滿足以上三點(diǎn)的情況即是無(wú)權(quán)值的最小連通圖問(wèn)題的解。例如：求下圖的最小連通圖：城市間可以修建，，，，，，，八條管道，每條管道的總成本一樣，問(wèn)有多少種修建方法使這些城市都連接起來(lái)，且管道數(shù)目最少（如圖1）：用DNA表面計(jì)算芯片計(jì)算此問(wèn)題的模型和步驟如下：（1）此問(wèn)題包括8條邊，即八個(gè)變量。首先定義一種完全數(shù)據(jù)池的映射策略：1）邊分別用，，，，，，，表示。2）定義任一條邊有兩種賦值，當(dāng)該條邊在圖中的邊的子集時(shí)，則取值為1，否則取

8、值為0。3）將邊的子集映射為由1和0組成的數(shù)據(jù)，順序依次為。例如：邊的集合映射為二進(jìn)制數(shù)101100000。（2）在以上的