摘要:設(shè)計(jì)gc含量恒定且滿足寡核苷酸與Watson-Crick互補(bǔ)物之間漢明距離約束的大型寡核苷酸文庫(kù)樊诺，對(duì)于降低雜交錯(cuò)誤具有重要意義DNA計(jì)算，DNA微陣列技術(shù)，分子條形碼技術(shù)。人們研究了構(gòu)建這種寡核苷酸庫(kù)的各種技術(shù)，從通過(guò)隨機(jī)局部搜索的算法構(gòu)建到通過(guò)編碼理論的理論構(gòu)建瞎访。提出了一種新的隨機(jī)局部搜索方法，提高了搜索效率
化學(xué)合成的寡核苷酸(短單鏈DNA)作為DNA微陣列技術(shù)中的探針[3]忿晕、[4]和分子條碼[5]-[7]中的標(biāo)記装诡，是DNA計(jì)算[1]、[2]信息存儲(chǔ)的重要結(jié)構(gòu)践盼。DNA在這些應(yīng)用中的關(guān)鍵特性是寡核苷酸與它們的沃森-克里克互補(bǔ)物特異性雜交并形成穩(wěn)定的雙鏈[8]的趨勢(shì)鸦采。
為了降低寡核苷酸文庫(kù)錯(cuò)誤雜交的概率，必須滿足的基本約束條件中咕幻，以下是特別重要的:
(i)文庫(kù)中的兩個(gè)寡核苷酸必須不同渔伯。
(ii)庫(kù)中的寡核苷酸必須不同于庫(kù)中的另一個(gè)寡核苷酸(Watson-Crick)的補(bǔ)體。
(iii)文庫(kù)中每個(gè)寡核苷酸都有相似的熔化溫度肄程。
(iv) 寡核苷酸不能以使其失去化學(xué)活性的方式折疊回自身锣吼。
摘要針對(duì)寡核苷酸序列設(shè)計(jì)問(wèn)題，提出了一種新的隨機(jī)局部搜索方法蓝厌。該方法得到了許多破紀(jì)錄的寡核苷酸文庫(kù)玄叠。通過(guò)計(jì)算圖上最大群的窮舉搜索算法，得到了幾個(gè)最優(yōu)寡核苷酸庫(kù).
2,定義&符號(hào)
我們將寡核苷酸建模為字母表上的序列
Σ= { A拓提、C读恃、G、T }代态。
如果σ∈Σn,序列的元素的位置i,用σi來(lái)標(biāo)示σ寺惫。兩個(gè)序列之間的漢明距離σ,τ∈Σn,表示dH(σ,τ),,也就是說(shuō)位置的數(shù)量是不同的，當(dāng)σ和τ不相同
d H (σ,τ) = |{1 ≤ i ≤ n : σ i 6= τ i }|.
We model oligonucleotides as sequences over the alphabet
Σ = {A,C,G,T}. If σ ∈ Σ n , the element in position i of the
sequence σ is denoted σ i . The Hamming distance between
two sequences σ,τ ∈ Σ n , denoted d H (σ,τ), is the number of
positions where σ and τ differ, that is,
d H (σ,τ) = |{1 ≤ i ≤ n : σ i 6= τ i }|.
此后蹦疑，小寫(xiě)的希臘字母被用來(lái)表示寡核苷酸西雀，如果沒(méi)有其他說(shuō)明，則假定它們屬于一個(gè)通用集合ζ.
一個(gè)n-m的寡核苷酸庫(kù)ζ ? Σ n滿足所有要求歉摧、
被稱為一個(gè) (n,d,w)-DNA密碼艇肴。注意,第二個(gè)約束也同樣為了τ=σ。如果ζ?Σn只滿足漢明距離與恒gc含量約束叁温，我們稱ζ為弱(n,d,w)-DNA密碼豆挽。
三。設(shè)計(jì)了一種算法
用于確定大小為A的(n,d,w) DNA編碼的隨機(jī)局部搜索算法通常采用以下框架券盅。我們從一個(gè)子集開(kāi)始ζ? Σn 然后我們反復(fù)修改ζ，直到我們得到一個(gè)長(zhǎng)度為A的(n,d,w) DNA code膛檀。修改步驟包括移動(dòng)ζ到一個(gè)隨機(jī)的鄰域ζ’, 其接受概率由其接近大小為A的(n,d,w)-DNA編碼決定锰镀。設(shè)計(jì)DNA編碼隨機(jī)局部搜索算法的關(guān)鍵在于:
1.良好的初始化程序;
2.N(ζ)為ζ的鄰域;
3.成本(ζ)娘侍，表示ζ與解決方案的接近程度;
4.f，接受概率函數(shù);
5.合理有效的stop標(biāo)準(zhǔn)
