黃綠娥，鄢化彪

（江西理工大學(xué)，a.應(yīng)用科學(xué)學(xué)院；b.理學(xué)院，江西贛州341000）

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

黃綠娥a，鄢化彪b

（江西理工大學(xué)，a.應(yīng)用科學(xué)學(xué)院；b.理學(xué)院，江西贛州341000）

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

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

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

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

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

令I(lǐng)＝{A、T、G、C}，長(zhǎng)度（即核苷酸符號(hào)個(gè)數(shù)，又稱堿基對(duì)（Base Pair）長(zhǎng)度，單位記為bp）為N的任意DNA序列，可表達(dá)為：

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

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

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

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

2 快速算法模型

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

DNA序列S的功譜為：

NDA序列S的總功譜為：

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

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

所以：

3 算法算例分析

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

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

圖1 BK006948.2的酵母基因一外顯子和內(nèi)含子功譜圖

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

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

從計(jì)算結(jié)果可以看出，快速算法和DFT方法計(jì)算結(jié)果完全相同，但計(jì)算效率是DFT算法的500倍，特別是當(dāng)序列長(zhǎng)度更大時(shí)，計(jì)算效率差異更明顯.

4 結(jié)束語

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

[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ù)學(xué)學(xué)報(bào)，2009，24(2):363-368.

[7]敖麗敏，羅存金．基于神經(jīng)網(wǎng)絡(luò)集成的DNA序列分類方法研究[J].計(jì)算機(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]邵建峰，嚴(yán)曉華，邵 偉，等．DNA序列信號(hào)3-周期特性[J]．南京工業(yè)大學(xué)學(xué)報(bào)，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]黃綠娥，李平康.運(yùn)動(dòng)目標(biāo)自動(dòng)跟蹤系統(tǒng)的控制平臺(tái)設(shè)計(jì)[J].江西理工大學(xué)學(xué)報(bào)，2008，29(4):10-13.

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

[13]李冬冬，王正志，杜耀華，等．DNA序列中模式發(fā)現(xiàn)的一種快速算法[J]．生物物理學(xué)報(bào)，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

江西省教育廳資助項(xiàng)目（JXJG-09-6-25）

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