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

非编码区重复序列分析在基因组研究中起着重要作用,其基础就是在非编码DNA序列中识别和定位所有的重复结构。重复序列识别问题在计算机科学中主要体现为字符串匹配问题。在分析了后缀树和后缀数组字符串匹配算法的基础上,详细阐述了基于后缀数组的精确串联重复序列识别方法。实验表明,该方法适合用于非编码DNA序列分析。     

基于频谱分析的串联重复序列识别方法

针对现有串联重复序列识别方法存在的计算量大、灵敏度低等问题,提出一种基于频谱分析的串联重复序列识别方法。该方法采用碱基的电子离子相互作用势作为基因序列数字化表示的方法,通过对数字序列作离散傅里叶变换得到序列中串联重复序列出现的频率,并对基因序列做加窗傅里叶变换,找出串联重复序列存在的位置。实验表明,该方法的计算量较已有方法减少了75%,并能较好地解决已有方法识别灵敏度低的缺点。     

两种重复提取算法的研究比较

在利用计算机处理文本信息时,为了能发现大文本信息中的重复词句,本文介绍两种用来发现重复词句的算法——基于后缀树的方法和基于倒排索引的方法。第一种ST算法使用树型数据结构,每个节点表示一个字并且根节点为空。第二种算法应用倒排索引,以及哈希表实现方法（HT）。对同一样本运行仿真后,在时间和空间复杂度上对实验结果进行比较。得出结论,尽管ST算法在考虑到时间成本时要更优,但在空间复杂度方面倒排索引方法更胜一筹。     

关于重复词句提取的两种算法分析

针对重复网页的去重问题,对两种重复词句提取算法进行了系统分析比较。STC算法在时间成本上具有优秀性能,重复序列的倒排索引方法在空间复杂度方面更胜一筹。结合STC算法对重复序列方法进行了改进,而面向主题转载的重复网页,先抽取重复串,然后将重复串作索引进行STC算法的重复抽取。实验结果表明,改进算法在保持了原有空间特性的基础上极大地提高了时间效率。     

串联重复序列比对的位置筛选方法

串联重复序列是基因组构建的困难片段,由于其重复单元之间的相似性与其拷贝数的不确定性,在序列比对时容易定位到多个候选位置,如何快速而准确地筛选出正确的比对位置是一项挑战。现有方法使用种子（从测序片段中选取的短序列）来定位并扩展候选比对位置,但挑选种子时未考虑串联重复序列特性。因此,提出了一种串联重复序列比对的位置筛选方法,其通过计算稀有kmer（长度为k的子序列）序列的相似性来筛选比对结果。此外,采用合并稀有kmer的策略加速计算,并利用基于编辑距离的模糊查找以提高过滤信息密度。实验结果表明,在模拟数据集上提高比对结果的召回率与准确率的同时,该方法比现有方法快约2倍,且具有良好的并行加速性能。     

基于重复模式的Web信息抽取

网页中的大量数据记录往往以重复的HTML结构进行有规律的组织,从而形成一致的表现形式。根据这一特征,本文给出一种基于重复模式的Web内容抽取方法。通过使用一种叫做后缀树的数据结构,分析页面结构中所包含的重复模式,进而从模式的实例中抽取出对应的数据记录。     

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

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

大规模基因组重复序列识别与分类研究进展

重复序列在基因组中普遍存在,大量实验证实其在生物进化过程中起着重要作用.目前,重复序列的发现与识别技术已经成为基因组学的研究热点,文章分类总结了有关这方面的研究进展,并对相关工具的功能特点进行了简要分析,同时对重复序列发展趋势进行了总结和展望.     

基于后缀结构进行数据块优化的重复数据删除系统

为进一步提高重复数据删除系统的性能,提出基于数据分块的后缀数组SA和最长公共前缀LCP进行数据块优化的重复数据删除系统。系统首先将输入的数据流进行第一次分块,识别出相同的分块并给分块编号,创建分块编号序列的SA和LCP表,识别出最大重复队列和非重复数据块,进一步得出优化的超级块大小,然后以超级块为单元进行第二次数据分块并保存数据压缩结果。实验表明,相比于固定分块,该系统能实现给定输入流较好的压缩性和数据重构性。     

