利用統(tǒng)計(jì)語言模型對(duì)GenoCAD設(shè)計(jì)結(jié)果進(jìn)行優(yōu)化

方　剛，張社民

(1.西安文理學(xué)院 生物與環(huán)境工程學(xué)院， 陜西 西安 710065； 2.陜西理工大學(xué) 管理學(xué)院， 陜西 漢中 723001)

?

利用統(tǒng)計(jì)語言模型對(duì)GenoCAD設(shè)計(jì)結(jié)果進(jìn)行優(yōu)化

方剛1，張社民2

(1.西安文理學(xué)院 生物與環(huán)境工程學(xué)院， 陜西 西安 710065； 2.陜西理工大學(xué) 管理學(xué)院， 陜西 漢中 723001)

GenoCAD(www.genocad.com)是一種基于Web的免費(fèi)合成生物學(xué)設(shè)計(jì)軟件，使用它可以進(jìn)行表達(dá)載體及人工基因網(wǎng)絡(luò)設(shè)計(jì)。不斷地點(diǎn)擊代表各種合成生物學(xué)標(biāo)準(zhǔn)“零件”的圖標(biāo)，以一種語法進(jìn)行設(shè)計(jì)，最后就可以得到由數(shù)十個(gè)功能片段組成的復(fù)雜質(zhì)粒載體。但是一般來講在GenoCAD中，每一類的合成生物學(xué)標(biāo)準(zhǔn)“零件”數(shù)量眾多。隨著這些標(biāo)準(zhǔn)“零件”的不斷開發(fā)，其數(shù)量也在進(jìn)一步增加，目前選擇合適的“零件”組裝成功能性的質(zhì)粒載體費(fèi)時(shí)費(fèi)力并且容易發(fā)生錯(cuò)誤。在進(jìn)行載體設(shè)計(jì)的最后階段，從眾多的“零件”中選擇合適的往往比較困難。為解決這一問題，采用自然語言處理的統(tǒng)計(jì)語言模型，并以該模型為基礎(chǔ)應(yīng)用動(dòng)態(tài)規(guī)劃算法優(yōu)化質(zhì)粒載體設(shè)計(jì)，從眾多的選項(xiàng)中找出最優(yōu)者。利用這一方法可以減少進(jìn)行生物學(xué)實(shí)驗(yàn)的冗余操作，從而減少載體構(gòu)建過程中的花費(fèi)。

合成生物學(xué)；統(tǒng)計(jì)語言模型；動(dòng)態(tài)規(guī)劃算法；GenoCAD

一、引 言

