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

An Adaptive Suffix Tree Based Algorithm for Repeats Identification in a DNA Sequence

现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致.

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 required by the RepSeeker algorithm is added during the suffix tree construction.Because information on leaves and branch nodes are different,the RepSeeker algorithm directly obtains the needed information from the nodes to find out the frequency and locate the positions of a substring.The improvement is considerable for the repeats identification at a little extra cost in space.Nine sequences from the National Center for Biotechnology Information （NCBI） are used to test the performance of the RepSeeker algorithm.Comparisons between before and after improvements of the suffix tree construction show that the running time of the RepSeeker algorithm is reduced without losing the accuracy.The experimental results agree with the theoretical expectations.