黃綠娥，鄢化彪

（江西理工大學，a.應用科學學院；b.理學院，江西贛州341000）

一種基于Voss映射下計算DNA序列3-周期特性的快速算法

黃綠娥a，鄢化彪b

（江西理工大學，a.應用科學學院；b.理學院，江西贛州341000）

DNA序列信號頻譜3-周期特性被認為是用來區(qū)分編碼區(qū)和非編碼區(qū)的一個重要特征，傳統(tǒng)的DNA序列分析中頻譜計算量大占用了大量計算時間，使得分析效率極低.為提高DNA序列分析效率，針對傳統(tǒng)頻譜計算量大的問題，從3-周期特性原理出發(fā)，推導出了一種基于Voss映射下快速計算DNA序列3-周期頻譜的方法.該方法有效避開計算離散傅立葉變換（DFT），從序列本身直接得到信噪比.實驗結果表明快速算法計算效率是DFT方法的百倍之上，極大減小基因的信噪比計算時間，提高DNA序列識別中信噪比的計算效率.

DNA序列；Voss映射；外顯子；3-周期性；信噪比

生物信息學（Bioinformatics）是生命科學、計算機科學、信息科學和數(shù)學等學科交匯融合形成的一門交叉學科.它以計算機、網(wǎng)絡為工具，用數(shù)學和信息科學的理論、方法和技術去研究生物大分子，發(fā)現(xiàn)生物分子信息組織的規(guī)律.DNA序列數(shù)據(jù)是生物信息學中的主要研究對象之一，通過分析DNA序列的結構特征，不僅可以明晰已有序列，而且有利于發(fā)現(xiàn)新序列并預測其功能，而分析DNA序列的結構最基本的方法就是DNA序列分類[1-5]. 2000年全國大學生數(shù)學建模競賽就將其列為競賽題目，2012年全國研究生數(shù)學建模競賽又將其列為賽題之一，充分說明了分類的難度.近年來，許多生物學家、數(shù)學家在這方面也做了大量的研究，分類方法也各異，例如哈爾濱工業(yè)大學張德豐等采用傳統(tǒng)數(shù)理統(tǒng)計方法，沈陽大學岳曉寧等采用數(shù)據(jù)挖掘方法[6]，東北電力大學敖麗敏等采用神經(jīng)網(wǎng)絡方法[7]，等等.這些方法對于基因序列較短的問題效果明顯，對于比較長的序列都面臨計算量大、識別效率低的困境.為解決基因計算量大的問題，南京工業(yè)大學邵建峰教授所帶領的團隊采用DNA序列的3-周期特性分析方法[8-10]，大大降低計算量.本文從DNA序列3-周期特性的原理出發(fā)，從數(shù)學角度推導一種能有效避開計算離散傅立葉變換（DFT）的快速計算方法，以提高DNA識別效率[11-13].

1 映射下DNA序列3-周期特性模型

在DNA序列研究中，首先需要把A、T、G、C四種核苷酸的符號序列，根據(jù)一定的規(guī)則映射成相應的數(shù)值序列，以便于對其作數(shù)字處理[1].

令I＝{A、T、G、C}，長度（即核苷酸符號個數(shù)，又稱堿基對（Base Pair）長度，單位記為bp）為N的任意DNA序列，可表達為：

即A、T、G、C的符號序列S：S（0），S（1）,…，S（N－1）.

對于任意確定的b∈I，令：對序列ub（n）分別做離散Fourier變換(DFT)有：

計算每個復數(shù)序列Ub（k）的平方功譜，并相加得到整個序列S的功譜序列：

由DNA序列外顯因子的3-周期性[8-9]，將序列1/3處的功譜值與整個序列的平均功譜做比較，其比率定義為該序列的“信噪比”（Signal Noise Ratio，SNR），即：

2 快速算法模型

根據(jù)功率譜定義可得，Ub（k）的平方功譜可以轉化為：

DNA序列S的功譜為：

NDA序列S的總功譜為：

所以NDA序列S的總功譜為E=N2.

設xb、yb、zb分別為核苷酸b在序列的0，3，6，…和1，4，7，…以及2，5，8，…位置上出現(xiàn)的頻數(shù).的模平方可表示為：

所以：

3 算法算例分析

選用編號為BK006948.2的酵母基因DNA序列[10]的一段外顯子（區(qū)間為[81787，82920]，長度1134 bp）和一段內含子（區(qū)間為[96361，97551]，長度1191 bp）的指示序列為例.

用傳統(tǒng)DFT變換，并繪制功譜圖如圖1所示.

