于喆

（遼寧省海洋水產(chǎn)科學(xué)研究院，遼寧 大連 116023）

水生生物DNA序列相似度的算法

于喆

（遼寧省海洋水產(chǎn)科學(xué)研究院，遼寧 大連 116023）

本文提出DNA序列相似度指標(biāo)，建立DNA序列比對算法。首先，將水生生物DNA樣本序列與現(xiàn)有的基因庫中的DNA序列逐項(xiàng)比對；其次，在滿足特定閾值條件下，確認(rèn)樣本序列的分類。利用Java編程語言來實(shí)現(xiàn)算法，通過MonteCarlo模擬和實(shí)際應(yīng)用，驗(yàn)證算法的有效性。理論結(jié)果表明：在滿足特定閾值條件下，通過計(jì)算DNA序列相似度，能夠確定數(shù)據(jù)庫中與未知DNA樣本序列最相似的序列，判斷樣本序列的分類。模擬實(shí)驗(yàn)、對比研究和應(yīng)用結(jié)果表明：相似度指標(biāo)算法在有效判別DNA序列的分類，提高DNA序列匹配成功率，降低程序復(fù)雜度等方面具有優(yōu)良特征。

DNA序列相似度指標(biāo)；水生生物；MonteCarlo模擬

基因組攜帶了構(gòu)成生物體生命形式的全部信息，主要以DNA序列形式存在。DNA序列本質(zhì)上是一種線性多聚脫氧核糖核苷酸，由堿基、戊糖及磷酸組成，堿基又進(jìn)一步分為：腺嘌呤（A）、鳥嘌呤（G）、胞嘧啶（C）和胸腺嘧啶（T）。DNA序列所攜帶的生命體遺傳信息由堿基順序體現(xiàn)，不同生物體的DNA具有獨(dú)特的堿基順序，即所有DNA主鏈結(jié)構(gòu)相同，只是4種堿基A、G、C和T的排列順序不同。因此，觀察主鏈上堿基的排列順序就可以比較DNA序列；計(jì)算不同DNA序列之間的相似度，可以量化分析不同物種的DNA序列相似程度，推斷出物種之間的親緣關(guān)系。

隨著人類基因組計(jì)劃的發(fā)展，產(chǎn)生了海量的DNA數(shù)據(jù)信息，超出了現(xiàn)有計(jì)算機(jī)的處理水平。因此，設(shè)計(jì)合理的相似度指標(biāo)和檢驗(yàn)算法，識(shí)別和分析DNA序列，比較物種DNA序列同源性，對完善DNA序列數(shù)據(jù)庫匹配功能，實(shí)現(xiàn)大規(guī)模數(shù)據(jù)分析以及克服現(xiàn)有計(jì)算機(jī)內(nèi)存容量和計(jì)算能力的不足具有重要意義，國內(nèi)外已對此進(jìn)行了類似的研究[1,2]。

隨著分子生物學(xué)技術(shù)的發(fā)展，水生生物物種判別的研究和應(yīng)用逐漸從形態(tài)學(xué)深入到蛋白質(zhì)和DNA水平[3,4]。目前，基因序列分析是判別物種最直接的方式[3]，已經(jīng)實(shí)現(xiàn)了對一些海洋物種的成功判定[5,6]。在基因序列研究中應(yīng)用較多的是通過動(dòng)態(tài)規(guī)劃方法確定序列的相關(guān)程度，關(guān)于DNA序列相關(guān)性預(yù)測方法包括比較建模法[7-9]，主要指同源結(jié)構(gòu)預(yù)測,即面向有同源結(jié)構(gòu)的DNA比較所應(yīng)用的技術(shù)。同源結(jié)構(gòu)預(yù)測模型可以判定序列同源性大于30%的序列[8]。另一類方法是基于統(tǒng)計(jì)序列特征進(jìn)行定義，如計(jì)算兩DNA序列間的歐式距離來判定DNA序列相似性[10]，這類研究對計(jì)算復(fù)雜性要求較高，早期研究相對較少，隨著信息技術(shù)和計(jì)算機(jī)快速發(fā)展，統(tǒng)計(jì)思想越來越多地應(yīng)用于相似度研究，如基于LSH距離的時(shí)間子序列查詢算法[11]，這類算法結(jié)合了DNA序列距離的度量性質(zhì)和序列自身特征，能夠有效提高算法性能[12,13]。因此本文中，基于統(tǒng)計(jì)序列思想構(gòu)建DNA序列相似度算法，用于研究水生生物種質(zhì)基因庫DNA序列的相似性。