由美國(guó)弗吉尼亞理工大學(xué)生物信息研究所開發(fā)維護(hù)的合成生物學(xué)設(shè)計(jì)工具GenoCAD是基于網(wǎng)絡(luò)環(huán)境的而且免費(fèi)使用[1]。這一工具軟件不僅僅用于表達(dá)載體的設(shè)計(jì)，而且還可以用于基因及代謝網(wǎng)絡(luò)研究[2-3]。它通過編制一定的“語法”，將每一個(gè)合成生物學(xué)標(biāo)準(zhǔn)“零件”看做一個(gè)詞，用來設(shè)計(jì)所需的合成生物學(xué)構(gòu)件[4]。在GenoCAD的設(shè)計(jì)中，啟動(dòng)子、核糖體結(jié)合位點(diǎn)、基因及終止子都屬于各自的“詞類”，然后依據(jù)特殊編制的語法來設(shè)計(jì)分子生物學(xué)組件[5-6]。設(shè)計(jì)者們往往將已有的生物序列拆成“零件”來作為合成生物學(xué)的標(biāo)準(zhǔn)“零件”[7]，而當(dāng)設(shè)計(jì)者將這些屬于不同詞類的標(biāo)準(zhǔn)“零件”進(jìn)行組裝時(shí)，其過程通常耗時(shí)、費(fèi)力而且容易發(fā)生錯(cuò)誤。為了克服這些問題，研究者們引入了一些組裝標(biāo)準(zhǔn)，比如BioBrick基金(BioBrickFoundation，BBF)倡導(dǎo)的一些標(biāo)準(zhǔn)。屬于同一組裝標(biāo)準(zhǔn)的“零件”兩側(cè)序列包含相應(yīng)的限制性酶切位點(diǎn)，使用同一組限制性內(nèi)切酶和連接酶可以將同一標(biāo)準(zhǔn)的“零件”連接起來[8-9]。在一個(gè)設(shè)計(jì)軟件中，也會(huì)模擬使用這些組裝標(biāo)準(zhǔn)。對(duì)這些合成生物學(xué)標(biāo)準(zhǔn)“零件”的模擬組裝可以在計(jì)算機(jī)中完全自動(dòng)化[10]，但是這樣只是考慮了最基本的“語法”，也忽略了以往的組裝經(jīng)驗(yàn)。在GenoCAD中，使用者可以根據(jù)自己需要編制“語法”，再根據(jù)一些具有生物學(xué)意義的設(shè)計(jì)規(guī)則變換設(shè)計(jì)結(jié)構(gòu)，最后選擇“零件”完成設(shè)計(jì)[11]。但是越來越多的“零件”被輸入數(shù)據(jù)庫，在設(shè)計(jì)的最后一步，設(shè)計(jì)者往往不知道選擇哪個(gè)“零件”更為合適。為了解決這個(gè)問題，統(tǒng)計(jì)語言模型(statisticallanguagemodel，SLM)被引入設(shè)計(jì)中。統(tǒng)計(jì)語言模型(SLM)最初用于自然語言識(shí)別[12]，它用來估算一組詞串成為一個(gè)正確語句的概率的大小。它最初也是目前最主要的應(yīng)用是語音識(shí)別，除此之外還應(yīng)用于機(jī)器翻譯、分詞、智能輸入法及文本語音轉(zhuǎn)換。本文介紹的統(tǒng)計(jì)語音模型通過統(tǒng)計(jì)BioBrick合成生物學(xué)標(biāo)準(zhǔn)件的一些參數(shù)，將BioBrick的組裝過程轉(zhuǎn)化為統(tǒng)計(jì)語音模型，然后使用動(dòng)態(tài)規(guī)劃算法找出合適的“零件”組裝成最后的表達(dá)載體而完成設(shè)計(jì)。這一算法將iGEM(InternationalGeneticallyEngineeredMachineCompetition)競(jìng)賽設(shè)計(jì)的經(jīng)驗(yàn)考慮進(jìn)來，以減少時(shí)間和花費(fèi)。這一方法不僅可以用來優(yōu)化其它工具軟件的設(shè)計(jì)方案，而且可以獨(dú)立使用設(shè)計(jì)新的基因表達(dá)載體及分子生物學(xué)組件。

二、材料方法

通過鏈接http://parts.igem.org/das/parts/entry_points/ 下載BioBrick合成生物學(xué)組件信息，2014年1月的版本包含7 242個(gè)合成生物學(xué)組件。編寫一個(gè)Perl腳本通過鏈接http://parts.igem.org/das/parts/features/?segment=part# 分析并提取每個(gè)組件的信息。將每個(gè)組件的信息分解排列成特有的結(jié)構(gòu)輸入MySQL數(shù)據(jù)庫。輸入數(shù)據(jù)庫后共分解提取出 75 744個(gè)“零件”，這些“零件”包括基礎(chǔ)“零件” (啟動(dòng)子、核糖體結(jié)合位點(diǎn)、基因編碼序列、終止子及質(zhì)粒序列) 和復(fù)合“零件”。這些復(fù)合“零件”依然由基礎(chǔ)“零件”組裝而成。通過查詢MySQL數(shù)據(jù)庫提取出這些基礎(chǔ)“零件”并統(tǒng)計(jì)它們的使用頻數(shù)。同時(shí)編寫一個(gè)Perl腳本和一些SQL語句分析復(fù)合“零件”，統(tǒng)計(jì)出相鄰接的兩個(gè)基礎(chǔ)“零件”的使用頻數(shù)。通過查詢數(shù)據(jù)庫，共提取出1 682個(gè)基礎(chǔ)“零件”并符合RFC23組裝標(biāo)準(zhǔn)[13]。這意味著這些基礎(chǔ)“零件”序列中(除了兩側(cè)的連接序列)不會(huì)包含這一組裝標(biāo)準(zhǔn)使用的限制性酶切位點(diǎn)。這1 682個(gè)基礎(chǔ)“零件”包含405個(gè)啟動(dòng)子，42個(gè)核糖體結(jié)合位點(diǎn)，57個(gè)終止子以及1 178個(gè)基因序列。這些基礎(chǔ)“零件”將被用來設(shè)計(jì)基因表達(dá)載體。同時(shí)每一個(gè)基礎(chǔ)“零件”的使用頻率和每一對(duì)基礎(chǔ)“零件”的使用頻率都可以被計(jì)算出來。