圖1 BK006948.2的酵母基因一外顯子和內含子功譜圖

用DFT方法和快速算法對上述DNA序列片段進行分析，得到其效果比較如表1所示.

表1 傳統(tǒng)DFT方法和快速算法的效果比較

從計算結果可以看出，快速算法和DFT方法計算結果完全相同，但計算效率是DFT算法的500倍，特別是當序列長度更大時，計算效率差異更明顯.

4 結束語

本文建立了Voss映射下信噪比模型，從原理出發(fā)推導出了一種能直接計算信噪比的方法，避免計算離散傅立葉變換帶來的計算復雜度.并通過實例與傳統(tǒng)DFT方法進行比較，實驗結果表明，快速算法完全保證了DFT方法的結果，但計算效率提高了上百倍，而且，當序列越長，計算效率比值越大.充分說明該方法適用于Voss映射下的長序列計算辨識問題.

[1]Sharma S D,Shakya K,Sharma S N.Evaluation of DNA mapping schemes for exon detection[C]//Computer,Communication and Electrical Technology (ICCCET),2011 International Conference on.IEEE,2011:71-74.

[2]Burge C,Karlin S.Prediction of complete gene structures in human genomic DNA[J].Journal of molecular biology,1997,268 (1):78-94.

[3]Berryman M J,Allison A,Wilkinson C R,et al.Review of signal processing in genetics[J].Fluctuation and Noise Letters,2005,5 (4):13-35.

[4]Anastassiou D.Frequency-domain analysisofbiomolecular sequences[J].Bioinformatics,2000,16(12):1073-1081.

[5]Kotlar D,Lavner Y.Gene prediction by spectral rotation measure: a new method for identifying protein-coding regions[J].Genome research,2003,13(8):1930-1937.

[6]岳曉寧，井元偉．基于DNA序列數(shù)據(jù)挖掘算法研究[J]．生物數(shù)學學報，2009，24(2):363-368.

[7]敖麗敏，羅存金．基于神經(jīng)網(wǎng)絡集成的DNA序列分類方法研究[J].計算機仿真，2012，29(6):171-175.

[8]Yin C,Yau S S T.Prediction of protein coding regions by the 3-base periodicity analysis of a DNA sequence [J].Journal of theoretical biology,2007,247(4):687-694.

[9]邵建峰，嚴曉華，邵 偉，等．DNA序列信號3-周期特性[J]．南京工業(yè)大學學報，2012,34(4):133-137.

[10]Goffeau A.TPA_inf:Saccharomyces cerevisiae S288c chromosome XV,complete sequence[EB/OL].[2012-09-18].http://www.ncbi. nlm.nih.gov/nuccore/329138966?report=fasta.x.

[11]黃綠娥，李平康.運動目標自動跟蹤系統(tǒng)的控制平臺設計[J].江西理工大學學報，2008，29(4):10-13.

[12]余水靜，彭艷平，鄧揚悟．一株嗜酸氧化亞鐵硫桿菌分離及生長特性研究[J]．江西理工大學學報，2011，32(5):1-4.

[13]李冬冬，王正志，杜耀華，等．DNA序列中模式發(fā)現(xiàn)的一種快速算法[J]．生物物理學報，2005，21(2):121-129.

A fast algorithm to calculate the 3-periodicity characteristic in DNA sequence based on Voss mapped

HUANG Lv-ea,YAN Hua-biaob(a.Faculty of Applied Science;b.Faculty of Science,Jiangxi University of Science and Technology,Ganzhou 341000,China)

The 3-periodicity obtained by direct Fourier transform (FDT)was acknowledged as an important feature for distinguishing gene coding regions of a DNA sequence.Aim at the quantity work to calculate the value of DNA sequence by direct Fourier transform in calculate SNR,this paper given an expeditious algorithm based on Voss mapped DNA sequence.This method used DNA sequence's character,direct to calculate SNR without FDT,which acquiring the noise-signal ratio from the sequence.The experimental results show that the expeditious algorithm's computing efficiency is 100 times of DFT,which greatly reduced the gene SNR calculation time.

DNA sequence;Voss mapped;exon;3-periodicity;SNR

Q812；O242

A

2095-3041（2014）00-0098-04

10.13265/j.cnki.jxlgdxxb.2014.01.017

2013-06-21

江西省教育廳資助項目（JXJG-09-6-25）

黃綠娥（1981- ），女，碩士，講師，主要從事系統(tǒng)控制與建模方法等方面的研究，E-mail：42673284@qq.com．