【作者】 郭顺； 管河山； 姜青山；

【Author】 Guo Shun~1,Guan Heshan~2,and Jiang Qingshan~1 1(Software School,Xiamen University,Xiamen,Fujian 361005) 2(Department of Computer Science,Xiamen University,Xiamen,Fujian 361005)

【机构】 厦门大学软件学院； 厦门大学计算机科学系；

【摘要】 寻找DNA序列中的重复片段是DNA序列挖掘中的一项重要的研究内容,它是基因分析的一个重要问题.通常的方法采用特定的索引结构如后缀树、后继数组等,算法效率有待提高.提出一种新的索引结构,并在此基础上提出了MSATR算法.MSATR算法可以适用于各种不同相似度定义的DNA重复片段的查找.分析和实验表明,MSATR算法时间和空间复杂度为O(n).实验结果表明,MSATR算法有较好的查找效率,并且MSATR算法能得到较好的查找结果.更多还原

【Abstract】 In gene analysis,finding approximate repetitions in DNA sequence is an important problem.Proposed here is 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 it is also time saving.更多还原