孫弢

摘 要：信息技術(shù)在各個領域的廣泛應用也促使生物科學技術(shù)的變革，利用計算機系統(tǒng)平臺解決基因表達數(shù)據(jù)時間序列的相似查詢有多種方法，本文介紹了一個最常用的算法——在動態(tài)時間規(guī)整算法基礎上進行優(yōu)化的多分段動態(tài)時間規(guī)整算法，本文主要研究使用多分段的動態(tài)時間規(guī)整算法對酵母的基因表達數(shù)據(jù)進行序列比對，主要從計算速度，時間復雜度，比對精度等方面進行了實驗分析。

關鍵詞：計算機系統(tǒng)平臺；算法；基因序列比對

1 引言

生物信息學是是多學科交叉的產(chǎn)物，它是以互聯(lián)網(wǎng)為媒介，數(shù)據(jù)庫為載體，利用數(shù)學知識建立各種計算模型，并以計算機為工具對實驗生物學中產(chǎn)生的大量生物學數(shù)據(jù)進行采集、存儲、分析、解釋等研究內(nèi)容。生物信息學已經(jīng)在農(nóng)學、醫(yī)藥學、食品、環(huán)境等各種生命學科中廣泛應用。其中，序列比對是生物信息學的基礎也是核心內(nèi)容，在各種生物基因組中都含有成千上萬海量的基因，它們之間相似性問題主要是通過序列比對得到結(jié)論，那么優(yōu)化比對算法尤其重要。比對算法合理，計算速度快，時間短，精度高是衡量一個好算法的主要標準，本文通過對酵母基因的序列比對實驗來證明了多分段的動態(tài)時間規(guī)整算法的合理性及優(yōu)越性。

2 多分段動態(tài)時間規(guī)整算法

動態(tài)時間規(guī)整算法的優(yōu)化，即多分段動態(tài)時間規(guī)整算法的工作原理就是把整個基因表達數(shù)據(jù)，按照時間序列把數(shù)據(jù)分成多個直線段處理，找到一個序列的極值點，從這點出發(fā)，選擇序列中那些對序列形狀影響最大的點稱為特征點，通過連接這些特征點將序列線段化，在此基礎上定義了新的特征點多分段的動態(tài)時間規(guī)整距離。也就是說多分段動態(tài)時間規(guī)整算法是在原來的時間序列的基礎上提取關鍵特征點，在新的特征點再做動態(tài)時間規(guī)整算法。提取新的特征點就是把原來時間序列里變化不大或者變化一致的點忽略掉。多分段動態(tài)時間規(guī)整算法主要包括兩部分：

（1）時間序列新特征點（極值點）的搜尋

（2）基于新特征點的動態(tài)時間規(guī)整算法

3 酵母基因表達數(shù)據(jù)比對實驗

3.1 數(shù)據(jù)分析

酵母基因表達數(shù)據(jù)的時間序列的特征點應該滿足以下兩個條件，一個是該點必須是序列的極值點，另外一個該極值點保持極值的時間段（即該點與前極值點及后極值點的時間段）與該序列長度的比值必須大于某個閾值。

本論文實驗中在任意時刻只要基因表達數(shù)據(jù)超過一個閾值，則認為是需要保留的數(shù)據(jù)，不去改動它；而低于閾值則除掉，然后根據(jù)分段計算數(shù)據(jù)之間的相似度，利用多分段動態(tài)時間規(guī)整算法把時間序列數(shù)據(jù)根據(jù)要求重新擬合，畫出曲線。這種優(yōu)化算法對于時間序列長的基因表達數(shù)據(jù)有著非常好的降低時間復雜度的作用，并且數(shù)據(jù)精確度依然很高。

我們的實驗主要針對酵母表達數(shù)據(jù)展開，通過實驗對多分段動態(tài)時間規(guī)整算法的相關性計算做數(shù)據(jù)分析。

3.2 數(shù)據(jù)來源

本論文實驗數(shù)據(jù)來源是用Spellman的酵母循環(huán)基因表達數(shù)據(jù)，該實驗數(shù)據(jù)共有77個時間點，一共是6178個基因。實驗己經(jīng)知道其中104個酵母基因?qū)儆?個功能類（M/G1 Boundary/STE12/MCM1 dependen、Late G1， SCB regulated、Late G1， MCB regulated、S-phase、S/G2-phase、G2/M-phase），我們主要是針對這104個酵母基因?qū)Χ喾侄蝿討B(tài)時間規(guī)整算法做實驗分析。

3.3 數(shù)據(jù)處理和結(jié)果分析

由于在數(shù)據(jù)采集實驗中存在各種異質(zhì)噪聲和缺失，需要進行數(shù)據(jù)預處理。主要包括以下幾個方面：

⑴缺失數(shù)據(jù)處理：在這104條酵母基因表達數(shù)據(jù)中，有一些酵母基因數(shù)據(jù)有大量的缺失值，本論文實驗中找出了缺失值大于15%的酵母基因表達數(shù)據(jù)將其刪除，這樣的酵母基因表達數(shù)據(jù)一共有15條。

⑵基本不表達數(shù)據(jù)處理：然后在剩余的酵母基因中再去除基本不表達的基因，就是把在一段時間內(nèi)實驗數(shù)據(jù)沒有發(fā)生明顯變化的基因表達數(shù)據(jù)去除。這個可以通過計算每個基因的方差值得到。用方差計算，采用閾值0.25，即刪除方差小于0.25的基因項——共15個，保留基因74項。

方差公式為：

⑶數(shù)據(jù)規(guī)范化：用公式 對酵母基因表達數(shù)據(jù)進行規(guī)范化，使得每個酵母基因數(shù)據(jù)規(guī)范為：0均值，1方差。本論文中的實驗數(shù)據(jù)主要以這個矩陣組成的酵母基因表達數(shù)據(jù)為主。

實驗中用多分段動態(tài)規(guī)整算法把原有的時間序列也就是在77個時間點中，尋找時間序列的極值點，提取了13個關鍵特征點，再用提取出的這13個特征點用動態(tài)時間規(guī)整算法做計算。

4 結(jié)束語

通過進行實驗分析說明使用多分段的動態(tài)時間規(guī)整算法對基因表達數(shù)據(jù)進行比對，無論是在分類還是在精度上也都是很有優(yōu)勢的。隨著時間序列分析的應用需求的增加，這樣的簡便的、高精度的算法可以有廣泛的應用價值。

[參考文獻]

[1]文翰.黃國順語音識別中算法改進研究[期刊論文].模式識別.2006（2）.

[2]唐玉榮.生物信息學中一個優(yōu)化的全局雙序列比對[期刊論文].計算機應用.2004（6）.

[3]翁穎鈞，朱仲英.基于動態(tài)時間彎曲的時序數(shù)據(jù)聚類算法的研究[期刊論文].計算機仿真度.2004（3）.