生物dna序列化对比算法研究

《生物dna序列化对比算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第23卷第2期佳木斯大学学报(自然科学版)V01．23No．220o5年04月JournalofJiamusiUniversity(NaturalScienceEdition)Apr．2005文章编号：100g一1~(2oo5)o2—0153—06生物DNA序列比对算法研究段敏，许龙飞(暨南大学计算机科学系．广东广州510632)摘要：基于典型CLUSTALW序列比对算法，研究一种局部优化的多序歹Ij比对算法，用减少序列比对：．⋯yto中总评分的方法来达到优化算法的目的，并对基因库中的序列进行了测试．关键词：生物信息学；DNA序列；序列比对算法；数

2、据挖掘中图分类号：TP301文献标识码：A0引言DNA多序列比对是生物基因信息系统中，现代生物序列分析的重要内容，也是当今生物信息学研究的热点课题．通过多序列比对，可以预测新序列的结构和功能，可以分析序列之间的相似和同源关系，以及进行系统发育分析，多序列比对是一个具有高计算复杂度的组合优化问题．序列比对就是运用特定的数学模型，寻找两个或多个序列问的最大匹配碱基或残基数，比对结果反映了序列问的相似关系及其生物学特征．目前序列比对的算法很多，这些算法大多基于动态规划的算法思想，根据比对的序列数目不同，序列比对算法可分为两序列比对和多序列比对等．(1)两

3、序列比对算法两序列比对可分为全局比对与局部比对．全局比对是考虑两个序列之间的全局相似性，典型的算法有Needleman—Wunsch算法⋯，该算法适合于全局水平的相似性程度较高的两个序列．局部比对算法的基础是Smith—Waterman算法，该算法较适用于亲源关系较远，整体上不相似，而在较小局部区域中存在局部相似性的两个序列，由于蛋白质具有模糊性质，极可能由于外显子的交换而产生新的蛋白质，因而局部比对有时会更合理．典型的局部比对算法有Smith—Waterman，FAST7．和BLAST算法等[2]．Smith—Waterman算法的基本思想是，使

4、用迭代方法计算出两个序列的相似分值，存入一个评分矩阵，根据评分矩阵，以及动态方法回溯，寻找最优比对序列．由Pearson和Lipman提出的FASTA算法，是一种经改进的两序列启发式算法．在此基础上，后来由Altschul等人提出的BLAST算法是目前国际广泛采用的高效和敏感性较好的算法．它的基点是序列片段对概念，所谓序列片段对是指两个给定序列中的一对子序列，它们的长度相等，且可以形成无空位的完全匹配．(2)多序列比对算法目前的大多数的多序列比对算法基于渐进思想的启发式算法，以降低运算的复杂度，其中使用最广泛的是CLUSTALW，它的基本思想是基于

5、相似序列通常具有进化实习相关性这一假设，其算法过程描述为：1)对多个序列两两比对构成距离矩阵，表示序列间的两两关系；2)由距离矩阵计算系统进化树；基金项目：国家自然科学基金资助项目(60374070)，广东省自然科学基金资助项目(031903)作者简介：段敏(1978一)女，湖北孝感人，研究生研究方向：数据库、生物基因信息系统等、许龙飞(1946一)，男，广东开平人，广州暨南大学计算机科学系教授．研究方向：数据库、生物基因信息系统和知识工程154佳木斯大学学报(自然科学版)2005年3)对关系密切的序列进行加权，从最密切序列开始，逐步引入临近的序列

6、，并不断重新构建比对，直至所有的序列均被加入．近年来有学者引入遗传算法对多序列比对进行研究，如重新设计独特的遗传算子(插入、删去、合并和分离等)，基于BLAST相似度评分方法以及采用完全比对块加权的个体适应度值评价函数，以引导遗传算法寻优局部比对等J．本文所研究的多序列比对算法是在原来CLUSTALW算法基础上，采用了局部优化策略，以MicrosoftVisualC#开发，数据库是SQLServer2000，并用实验给予验证．1相关的研究工作序列比对算法(SequenceAlignmentAlgorithm)，就是根据一个给定的计分函数计算得到两个

7、或多个字符串序列的最优比对．即对两个或多个字符串序列，通过匹配相对应的字符或插入“一”来显示插入或删除，得到序列之间的最大相似性排列．比对的结果反映了算法在多大程度上表达序列之间的相似性关系以及它们的生物学特征．以下是对序列比对问题的描述定义1设为字符表，s1，s2，⋯，为字符表上的字符串，且k≥2，设不包含字符“一”，“一”表示输出串中的空格．一个序列比对是字符表=U{一}上的一个字符矩阵，且满足如下3个条件：(1)矩阵共有k行；(2)矩阵中的i行去掉“一”后，即得到字符串Si；(3)矩阵中不包含字符全是空格的列．如对于序列S=AGCGTAG和T

8、=GTCAGA进行比对，下面的字符矩阵AG—C—GTAG——GTCAG——A为序列S，的一个比对．定义2两个序列s和T，l