DNA序列中基于适应性后缀树的重复体识别算法

王小武霍红卫

西安电子科技大学;

摘要：

现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了N…展开v

关键词：重复体识别、适应性后缀树、Ukkonen算法、RepSeeker算法

所属期刊栏目：33

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金69601003;青年科学基金60705004

在线出版日期：2010-06-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：747-754