李榮燦, 楊矯云, 王海鵬

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230009)

基于非線性降維的合成生物元件可視化

李榮燦, 楊矯云, 王海鵬

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230009)

合成生物學(xué)中標(biāo)準(zhǔn)化元件數(shù)量多、種類雜,使得構(gòu)建生物設(shè)備時(shí)難以選擇標(biāo)準(zhǔn)化元件,將這些元件可視化有助于提高生物設(shè)備構(gòu)建效率。考慮生物元件為長(zhǎng)度不一的基因短序列,文章通過結(jié)合編輯距離與高斯核函數(shù)構(gòu)建生物元件距離矩陣,使用拉普拉斯特征映射方法將生物元件序列降為二維或三維數(shù)據(jù)；通過圖形化展示,功能類似的生物元件可有效地聚類,功能差異大的元件可有效地區(qū)分,且對(duì)降維后數(shù)據(jù)聚類顯示的二分類精度達(dá)到91.6%,三分類精度達(dá)到82.4%。實(shí)驗(yàn)結(jié)果表明，降維后的數(shù)據(jù)具有良好的區(qū)分度,通過降維可視化將顯著提高標(biāo)準(zhǔn)化元件的選擇效率。

可視化;合成生物學(xué);非線性降維;編輯距離;聚類

當(dāng)前合成生物學(xué)的可視化多集中于設(shè)備構(gòu)造過程的可視化,如Pigeoncad[1]、TinkerCell[2]、VisBOL[3]等軟件。這些軟件通過構(gòu)建生物元件的可視化符號(hào),將生物設(shè)備的構(gòu)建過程進(jìn)行形象化展示,從而促進(jìn)生物設(shè)備的設(shè)計(jì)。當(dāng)前合成生物學(xué)的迅猛發(fā)展,標(biāo)準(zhǔn)生物元件庫已積累三萬多個(gè)標(biāo)準(zhǔn)生物元件,在構(gòu)建生物設(shè)備時(shí),如何進(jìn)行元件選擇是一件耗時(shí)費(fèi)力的工作?？紤]到合成生物標(biāo)準(zhǔn)元件種類多、數(shù)量大,若將生物元件進(jìn)行可視化展示,具有不同功能的元件可有效區(qū)分,則可降低合成生物元件選擇時(shí)的復(fù)雜程度,提高生物設(shè)備的合成效率。

生物元件為基因片段,當(dāng)前也有若干基因可視化方法,如Cytoscape[4]、ParaView[5]等,這些方法多是對(duì)單個(gè)基因組可視化,從而形象化展示基因內(nèi)部結(jié)構(gòu)。而本文期望能夠?qū)ι镌M(jìn)行可視化聚類,這對(duì)當(dāng)前的方法提出了挑戰(zhàn)。

對(duì)生物元件可視化聚類的一個(gè)思路是數(shù)據(jù)降維。當(dāng)前數(shù)據(jù)降維主要分為線性降維與非線性降維。線性降維以主成分分析(principal component analysis,PCA)為主要代表[6],通過將原始數(shù)據(jù)進(jìn)行線性變換,消除屬性相關(guān)項(xiàng);非線性變換以局部線性嵌入(locally linear embedding,LLE)[7]、拉普拉斯特征映射(Laplacian eigenmaps,LE)[8]為主要代表,通過維持原始數(shù)據(jù)的流行結(jié)構(gòu),使得降維后的數(shù)據(jù)與原始數(shù)據(jù)維持結(jié)構(gòu)一致。鑒于標(biāo)準(zhǔn)生物元件為長(zhǎng)度不一的文本序列,難以直接對(duì)其進(jìn)行線性變換,同時(shí)非線性變換中的局部關(guān)系構(gòu)建也不適用于序列文本數(shù)據(jù),因此需要構(gòu)建一種針對(duì)長(zhǎng)度不一的基因文本序列進(jìn)行降維可視化的方法。

本文通過改進(jìn)拉普拉斯特征映射來進(jìn)行合成生物標(biāo)準(zhǔn)元件可視化。首先采用編輯距離構(gòu)建生物元件的距離矩陣,并利用高斯核函數(shù)進(jìn)行距離映射,然后借助映射后的距離矩陣構(gòu)建拉普拉斯矩陣,最后進(jìn)行特征分解完成數(shù)據(jù)降維并可視化。通過在合成生物標(biāo)準(zhǔn)元件庫上的應(yīng)用,實(shí)驗(yàn)結(jié)果表明，本文提出的可視化方法可有效區(qū)分具有功能差異的生物元件,通過聚類發(fā)現(xiàn),2類元件和3類元件的聚類精度分別達(dá)到91.6%和82.4%。這不僅為合成生物學(xué)家提供了一種利用可視化快速選擇元件的方法,也提供了一種有效分類生物元件序列的方法。

