方　剛，張社民

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

?

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

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

一、引 言

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

二、材料方法

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

(一)語法模型

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

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

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

表1　詳細(xì)語法表

圖1　在設(shè)計軟件GenoCAD最后一步的多個選項

在這一模型中，一個句子(sentence，S)是否有意義并且合理基于其出現(xiàn)的概率。一個句子由一系列的詞組成，在本文中一個“句子”S就是一個由基礎(chǔ)“零件”構(gòu)成的生物學(xué)組件，這些基礎(chǔ)“零件”就是組成“句子”的詞，一個基礎(chǔ)“零件”part就是一個詞。因此，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) 指一個基礎(chǔ)“零件”在一個設(shè)計中出現(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) 容易計算，但是計算P(part3︱part1,part2)的難度較大，而計算P(partn︱part1,part2,…,partn-1) 將非常困難，因為牽扯的變量太多導(dǎo)致條件過于復(fù)雜而難以估算?；隈R爾科夫假設(shè)，可以認(rèn)為一個“零件”在一個設(shè)計中出現(xiàn)的概率僅僅與它相鄰的前一個“零件”相關(guān)。因此式(2)可以簡化為：

P=(S)

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

(3)

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

(4)

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

(5)

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

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

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

PATH

(6)

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

(7)

(8)

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

(三)算法

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

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

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

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

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

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

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

P=address_of_B

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

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

P=address_where_V_comes_from

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

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

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

三、結(jié) 果

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

當(dāng)確定了我們要表達(dá)的基因，該裝配算法由一個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)在第一列排除啟動子R0040，算法給出序列R0011-B0030-J45008-B0030-J45009-R0040-B0030-J45014-B0010-B0012。

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

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

四、討 論

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

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

感謝美國弗吉尼亞理工大學(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

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

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

F222∶TN912.3

A

1007-3116(2016)08-0020-06

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

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

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