串联重复序列识别方法研究.pdfVIP

E—mail：eduf@ceec．net．en ISSN 1009—3044 ComputerKnowledgeAndTechnology电脑知识与技术 http：／／www．dnzs．net．en Vo1．4，No．4，November2008，PP．930—931，937 Tel：+86—551—5690963 5690964 串联重复序列识别方法研究 陈昌平，刘自伟，周文鹃，彭春艳 (西南科技大学 计算机科学与技术学 院，四川 绵 阳621000) 摘要：非编码 区重复序列分析在基 因组研究中起着重要作用 ，其基础就是在非编码 DNA序列 中识别和定位所有 的重复结构。重复 序列识别问题在计算机科学中主要体现为字符 串匹配问题。在分析 了后缀树和后缀数纽字符 串匹配算法的基础上．详细阐述 了基 于后缀数组的精确 串联重复序列识别方法。实验表明，该方法适合用于非编码 DNA序列分析。 关键词 ：串联重复序列；后缀树 ；后缀数组；最大 串联重复序列 中图分类号 ：TP274 文献标识码 ：A 文章编号 ：1009—3044(2008)31—0930—02 TheResearchofM ethodsforIdentifyingTandem Repeat CHENChang—ping，LIuZi—wei，ZHOUWen-juan，PENGChun—yan (SouthwestUniversityofScienceandTechnology，CollegeofComputerScienceandTechnology，Mianyang621000，China) Abstract：Therepeatsequencesanalysisofnon—codingareaplaysanimportantroleintheresearchofgenomes，itsfoundationistO identify andlocatetheperiodicpatterns．Itaddressesthemethodofidentifyingtheaccuratetandem repeatindetaila eranalyzingsuffix treeand sut~]xarrayalgorithmsofstringmatching．TheexperimentindicatesthatthemethodadaptstOnon—codingDNA sequenceanalysis． Keywords：tandem repeat；suffixtree；suffixarray；longesttandem repeat l引言 研究表明，在高等生物和人的基天【I组 中非编码区都 占到基因组序列的绝大部分。这说 明，非编码序列的存在与真核生物基因表 达调控密切相关 。绝大部分非编码序列 以高度重复序列的形式存在 ，如卫星、小卫星、微卫星、长散布元件 、短散布元件等。从物种进 化的观点来看，发生染色体数 目改变的最有可能的机制就是在特定的点发生断裂。产生这种特定的点的方式极有可能是非编码 区 DNA重复序列的加倍 ，而这种加倍的产生必定是 由具有一定催化功能的非编码 DNA功能元件调控的。根据这个机制 ，可以先识别 m非编码 DNA序列 巾的重复序列，然后再有哪些信誉好的足球投注网站其前的功能元件 。因此 ，识别非编码区的重复序列是分析非编码 区功能结构特征的 基础 串联重复序列(tandemrepeat)是指以一定的碱基数作为重复单元，首尾相连排列在一起形成聚集区的重复序列 。串联重复序列 识别问题在计算机科学中主要体现为字符串匹配 问题 ，在分析 了后缀树和后缀数组字符 串匹配算法 的基础上 ．详细阐述了基于后 缀数组 的精确 串联重复序列识别方法 。 2字符串匹配算法 、 在计算机科学领域，字符串匹配算法一直都是研究焦点之一。比较经典的字符串匹配算法有BF[1](Brute—Force)算法，KMP[1]算 法，后缀树和后缀数组算法等。前两种算法广泛用于单模式匹配中，后两种算法用于多模式匹配 、最长回文串查找等