首先，對數(shù)據(jù)庫中的目標(biāo)序列進(jìn)行預(yù)處理，生成空間向量，并將向量數(shù)據(jù)儲(chǔ)存在數(shù)據(jù)庫中；然后，對待查DNA序列生成待查向量，通過計(jì)算相似度找出待查序列和目標(biāo)序列間所有匹配程度超過一定閾值的序列片段對，確定數(shù)據(jù)庫中與待查DNA樣本序列最相似的序列，在滿足特定閾值條件下，判斷與樣本序列最相似的DNA序列，確定樣本序列的分類；最后，通過Java語言實(shí)現(xiàn)算法，應(yīng)用于水產(chǎn)種質(zhì)基因庫信息平臺(tái)，并使用MonteCarlo模擬和算法實(shí)際應(yīng)用驗(yàn)證指標(biāo)算法的有效性。

1 序列相似度算法

DNA序列特征包括內(nèi)容和形式兩方面[14]，內(nèi)容指堿基的含量，形式指其排列方式。通過綜合考慮兩種特征表達(dá)序列成分，分析序列堿基的含量和結(jié)構(gòu)差異，主要是考察堿基關(guān)聯(lián)方式的出現(xiàn)頻率進(jìn)行比對：首先，確定連接方式的步長，構(gòu)建向量空間模型；然后，按步長對兩條DNA鏈進(jìn)行整理，以堿基關(guān)聯(lián)方式為基底生成兩個(gè)多維向量；最后，計(jì)算兩個(gè)向量余弦相似度指標(biāo)，即相似度值，確定待查序列和目標(biāo)序列間所有匹配程度超過一定閾值的序列片段對，找出數(shù)據(jù)庫中與未知DNA樣本序列最相似的序列，在滿足特定閾值條件下，能夠確定與樣本序列最相似的DNA序列，判斷樣本序列的分類。

第一步：構(gòu)建向量空間模型。在該模型中，每個(gè)對象映射為一個(gè)特征向量，首先，通過確定連接方式的步長確定空間向量的基底。記待查詢序列長度為L0，數(shù)據(jù)庫樣本數(shù)為N，樣本長度為Lt，t=1，A，N，代表序列編號(hào)，其中每一種編號(hào)對應(yīng)一種水生生物。

確定步長滿足d=d0，如在d0=2時(shí)，即統(tǒng)計(jì)A、T、G、C兩兩組合在序列中的數(shù)量。表1為A、T、G、C兩兩組合統(tǒng)計(jì)表，由A、T、G、C兩兩組合生成空間基底總數(shù)即為n=4d0。在d0=2時(shí)，對應(yīng)基底總數(shù)即為n=16，即為表1中的總列數(shù)。

表1 A、T、G、C兩兩組合Tab.1 Pairwise Combination of‘ATGC’

第二步：按步長對DNA鏈進(jìn)行整理，以堿基關(guān)聯(lián)方式為基底生成多維向量，按照每種基底的頻數(shù)生成空間向量，則查詢序列即：

v（L0）=（W1（L0），A，Wn（L0））1×n

數(shù)據(jù)庫樣本Lt對應(yīng)的空間向量為：

v（Lt）=（W1（Lt），A，Wn（Lt））1×n

第三步：計(jì)算兩個(gè)向量余弦相似度指標(biāo)，即相似度的值。

第四步：將序列按相似度大小排序，判斷數(shù)據(jù)庫中與樣本DNA序列最相似的序列＾L。

第五步：計(jì)算序列＾L與數(shù)據(jù)庫中其他N-1個(gè)序列的余弦相似度指標(biāo)，確定其中最大值記為序列＾L對應(yīng)的閾值M。

第六步：判斷樣本序列L0與＾L相似度與序列＾L對應(yīng)的閾值M大小，滿足相似度大于閾值，才能確認(rèn)樣本序列L0與＾L相似度具有統(tǒng)計(jì)意義。

從以上指標(biāo)設(shè)計(jì)的步驟中可以看出，這種方法所得到的相似度能夠在一定的步長下計(jì)算出DNA相似程度，整體波動(dòng)范圍為0～1。同時(shí)，可以進(jìn)一步修改設(shè)定不同的步長值滿足d=d0（如d0=3、4、A），對序列相似度進(jìn)行補(bǔ)充說明。但是，由于方法沒有考慮DNA實(shí)際空間結(jié)構(gòu)，更多是基于頻率，會(huì)造成整體比對相似度偏高。

2 模擬實(shí)驗(yàn)與程序?qū)崿F(xiàn)