1 算法流程介紹

標(biāo)準(zhǔn)生物元件為長(zhǎng)度不一致的基因片段序列,傳統(tǒng)基于歐氏距離的方法難以有效衡量生物元件的相似性,因此本文算法主要采用編輯距離進(jìn)行生物元件相似性度量。通過結(jié)合編輯距離與拉普拉斯特征映射,對(duì)生物元件序列降維,達(dá)到序列數(shù)據(jù)可視化的目的。該主要過程步驟如下:

(1) 相似度計(jì)算。使用編輯距離作為衡量數(shù)據(jù)間距離的標(biāo)準(zhǔn),并進(jìn)行歸一化處理,以構(gòu)建表征數(shù)據(jù)集的加權(quán)無向圖矩陣。

(2) 非線性降維。構(gòu)建拉普拉斯矩陣,進(jìn)行矩陣分解,得到降維后的數(shù)據(jù)。

(3) 可視化。將降維后的數(shù)據(jù)以圖形化方式進(jìn)行展示。

1.1 距離矩陣構(gòu)建

編輯距離,又稱Levenshtein距離,是指2個(gè)字串之間由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)[9]。通常,編輯距離越小,2個(gè)字符串的相似度越高。例如計(jì)算TAGAA→TGACA的編輯距離為2,TAGAA到TGACA編輯操作轉(zhuǎn)換過程如圖2所示。

圖1 TAGAA到TGACA編輯操作轉(zhuǎn)換過程

當(dāng)前編輯距離的計(jì)算主要是基于動(dòng)態(tài)規(guī)劃算法[10]。給定2條長(zhǎng)為m、n的序列x、y,動(dòng)態(tài)規(guī)劃算法構(gòu)建大小為m×n的矩陣E其中的每個(gè)值Ei,j表示子序列x1x2…xi和y1y2…yj中xi與yj的最小編輯距離。Ei,j的計(jì)算公式為:

其中,δ(xi,-)、δ(-,yj)分別為插入、刪除的得分。若xi=yj,則δ(xi,yj)表示匹配得分;若xi≠yj,則δ(xi,yj)表示錯(cuò)配得分。

DNA序列TAGAA和TGACA的動(dòng)態(tài)規(guī)劃矩陣見表1所列。以(3,3)格計(jì)算為例，取如下3個(gè)值的最小值填入單元格。

(1) 若最上方的字符等于最左方的字符,則取左上方的數(shù)字;否則取左上方的數(shù)字加1(對(duì)于(3,3)格來說為3)。

(2) 左方數(shù)字加1(對(duì)于(3,3)格來說為2)。

(3) 上方數(shù)字加1(對(duì)于(3,3)格來說為2)。

矩陣右下角的值即為2條序列的編輯距離。

表1 TGACA和TAGAA的動(dòng)態(tài)規(guī)劃矩陣

編輯距離與2條序列的長(zhǎng)度相關(guān),其長(zhǎng)度為:

因?yàn)榻稻S可視化是要得到不同序列間的相似程度,所以計(jì)算出編輯距離值后應(yīng)對(duì)其進(jìn)行歸一化處理,即用ED(x,y)值除以2個(gè)序列中較長(zhǎng)序列的長(zhǎng)度(maxLength(|x|,|y|)值)。編輯距離與2條序列的長(zhǎng)度相關(guān),長(zhǎng)為m、n的序列間的編輯距離最大為max(m,n),即最長(zhǎng)序列的長(zhǎng)度。

得到歸一化距離后,為使距離矩陣具有更好的局部性,本文對(duì)計(jì)算得到的編輯距離使用徑向基函數(shù)核做高斯化處理,定義為:

1.2 拉普拉斯特征映射

拉普拉斯特征映射是非線性降維的主要方法,其主要思想是保證2個(gè)很相似的數(shù)據(jù)在降維的子空間里盡可能接近。假設(shè)數(shù)據(jù)實(shí)例xi、xj降維后數(shù)據(jù)實(shí)例為yi、yj,則拉普拉斯特征映射的目標(biāo)函數(shù)為:

