（由填寫題 基于譜分析的DNA序列識別算法研摘型的功率譜快速算法和基于帕斯瓦爾定理的信噪比快速算法，該算法與DFT及Z-curveVoss映射的線性變換和降維，Z-curve映射A0C1G2,T3，并給出了功率譜和信噪比的快速計表14N2Nlog24N23Nlog2N 表 固定閾值與自適應閾值的預測正確點定位的準確性。對27號上一段起始端點在802位的外顯子進行7948個未注釋的進行了預測（編碼區位置見正文27頁部，在鞍部中心附近嘗試插入/刪除堿基，通過觀察鞍部是否來判斷是否存目 Z-curve映射與Voss映射的關 總 附 基于譜分析的DNA序列識別算A，G，啶（C），胸腺嘧啶（T）這四種核苷酸（堿基）符號按一定的順序連接而成?；鶢畋憩F。預測，一般是指識別出DNA序列中編碼區（即外顯子。隨著人類組計劃的實施和順利完成，預測成為生物信息學中最基長為N的DNA序列在利用傅里葉變換對數值化映射后的序列進行頻譜對不同物種類型的閾值確1A序列的數值映射及譜分研究現示法兩大類。表2-1列舉了部分數值映射方法。數值表示法是將序列中的映射方法堿ACGT0123-1-術包括：神經網絡、馬爾科夫模型，支持向量機，動態規劃等[8]。在目前對生物信息領域的研究熱潮下，各種DNA序列的數值映射和預符號說明與假設 符號約定與含IS長度為NDNAubUbkERxb,yb,bI0,3,...N-31,4,…N-Voss映射與快速譜分析因此在序列的研究中被廣泛地使用。它的基本思想是將DNA序列按照四種I{A,T,G,C}，長度（即堿基符號的個數，單位記為bp）為NS{Sn|SnI,n0,1,2,N現對于任意確定的bIun

Snb

n0,1,2,N Sn用譜分析的方法查找DNA序列中的外顯子。對于長度為N的序列，其傅立葉變換NUbkub

j2N 計算每個復序列{Ubk}DNA序列S的功率譜序列{Pk}： PkUk2Uk2Uk2Uk2

k0,1,N NEPkk

(2-Ratio，SNRRPNE

(2-外顯子序列的功率譜曲線在頻率kN信噪比R大于某個適當選定的閾值R0（比如R02）的DN段，可作為DNA仍然很大，會影響到所設計的識別算法的效率。根據DFT(2-1)，求出N點Ub(k)需要N2次復數乘法NN1次復數加法。眾所周知，實現一次復數乘2在長為N的DNA序列中，若N為3的倍數，將堿基符號bI{A,T,G,C出現在該序列的0,3,6,...N－3與1,4,7,…N－2以及2,5,8,…N－1等位置上的頻數分別記xb,ybzb，則kN3處的總功率譜值即為：2 N

22nN2n

N j2P()Ub(

ub(n)

ub(n) j

j2

b b b

xy 3ze

x

xzyz DNA序列在kN3處的功率譜可以通過計算堿基出現的頻次而獲得。線性代數中，設F是一個數域，F上n元二次齊次多q(x,x,,x)ax2ax2a 11 22 nn2a12x1x22a13x1x32an1,n,x1x2q(x,x,,x)(x,x,,x)A

x

n P(3)xb,yb,zb 0.5yb

1z Bxb,ybzb b 為N

|

n|21N1bNkb

k

(2-NE|

n|2 bI

RbI kN3處的功率譜值的計算量。由該表可看出，隨著N表2-3計算頻數二次型4N2Nlog24N23Nlog2NN根據本文功率譜和信噪比對人類線粒體NC_012920_1進行分析，求解信噪比的結果。與題目給出的曲線相比可以看出，該快速算法與FFT算法求10 k Voss映射下頻次二次型法求解功率譜（人類線粒體76543210 n Voss映射下帕斯瓦爾定理求解信噪比（人類線粒體Z-curve和Voss映射下的譜分析Z-curve

1994年，張春霆提出了序列的Z-curve定義[9]。設DNA序列S

xn2(AnGn) y 2( zn2(AnTn)接著，若x10y10z10,以及xnxnxnynynyn1和znznzn，于是得Z-curvex 1uAn

uyn 1 zn 1uG un Z-curveZPkXk2Yk2Zk Z其中Xk，Yk和Zk分別表示數字序列xnyn和zn的離散傅PN

NY2

2

2Z3R

3

E

(2-Nk

NZ-curve從(2-12)可以看出，對于xn，AG被表示1CG被表示為-1；同樣yn中，A和C被表1，而GT被表示為-1；zn中，AT1CG被表示為-1。從某中程度上來說，這AGCG均為嘧啶，ACGT為酮類，ATCG之間存四種堿基的數目符合AnTnGnCnn，對特定的n，、、、中只有三個是獨立的，Z-curve就是將三個獨立的數用三坐標系中的一點Pn唯一表示出來了。對于長為N的DNA序列，當n從1到N增加時，三 關系的點P1,P2,...,PN的連線就構成了Z曲線。因此，Z-curve映射本質上是DNA序列的幾何表達形式。Voss映射是映射，而Z-curve映射是三維映射可以說Z-curve映射是對Voss映射所得到的序列進行線性變換得到的，下面定量分析Z-curve映射與Voss映射下功率譜和信噪比的關系。在Z-curve映射下，總功率譜值為xn,yn,zn三個序列功率譜值之求解功率譜的。由(2-12)不難xn只能取到兩個值：-11n0,1N1。這是由Voss映射中uAn,uCn,uGn,uTn在處n只有一個1，其余三個都0的緣DNA序列的第n位，xn1就表示該位上AG的現，而xn1則表示該位上堿CT的出現。xn序列1的總個數表xn序列在kN3XNXN2

N1x(n)ej2nPZ 3N/

3

x(3m)x(3m1)ej3x(3m2)ej3

(2- m0 3xyej3

zej

x2y2z2xyxzy3 b b b3其中xbxAxGxCxTybyAyGyCyTzbzAzGzCzTZPYN3和PZN3同理可得。 (2-15)可發現，PXN3、PYNZ ZZZ-curve映射和堿基出現的頻次聯系起來了。那么，在k P PN P PZ3 Z3 Z3 Z3

3Z-curve(2-4(x2y2z2xyxzyz) b b b (2-16)表明：在k

長度NDNA序列xnynzn序列僅有-11兩個值，因此根據帕斯瓦爾定理xn,yn,zn三個序列的功率平均值是其序列長度N。在Z-curve映射下，總功率譜的平均值如(2-17)所示。EZExEyEz (2-17)表明：在k

根據(2-16)和(2-17)，Z-curve映射下的信噪比為R bI (2-18)表明：在k

2-32-4給出了Z-curve映射下快速算法求解功率譜和信噪比的結果，與題目給出的曲線十分吻合，表明了Z-curve映射下快速算法的正確性。圖2-3Z-curve映射下頻次二次型法求解k

9876543210 n圖2-4Z-curve映射下帕斯瓦爾定理求解信噪比（人類線粒體

結論在kN3處，Z-curveVoss4實數映射下的通用快速譜算法 NDNA序列映射為一維序列unN3的倍數un序列2kN32N

N

N

j2nP U

u(n) 3N/

u(3m)u(3m1)ej3u(3m2)ej3 m0 j

2j

(2-xC2xG3xTyC2yG3yT

3zC2zG3zTe其中X(xC2xG3xTyC2yG3yTzC2zG3zTR=PN3 N |un

(2-xCyCzC4xGyGzG9xTyTzT體NC_012920_1信噪比分析的結果見圖2-5，與題目所給曲線十分吻合，證明76543210 實數映射下信噪比（人類線粒體四個堿基映射為實數值acg,t，堿基bI{A,T,G,Crbrb{acgtNDNA序列（N3的倍數）在k3 PN3

(2-其中XaxAcxCgxGtxTayAcyCgyGtyTazAczCgzGtzTR=xyzr

基于模糊邏輯的自適應閾值確本章主要解決問題（2。對識別來說，閾值是一個非常重要的參數?；蝾A測的最終目的是從DNA序列檢測出外顯子部分，因此對前一章節對DNADNA序列中將外顯子分離出來。進行外顯子預測時，需要設定一定的閾值。對于不同的類型，所選取有些DNA序列3-周期特性不明顯[9]，在仿真的過程中，甚至發現了部分具有“假3-周期”性的DNA序列，即內含子對應的頻譜也會出現譜峰。因此，本章將選取具有3-周期特性的，并對每類研究其閾值確定方法和閾值結果。問題分析與符號說明根據和題目的連續性，閾值確定方法將繼續基于頻譜3-周期性 3-1符號約定與含義符含符含預備模型：已注釋的最優固定閾值分號Ropt表示。令Tex表示被正確預測為外顯子的堿基個數，Lex表示真實序列外顯子上的理的正確率Ac的定義方法，如(3-1)所示：AcmaxL, 序列的選擇閾值范圍Rmin,Rmax，確定搜索STEPfori=Rmin:STEP:Aci選取maxAc的閾值，定為Ropt因閾值確定的準備工作，對未注釋閾值確定方法將在3.3節具體分析。根據閾值分析法，圖3-1給出了題目數據100個人和鼠的第14號AF019045的正確率隨閾值變化的曲線，曲線的峰值就是我們為這一選定的

AF019045正確率隨閾值變化曲線基于模糊邏輯的自適應閾值模型圖3-2給出了基于頻譜3-周期性的的預測方法流程圖圖中的每個步驟的測試集進試。窗尺寸：將序列分段后，信噪比序列長度相應減小，信噪比曲線窗類型：文獻[11]采用了矩形窗對DNA序列的功率譜進行處理，在截斷的過程，就等于將信號進行加窗函數操作ubnwnn0,1M1。而這當n為偶數時

1,0nM

(3-2n,0n

2n

(3-n

2 nM 2n,0nM

2

2Mn

,M1

nM

(4-76543210 x圖3-3加矩形窗信噪比曲線（39號外外顯6543210 n圖3-4加巴特利特窗的信噪比曲線（39號

x點，若此點的PN/3值大于閾值，則表征此時窗口內的 模糊集合：不同特征（均值、方差、峰值）的模糊集合Fs分為低、中低中高低中高 隸屬度函數曲blfxb

,ax0,xaxaba,axmf

xddc,cx0,xxhfxd

,cx模糊邏輯規則：在閾值范圍Rmin,Rmax上的模糊邏輯規則Fr如 3-3-2序均方峰1低低低rr2低低中rr3低低高rr4低中低rr5低中中rr6低中高rr7低高低rr8低高中rr9低高高rr序均方峰中低低rr中低中rr中低高rr中中低rr中中中rr中中高rr中高低rr中高中rr中高高rr序均方峰高低低rr高低中rr高低高rr高中低rr高中中rr高中高rr高高低rr高高中rr高高高rr值步長，模糊集合Fs，模糊邏輯規則Fr。輸出對每個分段2章的方法計算分組序列在kN3處依據Fs將信噪比的特征值分為低、中、高三個模糊集合通過模糊邏輯Fr規則確定閾值范圍Rmin,Rmax根據上一章節的最優閾值分析法在 , 上求解最優閾值Ropt 形成CRRopt對CRoptR將訓練集內按照Ropt訓練結束后形成訓練集，接下來進試輸出：將序列識別為外顯子和內含子對每個分段2章的方法計算分組序列在kN3處依據Fs將信噪比的特征值分為低、中、高三個模糊集合通過模糊邏輯Fr規則確定閾值范圍Rmin,Rmax根據閾值范圍Rmin,Rmax在波形樣本集中搜索最相似的波形及相應的閾值CRRopt；將Ropt定為該段序列的最優閾值SNR大于閾值的位置評價指標在信號檢測理論中，ROC曲線是一種對于靈敏度進行描述的功能圖像[12]。ROC曲線可以通過描述率和虛驚率來實現。ROC曲線首先是由二戰中的電論。之后很快就被引入了心理學來進行信號的知覺檢測。ROC分析現在已經在作出判斷。ROC曲線將靈敏度與特異性以圖示方法結合在一起，可準確反映某分析方法特異性和敏感性的關系，是試驗準確性的綜合代表。ROC曲線不固定的比較，ROC曲線越凸越近左上角表明其評價價值越大，利于不同指標間的比ROC3-6所數，即錯誤的肯定，表示假，是第一類錯誤；Fin表示被錯誤地判為內含子 Fex預3-6SnT

特異性Sp：表示被預測為外顯子的堿基中真實來自外顯子的比例SpT

用敏感性和特異性兩個指標評價預測準確性，這種方法充分考慮到DNA序列中的每一個堿基，在堿基水平上將預測結果和序列中外顯子的實際位說敏感Sn、特異性Sp和準確率Ac的關系分析三者的定義不難發現，準確率Ac其實就是敏感性和特異性二者的較小結果分析與小結本文從國家生物信息中心NCBI數據庫[14]中了1000個人類和鼠類的樣本，對每個按每段長度900進行分段，通過模糊邏輯自適應閾見附錄2。結表3-3列出了10個的自適應閾值與最優固定閾值分析法得到的固定DNA3-周期特性是堿基分布不平衡造成的，是一個統計學的分析也驗證了這一點，分析表3-3可以看出有部分無論是固定閾值分析413-441號樣本的信噪比曲線及已知的編碼區位置，可以看出編碼區具有3-周表3-3測試的閾 1 6 2 3210 n圖3-741號的信噪比及編碼區位圖3-8至3-11給出了測試集100個中的第84號和97號固定閾值和自適應閾值的預測結果，其中84號的預測準確率由0.4532提高到了0.7925，97號的預測準確率由0.6494提高到了0.9408，從圖中也可以直觀543210 n圖3-884號固定閾值下的信噪43210 n圖3-984號自適應閾值下的信噪3210 n圖3-1097號固定閾值下的信噪預測外顯3210 n圖3-1197號自適應閾值下的信噪基于邊界搜索的識別算DNA序列的所有編碼序列（外顯子）片段，即盡可能“精確地”確定基于小波變換的梯度邊緣檢測解決了傅立葉變換不能解決的很多問題，因而被譽為“數學顯微鏡”。信號邊設(x)是一個在不同尺度下能對信號適當平滑的函數，并滿足條件(x)dx

及lim(x)

(5-定義(x)d(x)，由于(x)dx0，函數(x)是一個小

j(x)2j/2(2j 對于任何函數，小波變換表示為Tjf(xj(xTf2j/2dj(x)2j/2df dx dx j 由（5-3）可以得出，用j(x)對f(x)平滑后的函數的微分對應于f(x)的對曲線的平滑方法一類是采用Gaussian1P(x)P(x)(x)，其 1(x)

22e

n k0求ak

minEa,a,af(x)P 對27號外顯子端點的模糊區域進行邊緣檢測，結果如圖4-1所示。33實際外顯子預測外顯子擬合曲線端點位置210 4-1基于序列重復的邊界搜索算法34-24-33-周期特性進一步增強，而內含

4-2

4-3R序列，對該求R序列重復擴展后作譜分析。H重復擴EMH

確定搜索序列。以外顯子的邊界堿基M為中點分別向兩邊擴展對應序列中的u0，末尾堿基稱為E，對應序列中的uN1R序列。對搜索序列中的每個nn0,1N1加窗，以n為中心向兩邊擴展3l1LL6l3R序列tnn0,1,...,L處的信噪rn對n0,1N1rn在邊界搜索算法中N100，L33，重復擴展k3進行仿真分析。27號的信噪比曲線如圖4-5所示，在該段上預測的外顯子起始點在7718023143210 n圖4-5初步預測的片0 n 搜索序列的信噪比曲對未注釋的預 6個未注釋的預測編碼11087…1570,1704…1749,2401…2492,2716…2881,3114…3159,23456預測外76543210 n 1號的信噪預測外43210 n 2號的信噪預測外210 n 3號的信噪自自適應6543210 n 4號的信噪7預預測外5432100n 5號的信噪自適自適應32100 n 6號的信噪基于信號增強的譜分析技術由于部分序列編碼區（比如，過短的外顯子序列）的3-周期性不強，甚幅度差別不大?？紤]到此種情況，本文設計了一種信號增強技術，對DFT變換后M/3處峰值得到的功率譜Rm進行平滑濾波和信號增強，得到優化的功思想是對弱3-周期性的有效放大，實現準確算法設計(m。其中，信噪比可以通過短時平均信號能量與估計的噪聲門 PmiPmiRi

(5-其中i為相關器的階數；i是一個正的常數因子，控制算法隨信號能量變化的敏感度，并起到平滑因子的作用，i1。i慢變的噪聲門限估計值計算為Qm1Qm1,Qm1P

(5-Pm,Qm1P增強的信號?m通過下式進行計?m(m)RmPmRQ

(5-結果分析P10.5R(1)Q10.1，相關器的階數設為i2，120.40.22104。同時，若(m過大，可能導致信號過大的放大，將比較模糊的信號濾掉，因此限制(m)不超過3dB。率為0.6354，在采用信號增強技術的情況下，的正確率為0.9733。由此說43210 n 信號增強前信噪比及預測結10 n 信號增強后的信噪比及預測結5.2突變中的偽鞍部識變，在n=5000處插入一個堿基C，將n=5000處的堿基刪除，對突變前后的信噪比曲線如圖5-3所示，可以看出插入和刪除確實造成了鞍部效應。

圖5-3突變前后信噪比曲線對 析每個鞍部，判斷其是否屬于偽鞍部。在鞍部周圍分別插入/刪除一個堿基，判以在人類線粒體上插入堿基C的突變為例，在n=5000的鞍部周圍，刪因突變。仿真結果表明，若在某位置插入/刪除一個，使偽鞍部恢復為波刪除刪除刪除4321 n圖5-4偽鞍部隨刪除位置的變總DNA是遺傳物質的載體，但并不是所有的DNA都能夠反映生物的性狀，只有編碼區能夠編碼蛋白質，因此如何從DNA序列中找到編碼區部分成為近年來的一個熱門話題。DNA序列是由一系列字符構成的，怎樣將這些字符轉換DNA序DNAA、C、GT四種字符構成的字符串序列，因此Voss映射、Z-curveDFT進行DFT計算量龐大的問題，提出了不同映射下的功率譜和信估標準來評估預測，獲得了較好的預測效果。為進一步提高預測的準確性，又研究了外顯子端點的精確定位問題。分參考文王震,基于信號處理方法的識別算法研究,博士,,E.Hamori,Hcurve,anovelmethodofrepresentationofnucleotideseriesespeciallysuitedforlongDNAsequence.JournalofBiologicalChemistry,258(2):1318-1327,1983.E.Hamori