基于計算機系統平臺上的動態時間規整算法在基因比對中的應用

孫弢

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

關鍵詞：計算機系統平臺；算法；基因序列比對

1 引言

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

2 多分段動態時間規整算法

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

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

（2）基于新特征點的動態時間規整算法

3 酵母基因表達數據比對實驗

3.1 數據分析

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

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

我們的實驗主要針對酵母表達數據展開，通過實驗對多分段動態時間規整算法的相關性計算做數據分析。

3.2 數據來源

本論文實驗數據來源是用Spellman的酵母循環基因表達數據，該實驗數據共有77個時間點，一共是6178個基因。實驗己經知道其中104個酵母基因屬于6個功能類（M/G1 Boundary/STE12/MCM1 dependen、Late G1， SCB regulated、Late G1， MCB regulated、S-phase、S/G2-phase、G2/M-phase），我們主要是針對這104個酵母基因對多分段動態時間規整算法做實驗分析。

3.3 數據處理和結果分析

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

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

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

方差公式為：

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

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

4 結束語

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

[參考文獻]

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

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

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