(一)語法模型

如何編制設(shè)計(jì)合成生物學(xué)組件的語法在以前的文獻(xiàn)中已予以詳細(xì)描述[14]，可以根據(jù)不同的目的編制不同的語法。本文使用的語法與文獻(xiàn)[14]使用的上下文無關(guān)的語法類似(見表1)，其中規(guī)則1表示開始設(shè)計(jì)，規(guī)則2表示將一個(gè)表達(dá)盒變成兩個(gè)，規(guī)則3表示翻轉(zhuǎn)一個(gè)表達(dá)盒，規(guī)則4表示將一個(gè)表達(dá)盒變成一個(gè)啟動(dòng)子加一個(gè)閱讀框加一個(gè)終止子，規(guī)則6表示將一個(gè)閱讀框變成兩個(gè)，規(guī)則7表示將一個(gè)閱讀框變成一個(gè)核糖體結(jié)合位點(diǎn)與一個(gè)基因，規(guī)則8表示將一個(gè)終止子變成兩個(gè)，規(guī)則9表示將一個(gè)基因變成兩個(gè)。與文獻(xiàn)[14]不同的是增加了第5條規(guī)則以表達(dá)融合蛋白，它使一個(gè)表達(dá)盒變成一個(gè)啟動(dòng)子加一個(gè)閱讀框，以便在一個(gè)表達(dá)盒里讓兩個(gè)蛋白融合表達(dá)。表1給出了本文使用的詳細(xì)語法。

(二)數(shù)學(xué)模型

在一些設(shè)計(jì)軟件中，比如GenoCAD在完成設(shè)計(jì)的最后一步設(shè)計(jì)者往往要從大量的基礎(chǔ)“零件”中選擇合適的“零件”以完成設(shè)計(jì)(圖1)，這一過程往往是困難的。為解決這一問題，本文引入了在語音識(shí)別、機(jī)器翻譯、智能輸入法中廣泛應(yīng)用的統(tǒng)計(jì)語言模型。

表1　詳細(xì)語法表

圖1　在設(shè)計(jì)軟件GenoCAD最后一步的多個(gè)選項(xiàng)

在這一模型中，一個(gè)句子(sentence，S)是否有意義并且合理基于其出現(xiàn)的概率。一個(gè)句子由一系列的詞組成，在本文中一個(gè)“句子”S就是一個(gè)由基礎(chǔ)“零件”構(gòu)成的生物學(xué)組件，這些基礎(chǔ)“零件”就是組成“句子”的詞，一個(gè)基礎(chǔ)“零件”part就是一個(gè)詞。因此，S=part1,part2,…,partn需要知道其發(fā)生概率P(S)的大小:

P(S)=P(part1,part2,…,partn)

(1)

根據(jù)條件概率公式有：

P=(part1,part2,…,partn)

=P(part1)P(part2|part1)P(part3|part1,part2)…P(partn|part1,part2,…,partn-1)

(2)

式(2)中，P(part1) 指一個(gè)基礎(chǔ)“零件”在一個(gè)設(shè)計(jì)中出現(xiàn)的概率。P(part2︱part1)指part1出現(xiàn)在part2之前part2出現(xiàn)的概率。根據(jù)式(2)，partn出現(xiàn)的概率由所有出現(xiàn)在它之前的基礎(chǔ)“零件”確定。其中 P(part1)andP(part2︱part1) 容易計(jì)算，但是計(jì)算P(part3︱part1,part2)的難度較大，而計(jì)算P(partn︱part1,part2,…,partn-1) 將非常困難，因?yàn)闋砍兜淖兞刻鄬?dǎo)致條件過于復(fù)雜而難以估算?；隈R爾科夫假設(shè)，可以認(rèn)為一個(gè)“零件”在一個(gè)設(shè)計(jì)中出現(xiàn)的概率僅僅與它相鄰的前一個(gè)“零件”相關(guān)。因此式(2)可以簡(jiǎn)化為：

P=(S)

=P(part1)P(part2|part1)P(part3|,part2)…P(parti|parti-1)…P(partn|partn-1)

(3)

現(xiàn)在P(S)即一個(gè)“句子”發(fā)生的概率就可以被計(jì)算出來了。式(3)就是統(tǒng)計(jì)語言模型中的二元模型(BigramModel)。因此，根據(jù)條件概率公式：

