基于計(jì)算機(jī)系統(tǒng)平臺(tái)上的動(dòng)態(tài)時(shí)間規(guī)整算法在基因比對(duì)中的應(yīng)用

孫弢

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

關(guān)鍵詞：計(jì)算機(jī)系統(tǒng)平臺(tái)；算法；基因序列比對(duì)

1 引言

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

2 多分段動(dòng)態(tài)時(shí)間規(guī)整算法

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

（1）時(shí)間序列新特征點(diǎn)（極值點(diǎn)）的搜尋

（2）基于新特征點(diǎn)的動(dòng)態(tài)時(shí)間規(guī)整算法

3 酵母基因表達(dá)數(shù)據(jù)比對(duì)實(shí)驗(yàn)

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

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

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

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

3.2 數(shù)據(jù)來(lái)源

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

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

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

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

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

方差公式為：

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

實(shí)驗(yàn)中用多分段動(dòng)態(tài)規(guī)整算法把原有的時(shí)間序列也就是在77個(gè)時(shí)間點(diǎn)中，尋找時(shí)間序列的極值點(diǎn)，提取了13個(gè)關(guān)鍵特征點(diǎn)，再用提取出的這13個(gè)特征點(diǎn)用動(dòng)態(tài)時(shí)間規(guī)整算法做計(jì)算。

4 結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

[1]文翰.黃國(guó)順語(yǔ)音識(shí)別中算法改進(jìn)研究[期刊論文].模式識(shí)別.2006（2）.

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

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