為了滿足DNA序列查詢功能的基本要求，筆者采用MonteCarlo模擬實(shí)驗(yàn)，基于水生生物種質(zhì)基因庫資源平臺(tái)系統(tǒng)方案設(shè)計(jì)，通過對水生生物種質(zhì)基因庫資源堿基配對統(tǒng)計(jì)，按照相應(yīng)堿基或者堿基組合比例隨機(jī)生成樣本，選取數(shù)據(jù)庫中已有DNA序列進(jìn)行加工。

隨機(jī)抽取數(shù)據(jù)庫中的一條序列，用本文所提出的相似度指標(biāo)比對算法進(jìn)行查詢，計(jì)算最佳匹配序列的相似度指標(biāo)，并在序列基礎(chǔ)上隨機(jī)改變5%、20%、50%、100%（完全隨機(jī)生成新DNA序列），依次進(jìn)行對比。共進(jìn)行500次隨機(jī)抽取操作，取所計(jì)算的平均值為最終結(jié)果。為了進(jìn)一步說明本文算法的可靠性和實(shí)用性，區(qū)分步長d=2、d=3、d=4時(shí)，通過構(gòu)建不同基底進(jìn)一步計(jì)算相似度指標(biāo)，表2為不同步長的相似度實(shí)驗(yàn)結(jié)果。

從表2可以得出以下兩個(gè)結(jié)論：

表2 不同步長的相似度實(shí)驗(yàn)結(jié)果Tab.2 Similarity Test Results under Different Steps

（1）隨著步長增加，序列相似度下降，對應(yīng)閾值也有所下降。

（2）隨著待查詢樣本序列中同源性降低（隨機(jī)部分增加），序列相似度下降，閾值變化不明顯。

實(shí)驗(yàn)結(jié)果說明：判定序列相似度必須結(jié)合步長和相似度，閾值限定對非同源性樣本序列篩除具有顯著效果。參考MonteCarlo模擬實(shí)驗(yàn)結(jié)果，考慮在5%的容錯(cuò)機(jī)制下，步長d=2、3、4時(shí)，必須保證相似度在99%、96%和91%以上。

為了比較本文提出的序列對比算法的意義，與另外一類序列比對研究中常用的BLAST算法進(jìn)行對比，結(jié)合數(shù)據(jù)模擬實(shí)驗(yàn)進(jìn)行驗(yàn)證。

（一）算法分析和數(shù)據(jù)模擬實(shí)驗(yàn)表明兩類算法的時(shí)間復(fù)雜度。Blast的核心算法是對兩個(gè)滿足長度相等，且形成無空位完全匹配的DNA序列的子序列，首先找出待查序列和目標(biāo)序列間所有匹配程度超過一定閾值的序列片段對，然后根據(jù)給定的相似性延伸閾值,得到一定長度的相似性片段。Blast算法本質(zhì)上是一類動(dòng)態(tài)規(guī)劃算法，通過定義變量（包括得分矩陣和罰分矩陣），計(jì)算最優(yōu)局部比對，確定最佳對位排列，幫助人們做出最佳選擇，但是由于源序列中大量子序列需要和待比對序列索引表所有子序列進(jìn)行比較，計(jì)算步驟多，速度較慢。假設(shè)數(shù)據(jù)庫中的目標(biāo)序列和待查序列的長度為L1與L2，則序列比較的時(shí)間復(fù)雜度為O（L1L2）。在本文提出的序列比對算法中，首先，對數(shù)據(jù)庫中的目標(biāo)序列進(jìn)行預(yù)處理，確定由不同長度的基底生成相應(yīng)的特征向量。每個(gè)目標(biāo)序列，如L1確定特征向量的時(shí)間復(fù)雜度為O（L1），不占用實(shí)際DNA序列對比的時(shí)間，特征向量數(shù)據(jù)儲(chǔ)存在數(shù)據(jù)庫中；然后，對待查序列確定其待查特征向量，通過計(jì)算相似度找出待查序列和目標(biāo)序列間所有匹配程度超過一定閾值的序列片段對，時(shí)間復(fù)雜度為O（L2），有效降低了在實(shí)際比對中耗費(fèi)的時(shí)間。在數(shù)據(jù)實(shí)驗(yàn)中，隨機(jī)抽取數(shù)據(jù)庫中的一條序列，分別使用本文所提出的相似度比對算法和Blast算法進(jìn)行查詢，進(jìn)行DNA序列比對，查找序列分類，計(jì)算耗費(fèi)時(shí)間。實(shí)驗(yàn)結(jié)果顯示：Blast算法耗時(shí)42.81s，本文相似度比對算法耗時(shí)24.17s，有效控制了算法的時(shí)間復(fù)雜度。