(4)

兩個(gè)相鄰基礎(chǔ)“零件”出現(xiàn)的頻率及單個(gè)基礎(chǔ)“零件”出現(xiàn)的頻率是可以被計(jì)算出來的，我們用它們來估計(jì)式(4)的條件概率?？傻茫?/p>

(5)

根據(jù)式(5)，式(3)中任何一個(gè)成份都可以被計(jì)算出來。

設(shè)計(jì)的最后一步(圖1)，可以有很多個(gè)基礎(chǔ)“零件”組合而成最后的設(shè)計(jì)。但是哪一種組合最合理且最有意義？根據(jù)統(tǒng)計(jì)語言模型理論，概率最大那一個(gè)將是最合理且最有意義的。在如圖1所示網(wǎng)格結(jié)構(gòu)中，可以有很多個(gè)候選路徑產(chǎn)生“句子”，一條路徑產(chǎn)生一個(gè)“句子”，一個(gè)“句子”就是一個(gè)設(shè)計(jì)(apath=a S=part1,part2,…,partn)。 最優(yōu)的路徑由PATH表示：

為避免計(jì)算時(shí)內(nèi)存溢出，我們對(duì)P(S)取對(duì)數(shù)值：

PATH

(6)

根據(jù)式(5)，得到了式(7)和式(8)

(7)

(8)

因?yàn)槲覀儚囊粋€(gè)相對(duì)稀疏的語料庫中提取參數(shù)，零概率問題不可避免。為克服這一問題我們采用卡茨退避法進(jìn)行數(shù)據(jù)平滑[15]。式(7)和(8)將被用來計(jì)算式(6)中各個(gè)成分的值從而得出最優(yōu)路徑。最優(yōu)路徑PATH將是在所有路徑中具有最大概率的那一個(gè)。這里使用動(dòng)態(tài)規(guī)劃算法找出最優(yōu)路徑PATH。

(三)算法

在如圖1的網(wǎng)格結(jié)構(gòu)中找出最優(yōu)的路徑，這一路徑將由一系列基礎(chǔ)“零件”構(gòu)成而它具有最大的出現(xiàn)概率。找最優(yōu)路徑的過程就是如何解式(6)，具體的算法還是源于維特比算法[16]，由三個(gè)步驟組成：

第一步，建立候選網(wǎng)格。每一類基礎(chǔ)“零件”對(duì)應(yīng)一列，而每列中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)基礎(chǔ)“零件”。在網(wǎng)格的開始和結(jié)束添加BEG和END列。在這兩列中兩個(gè)虛擬節(jié)點(diǎn)B和E被添加進(jìn)來(圖 2)， 每一個(gè)節(jié)點(diǎn)是一個(gè)三元組 ，三元組的第一元素name是基礎(chǔ)“零件”的序列號(hào)，這一序列號(hào)在數(shù)據(jù)庫中是唯一的。

全區(qū)設(shè)立有自治區(qū)級(jí)、市級(jí)、縣級(jí)、鄉(xiāng)鎮(zhèn)四級(jí)社會(huì)保險(xiǎn)征收服務(wù)機(jī)構(gòu)，而稅務(wù)部門根據(jù)稅源變化的特點(diǎn)，已收縮鄉(xiāng)鎮(zhèn)征收機(jī)構(gòu)，大多集中到縣級(jí)，對(duì)城鄉(xiāng)居民養(yǎng)老保險(xiǎn)和醫(yī)療保險(xiǎn)，尤其鄉(xiāng)鎮(zhèn)居民保險(xiǎn)的征收管理帶來一定程度的不便。

第二步，填充網(wǎng)格。從左至右填充網(wǎng)格，對(duì)于每一個(gè)三元組，V和P被計(jì)算出來并填充相應(yīng)值。V由相鄰兩列的任意兩個(gè)節(jié)點(diǎn)進(jìn)行組合運(yùn)算的最大值填充，P將存儲(chǔ)與當(dāng)前節(jié)點(diǎn)組合運(yùn)算產(chǎn)生最大值的前一個(gè)節(jié)點(diǎn)的地址信息。

1.對(duì)第一列，節(jié)點(diǎn)B使V=0且P=NULL。

2.對(duì)第二列每一節(jié)點(diǎn)三元組 (name∈{I0500,R0011, … ,R0040, …})將與B節(jié)點(diǎn)組合計(jì)算其V值和P。