后缀数组创建算法的分析和比较

后缀数组构建算法的时间和空间开销是它在实际应用中的瓶颈。该文介绍了两种较好的构建算法,对它们的性能作了评估和分析,指出了各自的适用范围,给出并比较了两种算法在不同情况下的实验结果。     

Tandem repeat查找方法比较

Tandem repeat在基因组成和进化中起到非常重要的作用,查找和分析Tandem repeat已经成为当前生物信息学的一个前沿领域和研究焦点.目前在这一研究领域存在多类解决方法,主要有基于LZ分解技术的方法和最近兴起的基于后缀树索引的方法.本文选取了两种时间复杂度达到O（nlogn）数量级的代表性的方法,对这两种方法进行了全面的综述,并对它们的性能进行了系统的比较和分析.     

Efficient implementation of suffix trees

We study the problem of string searching using the traditional approach of storing all unique substrings of the text in a suffix tree. The methods of path compression, level compression and data compression are combined to build a simple, compact and efficient implementation of a suffix tree. Based on a comparative discussion and extensive experiments, we argue that our new data structure is superior to previous methods in many practical situations.     

变阶马尔科夫模型算法实现

如何快速有效对历史数据进行统计建模和规律挖掘具有重要意义.鉴于模型在实际数据挖掘应用的局限及马尔科夫模型的良好统计特性,设计实现了基于后缀数组和后缀自动机的变阶马尔科夫模型.算法在后缀树形结构实现的基础上,引入后缀链,实现各状态子序列的快速跳转,能动态自适应计算不同阶长概率的需求.实验结果表明：相比传统马尔科夫模型,模型能在线性时间和空间复杂度内,构建历史数据的概率统计特征及各状态后缀子序列之间的链接关系,大大降低了存储空间和时间,能实现大规模数据的在线学习和应用.     

大规模语料中频繁模式增量发现算法

提出一种适用于大规模语料的频繁模式增量发现算法。统计局部区域提取的字符串频度,对局部相对低频字符串进行剪枝。利用多模式串匹配算法,统计剪枝后局部相对高频字符串在整个语料中的频度,得到频度大于阈值的频繁模式。实验结果表明,该算法具有较低的空间复杂度和时间复杂度,内存消耗为基于后缀数组的频繁模式发现算法的20%左右。     

维吾尔文后缀树构造算法的设计与实现

为用后缀树聚类算法对维吾尔文网页进行聚类,通过分析可扩展后缀树和维吾尔文的特点设计了维吾尔文后缀树构造算法。实验结果证明该方法能够在线性的时间范围内构造维吾尔文后缀树,并用它来对维吾尔文网页进行聚类。     

Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem

We present new algorithms for computing matching statistics with suffix arrays. We show how the Multiple Common Substring Problem can be solved efficiently in practice with a new approach using matching statistics. This problem consists of finding the common substrings of a set of strings. For the computation of matching statistics we compare seven different methods based on suffix trees and suffix arrays. Most of the suffix array algorithms have an inferior asymptotic worst case running time but a very low memory overhead and small constants in the running time complexity. Our experiments show a good performance in practice. Copyright © 2005 John Wiley & Sons, Ltd.     

A space efficient solution to the frequent string mining problem for many databases

The frequent string mining problem is to find all substrings of a collection of string databases which satisfy database specific minimum and maximum frequency constraints. Our contribution improves the existing linear-time algorithm for this problem in such a way that the peak memory consumption is a constant factor of the size of the largest database of strings. We show how the results for each database can be stored implicitly in space proportional to the size of the database, making it possible to traverse the results in lexicographical order. Furthermore, we present a linear-time algorithm which calculates the intersection of the results of different databases. This algorithm is based on an algorithm to merge two suffix arrays, and our modification allows us to also calculate the LCP table of the resulting suffix array during the merging.     

求最长公共子串问题的算法分析

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.