基于计算机系统平台上的动态时间规整算法在基因比对中的应用

孙弢

摘 要：信息技术在各个领域的广泛应用也促使生物科学技术的变革，利用计算机系统平台解决基因表达数据时间序列的相似查询有多种方法，本文介绍了一个最常用的算法——在动态时间规整算法基础上进行优化的多分段动态时间规整算法，本文主要研究使用多分段的动态时间规整算法对酵母的基因表达数据进行序列比对，主要从计算速度，时间复杂度，比对精度等方面进行了实验分析。

关键词：计算机系统平台；算法；基因序列比对

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）.