V=VB+logP(part)=logP(part)

P=address_of_B

3.對(duì)第三列每一節(jié)點(diǎn)三元組 (name∈{R0032,B0034, … ,B0041, …}) 將與第二列中的所有節(jié)點(diǎn)組合并計(jì)算其V值和P。

V=max{Vprior+logP(part|partprior)}

P=address_where_V_comes_from

4.重復(fù)3，在當(dāng)前列中的每一個(gè)節(jié)點(diǎn)都與前一列的每一個(gè)節(jié)點(diǎn)組合計(jì)算其V值和P。

5.在END列，E節(jié)點(diǎn)的V將由選自前一列的最大值填充，P將存儲(chǔ)前一列那個(gè)最大值節(jié)點(diǎn)的地址信息。

第三步，回溯找出最優(yōu)路徑PATH。從節(jié)點(diǎn)E開始不斷找出前面節(jié)點(diǎn)的P (圖 2)，最終最優(yōu)路徑PATH將是具有最大概率的那一個(gè)，其產(chǎn)生的“句子”S就是最后設(shè)計(jì)的具有生物學(xué)意義的分子生物學(xué)組件。如果S的長(zhǎng)度是L而一列中節(jié)點(diǎn)的個(gè)數(shù)最多是D，該算法的算法復(fù)雜度是O(L·D2)，而窮舉算法的算法復(fù)雜度是O(DL)。

三、結(jié) 果

為展示如何將BioBrick基礎(chǔ)“零件”組裝成功能性的合成生物學(xué)組件，我們挑選了一個(gè)可以產(chǎn)生香蕉氣味的質(zhì)粒 (http://parts.igem.org/Part:BBa_J45900) 。該質(zhì)粒由麻省理工學(xué)院參加2006年iGEM競(jìng)賽的參賽隊(duì)設(shè)計(jì)并實(shí)施。該組件包含兩個(gè)表達(dá)盒：一個(gè)盒子包含BAT2 和THI3 基因，另一個(gè)表達(dá)盒的產(chǎn)物催化前面基因的產(chǎn)物而使大腸桿菌發(fā)出香蕉的氣味，最后的設(shè)計(jì)如圖1所示。

當(dāng)確定了我們要表達(dá)的基因，該裝配算法由一個(gè)Perl腳本執(zhí)行，首次執(zhí)行算法它給出序列R0040-B0034-J45008-B0030-J45009-R0040-B0034-J45014-B0010-B0012。

第二次執(zhí)行算法，排除核糖體結(jié)合位點(diǎn)B0034，算法給出序列R0040-B0030-J45008-B0030-J45009-R0040-B0030-J45014-B0010-B0012。

第三次執(zhí)行算法，當(dāng)在第一列排除啟動(dòng)子R0040，算法給出序列R0011-B0030-J45008-B0030-J45009-R0040-B0030-J45014-B0010-B0012。

由這些基礎(chǔ)“零件”構(gòu)成的序列就是產(chǎn)生香蕉氣味這一合成生物學(xué)組件的真實(shí)組成。如果進(jìn)行其它的設(shè)計(jì)并執(zhí)行算法，該方法將給出一個(gè)優(yōu)化的結(jié)果，這一結(jié)果采用了以往設(shè)計(jì)的經(jīng)驗(yàn)。如果需要更多的選項(xiàng)，我們可以排除一些“零件”并重新執(zhí)行算法，它將給出其它一些優(yōu)化的結(jié)果供選擇。如果已知某些“零件”是確定相鄰接的，使用者可以先確定這些連接然后執(zhí)行算法。

圖2　建立網(wǎng)格、填充網(wǎng)格及回溯過程圖

四、討 論

本文通過將BioBrick基礎(chǔ)“零件”的裝配過程轉(zhuǎn)化成一個(gè)二元統(tǒng)計(jì)語言模型，然后執(zhí)行動(dòng)態(tài)規(guī)劃算法找出最優(yōu)的裝配結(jié)果。算法可被迭代從而給出不同的優(yōu)化結(jié)果供選擇。這一方法不僅可以用來優(yōu)化其它合成生物學(xué)軟件設(shè)計(jì)結(jié)果，而且可以獨(dú)立使用來模擬裝配合成生物學(xué)基因片段產(chǎn)生表達(dá)載體。依據(jù)一定的語法輸入不同類的合成生物學(xué)基礎(chǔ)“零件”，算法依據(jù)以往經(jīng)驗(yàn)自動(dòng)選擇合適的“零件”裝配成合成生物學(xué)組件。采用這一方法可以減少真實(shí)裝配過程的冗余操作，從而節(jié)省時(shí)間和費(fèi)用。如前所述，該方法采用二元統(tǒng)計(jì)語言模型，這意味著每一個(gè)“零件”只與它前面一個(gè)相鄰的“零件”有聯(lián)系。然而在真實(shí)的分子生物學(xué)環(huán)境中，一個(gè)基因能否高效表達(dá)不僅與其核糖體結(jié)合位點(diǎn)有關(guān)，而且與其啟動(dòng)子有關(guān)?？紤]N元模型，這意味著每一個(gè)“零件”與它前面N-1個(gè)“零件”有關(guān)系，但是這時(shí)條件概率是非常難以計(jì)算的。當(dāng)N=3或4時(shí)，盡管在其它統(tǒng)計(jì)語音模型應(yīng)用范例中(如機(jī)器翻譯、分詞、智能輸入法)準(zhǔn)確率會(huì)大大提高，但是計(jì)算量也大大增加，這時(shí)需要功能強(qiáng)大的計(jì)算機(jī)[12]121-122。下一步，我們將開發(fā)一個(gè)3元模型并且將質(zhì)粒序列考慮進(jìn)來，從而更高效地模擬合成生物學(xué)基因片段的組裝過程并使真實(shí)的組裝變得更為方便快捷。

