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

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

基于后缀树的中文新闻重复网页识别算法

针对识别中文新闻重复网页传统方法的不足,提出以后缀树作为基本数据结构,依据新闻网页的标题性和时间性,构建中文新闻重复网页识别算法。该算法以Ukkonen算法和Matching Statistics算法为基础,并对其具体实现进行优化。实验结果表明,该算法不仅具有有效性,而且对计算字符串相似度也有启发意义。

最大频长积字符串及其高效查找算法

在传统的字符串处理算法中往往分别考虑字符串的频度和长度。然而,在实际应用中,将字符串的频度和长度结合考虑是有意义的。基于这点我们提出了频长积的概念,规定字符串的频度和长度的乘积为字符串的频长积。并基于广义后缀树和Uk- konen算法,提出了时间复杂度为O(N)的查找算法。效率实验证实了该算法的高效性。语义实验表明,本算法找出的最大频长积字符串相比于最大频度字符串或最大长度字符串,其实际语义更为明确。这样的字符串在文本压缩、基因序列的分析以及其他注重语义的应用中将具有很高的应用价值。