| DNA序列中基于适应性后缀树的重复体识别算法 |
| |
| 引用本文： | 霍红卫,王小武.DNA序列中基于适应性后缀树的重复体识别算法[J].计算机学报,2010,33(4). |
| |
| 作者姓名： | 霍红卫 王小武 |
| |
| 作者单位： | 西安电子科技大学计算机学院,西安,710071 |
| |
| 基金项目： | 国家自然科学基金(69601003);;青年科学基金(60705004)资助 |
| |
| 摘 要： | 现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致.
|
| 关 键 词： | 重复体识别 适应性后缀树 Ukkonen算法 RepSeeker算法 |
An Adaptive Suffix Tree Based Algorithm for Repeats Identification in a DNA Sequence |
| |
| HUO Hong-Wei WANG Xiao-Wu.An Adaptive Suffix Tree Based Algorithm for Repeats Identification in a DNA Sequence[J].Chinese Journal of Computers,2010,33(4). |
| |
| Authors: | HUO Hong-Wei WANG Xiao-Wu |
| |
| Affiliation: | School of Computer Science and Technology/a>;Xidian University/a>;Xi 'an 710071 |
| |
| Abstract: | Many existing methods for repeats identification are based on alignments.Their speed and time significantly limit their applications.This paper presents the fast Rep(eats)Seeker algorithm for repeats identification based on the adaptive Ukkonen suffix tree construction algorithm.The RepSeeker algorithm uses the lowest frequency limit to maximize the extension of repeats.The adaptive improvements to the Ukkonen algorithm are made to increase the efficiency of the RepSeeker algorithm.The node information requ... |
| |
| Keywords: | repeats identification adaptive suffix tree Ukkonen algorithm RepSeeker algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