當(dāng)計(jì)算條件概率時(shí)，本文使用了卡茨退避數(shù)據(jù)平滑技術(shù)解決零概率問題。目前統(tǒng)計(jì)語言模型在合成生物學(xué)中鮮有應(yīng)用，我們無從知道哪一種數(shù)據(jù)平滑技術(shù)更有效。下一步開發(fā)3、4元模型時(shí)，我們將擴(kuò)大語料庫，并考慮Good-Turing估計(jì)、線性插值法等數(shù)據(jù)平滑技術(shù)以提高準(zhǔn)確率[17-18]。正如前述，我們從iGEM(InternationalGeneticallyEngineeredMachineCompetition)網(wǎng)站下載了一個(gè)相對(duì)稀疏的語料庫。目前我們考慮將語料庫擴(kuò)展到常用的、商業(yè)化的表達(dá)載體上統(tǒng)計(jì)相應(yīng)的參數(shù)，這樣統(tǒng)計(jì)語言模型可以在合成生物學(xué)中更廣泛地應(yīng)用并得到檢驗(yàn)。但是對(duì)這些合成生物學(xué)片段進(jìn)行描述的術(shù)語還沒有完全統(tǒng)一，因此發(fā)展合成生物學(xué)開放語言(SyntheticBiologyOpenLanguage，SBOL)變得十分必要。

感謝美國(guó)弗吉尼亞理工大學(xué)生物信息研究所(VirginiaBioinformaticsInstitute)的JeanPeccoud教授和MandyWilson指導(dǎo)作者搜集數(shù)據(jù)。

[1]CzarMJ,CaiY,PeccoudJ.WritingDNAwithGenoCAD[J].NucleicAcidsRes, 2009, 37(4).

[2]GolerJA,BramlettBW,PeccoudJ.GeneticDesign:RisingAbovetheSequence[J].TrendsBiotechnol, 2008, 26(6).

[3]GraslundS,NordlundP,WeigeltJ,HallbergBM,BrayJ,GileadiO,KnappS,OppermannU,ArrowsmithC,HuiR.etal.ProteinProductionandPurification[J].Nat.Methods, 2008,39(5).

[4]CaiY,WilsonML,PeccoudJ.GenoCADforiGEM:AGrammaticalApproachtotheDesignofStandard-CompliantConstructs[J].NucleicAcidsRes, 2010, 38(6).

[5]IsaacsFJ,DwyerDJ,DingC,Pervouchine,DD,CantorCR.EngineeredRiboregulatorsEnablePosttranscriptionalControlofGeneExpression[J].Nat.Biotechnol, 2004, 22(1).

[6]GardnerTS,CantorCR,CollinsJJ.ConstructionofaGeneticToggleSwitchinEscherichiaColi[J].Nature, 2000, 403(8).

[7]AdamesNR,WilsonML,FangG,LuxMW,GlickBS,PeccoudJ.GenoLIB:ADatabaseofBiologicalPartsDerivedfromaLibraryofCommonPlasmidFeatures[J].NucleicAcidsRes, 2015, 43(6).

