一种新的DNA序列重复片段的查找算法.doc

基金项目：厦门大学校科研基金(0630-X01117)；国家自然科学基金。 一种新的DNA序列重复片段的查找算法 郭顺1 管河山2 姜青山1 1(厦门大学软件学院 厦门 361005) 2(厦门大学计算机科学系 厦门 361005) ( gsgowell@163.com) A Novel Algorithm for Finding Approximate Tandem Repeats in DNA Sequences Guo Shun1, Guan Heshan2, Jiang Qingshan1 1(Software School, Xiamen University, Xiamen 361005) 2(Department of Computer Science, Xiamen University, Xiamen 361005) Abstract In gene analysis, finding approximate repetitions in DNA sequence is an important problem. This paper proposes a new efficient algorithm (MSATR) for detecting approximate tandem repeats in genomic sequences. The theoretical analysis and experimental results show that both space and time complexity of the algorithm is O (n). This algorithm also allows a wide range of definitions of similarity of approximate tandem repeats. The experiment results show that this algorithm is superior to other methods in finding results and time saving. Key words DNA sequence mining; approximate repetitions; segment-similarity; MSATR; 摘 要 寻找DNA序列中的重复片段是DNA序列挖掘中的一项重要的研究内容，它是基因分析的一个重要问题。通常的方法采用特定的索引结构如后缀树，后继数组等，算法效率有待提高。这篇论文提出一种新的索引结构，并在此基础上提出了MSATR算法。MSATR算法可以适用于各种不同相似度定义的DNA重复片段的查找。分析和实验表明，MSATR算法时间和空间复杂度为O(n)。实验结果表明，MSATR算法有较好查找效率，并且MSATR算法能得到较好的查找结果。 关键词 DNA序列挖掘；相似性重复片段；片段相似度；MSATR； 1 引言 生物信息学(Bioinformatics)是生命科学、计算机科学、信息科学和数学等学科交汇融合所形成的一门交叉学科[1], DNA序列数据是生物信息学的主要研究对象之一。通过分析DNA序列,科学家不仅能够解已有的序列,而且能够更好地研究新的序列及其功能,解读序列在生物体中充当的角色,进而理解生命本质[2]。而在DNA序列中经常包含一些连续的重复模式称为重复片段((TRs),Tandem Repeats)。这些重复的片段同它们的生物功能一样不能被完全理解，但是，它们被确定在基因组织和进化上起着重要的作用[3,4]。目前，重复片段作为一个重要的遗传标记，已经广泛运用于精密遗传连锁作图、肿瘤生化研究、法医学个体识别、亲子鉴定和群体遗传学分析等领域[5,6]。因此，采用数据挖掘技术，查找和分析这种重复片段显得十分必要。 现有的查找算法[7-12]包括完全重复片段查找的算法和相似性重复片段查找的算法。完全重复片段查找算法[7-9]查找的是DNA序列中多个完全相同的模式串联而成的片段，这些算法的复杂度为O(nlogn)。但是，由于基因的突变，迁移，反转，重复片段往往不完全相同[11]。于是，相似性重复片段((ATR),Approximate Tandem Repeat)被提出来，并且出现了大量的查找ATRs[10-12]算法。 本文提出的新的算法MSATR（Motif-divide based Search Approximate Tandem Repeats），该算法先在第一阶段根据模式长度将DNA序列划分成多个串联的模式放入数组，再在第二阶段将已经建立的数组中的模式进行连接。实验和分析表明，同SUA_SATR [12]算法相比，