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

于喆

（遼寧省海洋水產科學研究院，遼寧 大連 116023）

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

于喆

（遼寧省海洋水產科學研究院，遼寧 大連 116023）

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

DNA序列相似度指標；水生生物；MonteCarlo模擬

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

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

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

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

1 序列相似度算法

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

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

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

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

第二步：按步長對DNA鏈進行整理，以堿基關聯方式為基底生成多維向量，按照每種基底的頻數生成空間向量，則查詢序列即：

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

數據庫樣本Lt對應的空間向量為：

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

第三步：計算兩個向量余弦相似度指標，即相似度的值。

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

第五步：計算序列＾L與數據庫中其他N-1個序列的余弦相似度指標，確定其中最大值記為序列＾L對應的閾值M。

第六步：判斷樣本序列L0與＾L相似度與序列＾L對應的閾值M大小，滿足相似度大于閾值，才能確認樣本序列L0與＾L相似度具有統計意義。

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

2 模擬實驗與程序實現

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

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

從表2可以得出以下兩個結論：

表2 不同步長的相似度實驗結果Tab.2 Similarity Test Results under Different Steps

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

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

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

為了比較本文提出的序列對比算法的意義，與另外一類序列比對研究中常用的BLAST算法進行對比，結合數據模擬實驗進行驗證。

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

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

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

本文用JAVA語言實現了此算法并作為功能模塊運行在遼寧省水產種質基因庫信息平臺上，圖1、圖2為程序運行截圖。圖1中錄入物種的基因序列片段并選取相應的閾值、片段類型、物種種類等參數。圖2為此基因序列片段在數據庫中的比對后，按照相似度進行了打分并排序。平臺能夠對不同物種的DNA序列進行比較，說明相似度算法能夠計算出目標序列相似度，具有較強參考價值。

圖1 向系統輸入序列片段Fig.1 Input Sequence Fragment to the System

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

3 討論

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

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

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

［2］張寶華,王海水,許祿.DNA序列編碼及相似度計算［J］.高等學校化學學報,2006（12）:2277-2280.

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

［4］姜維,王啟軍,鄧捷,等.以川陜哲羅鮭為目標物種的水樣環境DNA分析流程的優化［J］.應用生態學報,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］郝柏林,張淑譽.生物信息學手冊［M］.上海:上海科學技術出版社,2000.

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

［9］趙東明,強小利,劉向榮.一種蛋白質結構同源建模的DNA算法［J］.北京大學學報:自然科學版,2009,45（5）:748-752.

［10］錢能,金文東.DNA序列比對分析中的統計特征方法［J］.浙江工業大學學報,2005,33（2）:173-175.

［11］湯春蕾,董家麒.基于LSH的時間子序列查詢算法［J］.計算機學報,2012,35（11）:2228-2236.

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

［13］廖麗,伍紹佳.優化多重過濾的序列查詢算法研究［J］.網絡安全技術與應用,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

國家水產種質資源平臺項目（2016DKA30470）；遼寧省水產種質基因庫信息平臺建設（201519）.

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