其中,Wi,j為實(shí)例xi、xj相似度。傳統(tǒng)拉普拉斯特征映射采用歐氏距離等計(jì)算相似度,本文通過(2)式計(jì)算得到實(shí)例間的距離矩陣,從而更好地刻畫不同基因序列間的相似度。

(4)式中目標(biāo)函數(shù)的求解可轉(zhuǎn)化為最小化目標(biāo)函數(shù)yTLy,再通過矩陣分解進(jìn)行計(jì)算。因此拉普拉斯特征映射的主要步驟為:

(1) 采用特定的距離衡量方法,得到所有點(diǎn)間的相似度值,并構(gòu)建一個(gè)相似度矩陣W,本文使用編輯距離來確定,即

Wi,j=K(xi,yj)

(5)

(2) 借助W和度矩陣D(D是由di構(gòu)成的對(duì)角矩陣)計(jì)算拉普拉斯矩陣L,并計(jì)算其特征值與特征向量,即

L=D-W

(7)

Ly=λDy

(8)

(3) 取最小的k個(gè)非零特征值對(duì)應(yīng)的特征向量作為L(zhǎng)E算法的結(jié)果輸出,得到降維后的數(shù)據(jù)結(jié)果。

1.3 算法流程

本文算法的詳細(xì)流程為:

(1) 計(jì)算任意2條序列x、y間的編輯距離ED(x,y),并依據(jù)(2)式進(jìn)行標(biāo)準(zhǔn)化處理。

(2) 利用步驟(1)的距離計(jì)算結(jié)果構(gòu)造距離相似度矩陣W。

(3) 對(duì)步驟(2)的矩陣W進(jìn)行高斯化處理,其中參數(shù)σ需要不斷調(diào)整以實(shí)現(xiàn)好的聚類效果。

(4) 計(jì)算度矩陣D。具體公式如下：

(5) 將度矩陣D和鄰接矩陣W相減得到拉普拉斯矩陣L。

L=D-W

(12)

(6) 再通過對(duì)相似矩陣進(jìn)行特征分解得到特征向量。

Ly=λDy

(13)

(7) 取最小的k個(gè)非零特征值對(duì)應(yīng)的特征向量作為L(zhǎng)E算法的結(jié)果輸出,得到降維后的數(shù)據(jù)結(jié)果,并進(jìn)行可視化展示。

2 實(shí)驗(yàn)結(jié)果

本文從合成生物學(xué)標(biāo)準(zhǔn)元件數(shù)據(jù)庫中選取了3類生物元件,即復(fù)合部件(composite)、核糖體綁定位點(diǎn)(ribosome binding site,RBS)、引物(primer)來檢驗(yàn)算法分類效果。其中復(fù)合部件數(shù)目為200,核糖體綁定位點(diǎn)數(shù)目為300,引物數(shù)目為300。實(shí)驗(yàn)中的參數(shù)σ取值為0.3。

2類組件的可視化結(jié)果如圖2所示。圖2a表示復(fù)合部件與引物的可視化結(jié)果,其中深色代表復(fù)合部件,淺色代表引物;圖2b表示復(fù)合部件與核糖體綁定位點(diǎn)的可視化結(jié)果,其中深色代表核糖體綁定位點(diǎn),淺色代表復(fù)合部件。圖2中不同顏色和符號(hào)代表不同類型的元件,可以看出,同一類型的元件會(huì)聚集在一起,不同類型間的元件會(huì)有較大差距。這說明本文的可視化方法可以很好地區(qū)分不同的元件,使得用戶可依據(jù)功能差異進(jìn)行元件選擇。

3類元件的三維可視化結(jié)果如圖3所示。由圖3可以看出,淺色代表的復(fù)合部件與其他2類元件具有顯著差異性,而深色(左側(cè)下方)代表的核糖體綁定位點(diǎn)與深色(左側(cè)上方)代表的引物之間差別相對(duì)較小,但也可明顯看出兩者之間具有明顯聚類。產(chǎn)生這種現(xiàn)象的原因是復(fù)合部件是由不同元件構(gòu)成的復(fù)合體,功能復(fù)雜,而核糖體綁定位點(diǎn)與引物相對(duì)簡(jiǎn)單,差異性較小。這也反映了本文基于編輯距離的可視化很好地區(qū)分出了不同元件的功能。

圖2 2類組件的可視化結(jié)果

圖3 復(fù)合部件、核糖體綁定位點(diǎn)和引物的可視化結(jié)果