（二）通過數(shù)據(jù)實(shí)驗(yàn)進(jìn)行小片段序列在基因組中搜尋定位。首先，隨機(jī)抽取數(shù)據(jù)庫中的一條序列，分別采用完整方式和間隔方式抽取目標(biāo)序列80%、60%和40%的片段；然后，用本文所提出的相似度比對算法和Blast算法進(jìn)行查詢，進(jìn)行DNA序列比對查找序列分類。結(jié)果顯示：若序列足夠完整,即序列包含充分的生物基因的信息,無論是采用完整方式或是間隔方式抽取局部序列，本文所提出的序列比對算法更為有效。對按照完整方式抽取目標(biāo)序列小片段（25%），Blast算法的準(zhǔn)確性有一定優(yōu)勢，本文相似度比對算法計(jì)算最佳匹配的相似度指標(biāo)和相應(yīng)的閾值，同樣可以說明目標(biāo)序列相似度的可信度，具有一定的參考價(jià)值。對不同物種同源序列的搜索，為了說明算法的有效性，尋找可信度較高的目標(biāo)序列，同樣需要保證序列包含充分的生物基因信息。

（三）通過數(shù)據(jù)實(shí)驗(yàn)對基因組大片段序列進(jìn)行共線性分析。在具體數(shù)據(jù)實(shí)驗(yàn)中，隨機(jī)抽取數(shù)據(jù)庫中的一條序列，采用完整和間隔兩種方式隨機(jī)改變5%、10%、20%的片段，計(jì)算最佳匹配的相似度指標(biāo)和相應(yīng)的閾值，結(jié)果可以得到類似的結(jié)論：若序列能夠包含充分的生物基因信息,無論是采用完整方式或是間隔方式抽取局部序列，則本文所提出的序列比對算法都更為有效，說明本文算法具有一定的參考價(jià)值。

本文用JAVA語言實(shí)現(xiàn)了此算法并作為功能模塊運(yùn)行在遼寧省水產(chǎn)種質(zhì)基因庫信息平臺(tái)上，圖1、圖2為程序運(yùn)行截圖。圖1中錄入物種的基因序列片段并選取相應(yīng)的閾值、片段類型、物種種類等參數(shù)。圖2為此基因序列片段在數(shù)據(jù)庫中的比對后，按照相似度進(jìn)行了打分并排序。平臺(tái)能夠?qū)Σ煌锓N的DNA序列進(jìn)行比較，說明相似度算法能夠計(jì)算出目標(biāo)序列相似度，具有較強(qiáng)參考價(jià)值。

圖1 向系統(tǒng)輸入序列片段Fig.1 Input Sequence Fragment to the System

圖2 輸出序列查詢的結(jié)果Fig.2 OutputThe Results of the Query Sequence

3 討論

研究發(fā)現(xiàn)，本文提出的相似度算法可能損失了DNA空間部分連接信息，導(dǎo)致結(jié)果有誤差。若研究對象只是DNA序列的小片段，由于信息量不足而導(dǎo)致相似度與實(shí)際情況差別較大，無法得到目標(biāo)序列，需要結(jié)合其他算法予以說明。但總體上，若序列足夠完整，即序列包含充分的生物基因信息，無論采用完整方式或是間隔方式抽取局部序列，本文所提出的序列比對算法都有效。本方法所得到的結(jié)果比較符合生物物種的進(jìn)化規(guī)律，對研究物種的同源性有一定價(jià)值。

水生生物的分類目前仍然主要依賴于形態(tài)學(xué)特征，然而隨著樣本序列的復(fù)雜性提高，傳統(tǒng)的比對算法對序列片段的限制條件和時(shí)間復(fù)雜度較高，已逐漸無法滿足物種鑒定需求。本文從統(tǒng)計(jì)學(xué)特征出發(fā)，通過設(shè)計(jì)DNA序列比較算法確定物種分類，在序列包含充分的生物基因信息時(shí)，序列比對算法都有效，具有較強(qiáng)的實(shí)用價(jià)值，在保護(hù)海洋生物學(xué)及生物多樣性調(diào)查等領(lǐng)域中有較好的應(yīng)用前景。目前國內(nèi)水生生物DNA序列比對算法研究還不多，數(shù)據(jù)庫平臺(tái)的DNA序列樣本不足，制約了相關(guān)研究的進(jìn)展。隨著全球氣候變化、生態(tài)環(huán)境等問題的日益嚴(yán)峻，人類對理解生物多樣性的要求日益迫切，物種的準(zhǔn)確和快速鑒定對生物多樣性資源的保護(hù)有重要意義。

