匹配技术在多序列比对中的运用范文

本站小编为你精心准备了匹配技术在多序列比对中的运用参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

《信息系统工程杂志》2014年第十期

一、问题提出

由于星比对算法平方级的时间复杂度无法满足实际需要，文献[6]对其进行改进，提出了基于关键字树的DNA多序列星比对算法。其主要思想是依次将每个序列都分割成等长的子串集合，为这个集合构建一棵模式树。除该序列的其他序列使用Aho-Corasick算法对该模式树进行模式匹配，并记录所有模式串出现次数的总和。将出现次数总和值最大的序列定为中心序列，然后根据星比对算法中“一旦为空格，始终为空格”的思想，将其他序列与中心序列的未匹配部分进行多序列比对。文献[6]虽然将星比对算法的平方级时间复杂度降到了线级，但在选取中心序列时，模式串的出现次数没有考虑是否为公共的模式串，使得选取的中心序列并非为最优解。本文在文献[6]的基础上进行改进，建立一棵公共的模式树，所有序列都使用Aho-Corasick算法对这棵公共的模式树进行模式匹配，并使用数组记录搜索得到的模式号，通过对数组中的模式号的逐级筛选，最后剩下的序列所包含的公共的模式串为最多，增强了算法寻求最优解的能力。实验表明改进后的算法更能获得最优解。

二、模式树模型

模式树模型[7]描述如下：定义1：由模式串集合构成的模式树K是一棵有根树，满足：(1)K的每一条边由1个字符标记；(2)与同一节点相连的任意多条边标记的字符均不相同；(3)每个模式串都对应着一个节点v，使得，其中是从根节点到节点v所经过的边的对应字符的拼接；(4)K的每个叶节点v''''，存在模式串，使得。

三、算法描述

基于模式匹配的多序列比对算法仍然是以星比对为基础的，分为寻找中心序列和两两比对两个主要步骤。要寻找中心序列，设需要进行比对的多个序列分别是。具体操作如下。步骤1：将每个序列等分成长度为r的子序列构成子序列集合L，（l取值，k取值）。将集合L中的所有子序列构成一棵公共的模式树T。步骤2：对于公共的模式树T，每个序列利用Aho-Corasick算法搜索T，并记录每个序列匹配的模式号和该模式在当前序列中出现的位置，其中模式号表示模式树中该模式的编号。这里使用一个多维数组进行记录，表示序列Pi搜索T时，匹配编号为Pos[j]的模式串在Pi中的位置为Pos[j,j]。步骤3：统计每个序列匹配的模式号，这里只考虑搜索T时通过非失效链接得到的模式号，并使用一个二维数组进行统计。表示匹配成功的模式号，表示序列Pi匹配编号为的模式串的次数。步骤4：依次找出匹配次数最多的那个模式号，将没有匹配该模式号的序列从查找中心序列的队列中去除，最后剩下的序列将是中心序列Pc。步骤5：得到中心序列后，将Pc与依次进行比对。由于在步骤(4)中已经记录了Pc和Pi匹配的子串位置，然后使用动态规划算法将Pc和Pi未匹配的子串进行比对。并且记录需要在Pc和Pi中插入空格的位置Sci和Si。步骤6：依次比对完Pc和后，对所有需要插入空格的位置汇总，汇总后的位置记为Sc，分别比较Sc和Sci，在Si中加入新汇入的空格位置。分别根据Si中记录的空格位置将空格插入到Pi中并输出多序列比对的结果。

四、实验结果与分析

实验将基于模式匹配的多序列比对算法和星比对算法、基于关键字树的DNA多序列星比对算法进行比较。实验PC的CPU为Pentium(R)Dual-CoreT42002.00GHz，内存为2.00GB，操作系统为Windows7，运行环境为VistualStudio2008。选取了两组数据进行测试，对每组测试数据都连续运行程序20次，并从程序运行时间和碱基对匹配情况两个方面比较三种算法的期望时间复杂度和比对的效率。第一组实验通过对6种西藏部分地区豆科植物的根瘤菌多序列比对，完成DNA同源性分析。实验数据来自于NCBI上的核酸库以及文献[8]。序列的条数为6，序列的平均长度为1428。该实验数据程序运行时间如图1所示。第二组实验通过对11个物种的β-球蛋白基因的第一个外显子进行多序列比对。实验数据来自于NCBI上的核酸库以及文献[9]，序列的条数为11，序列的平均长度为92。该实验数据程序运行时间如图3所示。统计11个物种的β-球蛋白基因第一个外显子的碱基对匹配情况如图4所示。通过第一组实验结果可知，在运行时间上本算法虽然略高于基于关键字树的星比对算法，但其碱基对匹配数却远高于基于关键字树的星比对算法。因为本算法在寻找中心序列时采用的是逐级去掉希望最小的序列，最后剩下的序列所包含的公共的子串为最多，相对于基于关键字树的星比对算法中直接将模式串出现次数最多的序列定为中心序列的方法，得到的结果则更接近最优解。在第二组实验中，本算法的碱基对匹配数也高于基于关键字树的星比对算法，与星比对算法更为接近。在运行时间方面，由于本实验所选取的序列相似性很高，寻找中心序列时统计每个序列共有的模式号的个数接近k值，所以可以认为寻找中心序列的运行时间为O(n2k)。而基于关键字树的星比对算法的寻找中心序列运行时间为O(n2l)，k是待比较的序列所分割的段数，取值O(l/logl)，远小于l，所以O(n2k)也远小于O(n2l)。在建立好模式树后，本算法和基于关键字树的星比对算法一样，将完全匹配的子串位置存储下来。所以在其他序列与中心序列逐个进行比对的过程中，对于完全匹配的子串就不需要再进行比对。另外，其他序列与中心序列采用动态规划算法进行比对，其运行时间与比对的长度呈平方关系。如果相似程度非常高的序列进行比对，匹配的子串个数与k越接近，那么在每个序列与中心序列进行比对的长度就越短，花费的时间也就越少。

五、结论

本文提出了一种新的生物序列比对算法——基于模式匹配的DNA多序列比对算法。此算法是在星比对算法和Aho-Corasick算法的基础上，针对基于关键字树的DNA多序列比对方法提出来的。由于此算法是对原始星比对算法的一种改进，所以算法的实现仍然包括两个步骤：寻找中心序列和序列两两比对。通过实验结果表明，新算法相对于基于关键字树的DNA多序列比对算法的准确率更高，相对于原始星比对算法的运算速度更快。

作者：王樱杨丽李锡辉单位：湖南信息职业技术学院计算机工程系