使用k-means算法對(duì)3類降維可視化的數(shù)據(jù)進(jìn)行聚類,結(jié)果如下:對(duì)于2種合成元件的組合,復(fù)合部件與引物、復(fù)合部件與核糖體綁定位點(diǎn)的分類準(zhǔn)確率分別為99.2%、91.6%;對(duì)于3種合成元件的組合,復(fù)合部件、引物與核糖體綁定位點(diǎn)的分類準(zhǔn)確率為82.4%。可見降維后的數(shù)據(jù)具有較好的區(qū)分度。這里的準(zhǔn)確率是指聚類后與元件的原類型相比正確分類的比率。

3 結(jié) 論

本文針對(duì)多類型的大規(guī)模合成生物元件數(shù)據(jù)集進(jìn)行降維可視化,通過將編輯距離與高斯核函數(shù)相結(jié)合,建立不同元件間的相似度關(guān)系矩陣,然后基于此相似度關(guān)系進(jìn)行拉普拉斯特征映射,達(dá)到元件降維目的。通過觀察降維后的數(shù)據(jù)可視化結(jié)果,表明不同類型的元件可構(gòu)成不同聚類,功能差異性在圖中表現(xiàn)出了距離差異性，從而說明合成生物學(xué)者依據(jù)可視化的結(jié)果幫助進(jìn)行元件選擇的可能性。

[1] BHATIA S,DENSMORE D.Pigeon:a design visualizer for synthetic biology[J].ACS Synthetic Biology,2013,2(6):348-350.

[2] CHANDRAN D,BERGMANN F T,SAURO H M.TinkerCell:modular CAD tool for synthetic biology[J].Journal of Biological Engineering,2009,3(1):1-17.

[3] MCLAUGHLIN J A,POCOCK M,MISIR G,et al.VisBOL:web-based tools for synthetic biology design visualization[J].ACS Synthetic Biology,2016,5(8):874.

[4] SHANNON P,MARKIEL A,OZIER O,et al.Cytoscape:a software environment for integrated models of biomolecular interaction networks[J].Genome Research,2003,13(11):2498-2504.

[5] HENDERSON A,AHRENS J,LAW C,et al.The paraview guide[M].New York:Kitware,2004.

[6] KARL PEARSON F R S.LIII.On lines and planes of closest fit to systems of points in space[J].Philosophical Magazine Series 6,2010,2(11):559-572.

[7] ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[8] BELKIN M,NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering[J].Advances in Neural Information Processing Systems,2001(14):585-591.

[9] LI Y J,LIU B.A normalized levenshtein distance metric [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2007,29(6):1091-1095.

[10] JONES N C,PEVZNER P A.An introduction to bioinformatics algorithms [M]//An introduction to bioinformatics algorithms.Massachusetts:MIT Press,2004:626-626.

Visualizationofstandardsyntheticbiologicalpartsbasedonnonlineardimensionalityreduction

LI Rongcan, YANG Jiaoyun, WANG Haipeng

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In synthetic biology, there are a number of standard parts with a wide variety of categories, making it hard to choose a part when constructing devices. Visualizing these parts could simplify the part selection. Considering that synthetic biological parts are DNA segments with various lengths, the similarity of these parts is evaluated by the integration of edit distance and Gaussian kernel. Based on the similarity, Laplacian Eigenmaps is employed to reduce data dimensions to two or three dimensions. By visualizing the reduced data, the parts with similar functionality could cluster together, and the parts with different functionality could be separated efficiently. Besides, the cluster accuracy for two kinds and three kinds of parts reaches 91.6% and 82.4%, respectively, which proves the discrimination of the reduced data, and this could significantly improve the efficiency of parts selection.

visualization; synthetic biology; nonlinear dimensionality reduction; edit distance; clustering

2016-04-05；

2016-05-16

國家自然科學(xué)基金資助項(xiàng)目(61502135);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(JZ2015HGBZ0111)和國家高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃資助項(xiàng)目(B14025)

李榮燦(1990-),男,福建泉州人,合肥工業(yè)大學(xué)碩士生;

楊矯云(1987-),男,山東招遠(yuǎn)人,博士,合肥工業(yè)大學(xué)副教授,通訊作者，E-mail:jiaoyun@hfut.edu.edu.cn.

10.3969/j.issn.1003-5060.2017.12.006

TP317.4

A

1003-5060(2017)12-1610-04

(責(zé)任編輯胡亞敏)