[8]ArkinA.SettingtheStandardinSyntheticBiology[J].Nat.Biotechnol, 2008, 26(2).

[9]CantonB,LabnoA.EndyD.RefinementandStandardizationofSyntheticBiologicalPartsandDevices[J].Nat.Biotechnol, 2008, 26(2).

[10]DensmoreD,HsiauTHC,BattenC,KittlesonJT,DeLoacheW.AlgorithmsforAutomatedDNAAssembly[J].NucleicAcidsRes, 2010, 38(6).

[11]CollA,WilsonML,GrudenK,PeccoudJ.Rule-BasedDesignofPlantExpressionVectorsUsingGenoCAD[J].PLoSONE, 2015, 10(7).

[12]JelinekF.StatisticalMethodsforSpeechRecognition(Language,Speech,andCommunication)[M].Combridge:MITPress,1998.

[13]PhillipsIE,SliverPA.ANewBiobrickAssemblyStrategyDesignedforFacileProteinEngineering[EB/OL].DSpace@MIT, 2006,http://dspace.mit.edu/handle/1721.1/32535.

[14]CaiY,HartnettB,GustafssonC.PeccoudJ.ASyntacticModeltoDesignandVerifySyntheticGeneticConstructsDerivedfromStandardBiologicalParts[J].Bioinformatics, 2007, 23(1).

[15]ChenSF,GoodmanG.AnEmpiricalStudyofSmoothingTechniquesforLanguageModeling[J].ComputerSpeechandLanguage, 1999, 13(2).

[16]ViterbiAJ.APersonalHistoryoftheViterbiAlgorithm[J].IEEESignalProcessingMagazine,2006, 23(4).

[17]HuangFL,YuMS,HwangCY.AnEmpiricalStudyofGood-TuringSmoothingforLanguageModelsonDifferentSizeCorporaofChinese[J].JournalofComputerandCommunications, 2013, 22(1).

[18]KatzSM.EstimationofProbabilitiesfromSparseDatafortheLanguageModelComponentofaSpeechRecogniser[J].IEEETransactionsonAcoustics,Speech,andSignalProcessing, 1987, 35(6).

OptimizingGenoCADDesignbyUsingStatisticalLanguageModel

FANGGang1,ZHANGShe-min2

(1.SchoolofBiologicalandEnvironmentalEngineering,Xi'anUniversity,Xi'an710065,China;2.SchoolofManagement,ShaanxiSci-TechUniversity,Hanzhong723001,China)

GenoCAD(www.genocad.com)isafreeweb-basedapplicationthatguidesuserstodesignproteinexpressionvector,artificialgenenetworksandothergeneticconstructscomposedofgeneticparts.Bysuccessivelyclickingiconsrepresentingactualgeneticpartsaccordingtoagrammaticalmodel,complexgeneticconstructscomposedofdozensoffunctionalblockscanbedesigned.Butatthelaststepofdesign,usuallyeveryiconrepresentinggeneticpartshasitsoption.Withtheincreasingofgeneticpartsdatabase,moreandmorepartsareimportedintoGenoCADlibrary.Theprocessofassemblingmorethanafewsetsofgeneticpartscanbecostly,timeconsuminganderrorprone,anditissomewhatdifficulttomakedecisionwhichpartshouldbeselected.Basedonstatisticallanguagemodel,adynamicprogrammingalgorithmisdesignedtosolvetheproblemandoptimizestheresultsofGenoCADdesign.Inthisway,redundantoperationscanbereducedandthetimeandcostrequiredforconductingbiologicalexperimentcanbeminimized.

syntheticbiology;statisticallanguagemodel;dynamicprogrammingalgorithm;GenoCAD

2016-03-25；修復(fù)日期：2016-04-26

國(guó)家自然科學(xué)基金項(xiàng)目《蛋白質(zhì)介導(dǎo)的核酸自組裝體系及其計(jì)算問題研究與探索》(61173113)

方剛，男，陜西咸陽人，理學(xué)博士，副教授，研究方向：生物信息學(xué)；

F222∶TN912.3

A

1007-3116(2016)08-0020-06

(責(zé)任編輯：馬慧)

張社民，男，陜西商洛人，理學(xué)博士，教授，研究方向：圖與組合優(yōu)化。

【統(tǒng)計(jì)理論與方法】