［1］LiW.ArespectralanalysisusefulforDNAsequence analysis［J］.DNA in Chromatin,At the Frontiers of Biology,Biophysics,andGenomics,Arcachon,France,2002（3）：23-29.

［2］張寶華,王海水,許祿.DNA序列編碼及相似度計(jì)算［J］.高等學(xué)?；瘜W(xué)學(xué)報(bào),2006（12）:2277-2280.

［3］孫超,蘇彥平,劉洪波,等.水生生物近緣種和產(chǎn)地的分子生物學(xué)判別［J］.水產(chǎn)學(xué)雜志,2011,24（3）:53-59.

［4］姜維,王啟軍,鄧捷,等.以川陜哲羅鮭為目標(biāo)物種的水樣環(huán)境DNA分析流程的優(yōu)化［J］.應(yīng)用生態(tài)學(xué)報(bào),2016,27（7）:2363-2371.DOI:10.13287/j.1001-9332.201607.015.

［5］Steinke D,Zemlak T S and Hebert P D N.Barcoding nemo: DNA-based identifications for the ornamental fish trade［J］. Plosone,2009,4（7）:1-5.

［6］Kartavtsev Y P,Park T J,Vinnikov K A,et al.Cytochromeb（cyt-b）gene sequence analysis in six flatfish species（Teleostei,Pleuronectidae）,with phylogenetic and taxonomicinsights［J］.MarBiol,2007,152（4）:757-773.

［7］郝柏林,張淑譽(yù).生物信息學(xué)手冊［M］.上海:上海科學(xué)技術(shù)出版社,2000.

［8 Sali A and Blundell T L.Comparative protein modeling by satisfaction ofspatial restraint［J］.J MolBiol,1993,234（3）: 779-815.

［9］趙東明,強(qiáng)小利,劉向榮.一種蛋白質(zhì)結(jié)構(gòu)同源建模的DNA算法［J］.北京大學(xué)學(xué)報(bào):自然科學(xué)版,2009,45（5）:748-752.

［10］錢能,金文東.DNA序列比對分析中的統(tǒng)計(jì)特征方法［J］.浙江工業(yè)大學(xué)學(xué)報(bào),2005,33（2）:173-175.

［11］湯春蕾,董家麒.基于LSH的時(shí)間子序列查詢算法［J］.計(jì)算機(jī)學(xué)報(bào),2012,35（11）:2228-2236.

［12］戴東波,湯春蕾,邱伯仁等.一種優(yōu)化多重過濾的序列查詢算法［J］.計(jì)算機(jī)研究和發(fā)展,2010,47（10）:1785-1796.

［13］廖麗,伍紹佳.優(yōu)化多重過濾的序列查詢算法研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2014（6）:104-105.

［14］JoaoSand JoaoM.Introduction tocomputational molecular biology［M］.Brooks/Cole PublishingCompany:a Division of ThomsonLearning,1997.

Comparison Method of DNA Sequence Similarity in Aquatic Organisms

YU Zhe
（Liaoning Ocean and Fisheries Science Research Institute,Dalian 116023,China）

DNA sequence similarity index was proposed and the comparison method was constructed in this paper.Firstly,DNA sample sequence of aquatic organisms was compared with DNA sequence in the existing gene bank;secondly,sample sequence classification was determined based on the specific threshold condition.The algorithm was implemented using Java programming language,and the validity of the algorithm was verified by MonteCarlo simulation and application.Theoretical results showed that by calculating DNA sequence similarity index,the most similar DNA sequence in the gene bank of the unknown sample of DNA sequence was determined under certain threshold condition.Simulation experiments,comparison research and application results showed that Comparison Method of the similarity index was effective for classifying DNA sequence,improving matching rate of DNA sequences and reducing complexity of the program.

DNA sequence similarity index;aquatic organisms;MonteCarlo simulation

S917

A

1005-3832（2016）05-0022-05

2016-04-19

國家水產(chǎn)種質(zhì)資源平臺(tái)項(xiàng)目（2016DKA30470）；遼寧省水產(chǎn)種質(zhì)基因庫信息平臺(tái)建設(shè)（201519）.

于喆（1984-），男，碩士，工程師，從事生物信息技術(shù)研究.E-mail:chinayuzhe@126.com