k-长DNA子序列计数算法研究

基因组的结构与功能存在密切联系，其功能主要通过DNA子序列来表达，因此研究DNA序列结构对于生物信息学来说具有重要的意义。该文研究了k-长DNA子序列在DNA全序列中出现频数的计数问题，设计并实现了k-长DNA子序列内部计数算法和外部计数算法。该算法通过一个哈希函数把k-长DNA子序列映射为整数关键字从而把k-长DNA子序列出现频数的计数问题转化为整数关键字的重复计数问题，使得能够利用经典B树算法来解决k-长DNA子序列的出现频数计数问题。针对所要解决的问题提出3种改进措施以进一步提高算法的性能。     

基于离散度函数的DNA序列的相似性分析

用一种新的信息离散性量度法分析DNA序列的相似性。该法用DNA序列的子序列分布来描述DNA序列,从而充分考虑了DNA序列的信息。对不同的子序列长度,分析了11类不同生物的β-globin基因的第一个外显子的编码序列的相似性,结果表明,该法是分析DNA序列相似性的简单而有效的工具。     

基于二级索引结构无候选项闭合序列模式挖掘算法

针对CloSpan算法分两个阶段挖掘闭合序列模式中第一阶段需要保持候选序列且未充分利用项的位置信息、存在对数据库重复扫描和计算大小的不足,提出了posCloSpan算法。算法通过对二级索引结构进行检索实现向前剪枝,避免数据库重复扫描以及对超序索引表、子序索引表的检测,实现非闭合序列的修剪,无须保存候选序列。实验结果证明,算法在处理较长序列以及存在大量重复投影数据库的数据源时,有效降低了时间上的开销。     

基于符号化表示的时间序列频繁子序列挖掘

提出一种新的基于符号化表示的时间序列频繁子序列的挖掘算法。利用基于PAA的分段线性表示法进行降维,通过在高斯分布下设置断点,实现时间序列符号化表示,利用投影数据库挖掘频繁子序列。该算法简单、新颖,运行快速,简化了子序列支持数的计算。     

基于SPAM-FPT的WebLog访问序列模式挖掘

WebLog访问序列模式挖掘将数据挖掘中的序列模式技术应用于Web服务器上的日志文件,以此来改善Web的信息服务,而在对海量的数据挖掘时,系统资源开销很大。该文结合SPAM、PrefixSpan的思想,提出一个新的算法——SPAM-FPT,该算法通过建立First_Positon_Table,避免了SPAM中的“与操作”、“连接操作”以及PrefixSpan中大量的“投影数据库”的建立,可以快捷地挖掘数据库中所有“频繁子序列”。     

基于子序列全连接和最大团的时间序列模体发现算法

针对时间序列模体发现算法计算复杂，并且无法发现多实例模体的问题，提出基于子序列全连接和最大团的时间序列模体发现（TSSJMC）算法。首先，使用快速时间序列子序列全连接算法求得所有子序列之间的距离，生成距离矩阵；然后，设置相似性阈值，将距离矩阵转化为邻接矩阵，构造子序列相似图；最后采用最大团搜索算法从相似图中搜索最大团，最大团的顶点对应的时间序列为包含最多实例的模体。在公开的时间序列数据集上进行实验，选用已有的能够发现多实例模体的Brute Force和Random Projection算法作为对比对象，分别从准确性、效率、可扩展性和鲁棒性对TSSJMC算法进行分析并获得了客观的评判结果。实验结果表明，与Random Projection算法相比，TSSJMC算法在效率、可扩展性和鲁棒性法方面均有明显优势；与Brute Force算法相比，TSSJMC算法发现的模体实例数量虽略低，但其效率和可扩展性都优于Brute Force算法。因此，TSSJMC是质量和效率相平衡的算法。     

时间序列流Top-K不协调子序列的发现

摘要: 针对传统算法中有关时间序列流不协调子序列计算代价比较高的问题,提出了一种快速发现Top-K不协调子序列的算法。该算法通过特殊的数据结构保留计算结果,避免了大量的重复计算,从而达到降低时间复杂度的目的;同时也通过一定的保留策略只保留有用的计算结果并及时清理无用的计算结果,从而达到降低空间复杂度的目的。实验采用随机数据和真实数据进行算法测试,其结果表明,该算法能显著降低计算量从而实现快速发现Top-K不协调子序列的目的。 关键字: 流时间序列;不协调子序列;实时     

一种具有精确边界的重复体识别算法

当前大部分重复体识别算法不是依靠于已经标识的重复体数据库就是定义重复体为两个最大长度的相似序列,而没有一个严格的定义来平衡重复体的长度和频率.针对这些问题文中提出了一种基于局部序列比对算法BLAST变型且支持空位的快速识别重复体的RepeatSearcher算法.算法通过定义重复体的精确边界运用逐步扩展调和序列来识别重复体.算法使用C.briggsae基因组序列作为测试对象,并与当前通用的重复体识别算法RECON以及新近的识别算法RepeatScout做了比较分析.结果表明RepeatSearcher使每一条重复体序列具有了精确的边界,而且相对其它算法在没有损失精度的情况下,缩短了算法的运行时间.     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

基于分形的DNA序列可视化表示研究

DNA序列可视化表示对于研究其结构与功能具有至关重要的意义,它有助于重复子序列的识别、内含子与外显子的区分以及DNA序列进化研究等等。本文首先介绍了生成DNA序列分形图像的Hao方法和经典的混沌游戏方法,然后深入分析和比较了这两种方法的异同点,并讨论了禁止子序列中回文子序列情况;紧接着,阐述了迭代函数系统产生分形吸引子的数学机理,并根据Moore自动机与迭代函数系统定义了混沌自动机,然后详细研究了以DNA序列驱动混沌自动机产生分形图像的方法;最后提出DNA序列三联密码子的分形图像表示方法,并对其进行了初步研究。     

基于高效精确的最大公共子序列的视频片段匹配

为视频序列匹配提出一个高效精确的最大公共子序列（Efficient and Effective Longest Common Subsequence,EELCS）算法。首先,利用矢量量化（Vector Quantization,VQ）将多维最大公共子序列算法（Multi-dimensional LCS,MLCS）中元素对匹配过程中的实际距离的计算简化成比较操作,较原始的最大公共子序列匹配算法（Original LCS,OLCS）,该处理不仅可以继承MLCS的可应用到实际多维时序匹配问题中的优点,同时大大降低了匹配的复杂度;然后进一步区分待匹配序列中由于匹配子序列和未匹配子序列在时间轴上连续性而产生的差异;最后将该算法应用到视频片段的匹配中。实验结果表明,与具有代表性的基于时间规扭曲的最大公共子序列（Time-Warped LCS,T-WLCS）和连续最大公共子序列（Continuous LCS,CLCS）相比,该算法能较好地应用于视频序列的匹配。     

基于改进DTW算法的手写签名识别系统设计

在线手写签名验证是一种基于生物特征的身份认证技术。为提高签名验证的效率,该文介绍了一种改进的在线签名识别算法。它优化了传统的动态时间弯折算法结构,提出了对最佳匹配路径的动态规划方法并将其应用于在线签名识别系统中。在模板较多时对匹配距离将适当限制,从而减少了系统运算量,提高了模板匹配速率。随着待识别模板数目的增多,该算法的效率优势更加明显。试验结果表明,该改进算法的运算效率高,误拒率和误纳率较低。     

基于AC自动机的多模式匹配算法FACA

Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态。为此,提出一种快速多模式匹配算法。该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率。算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息。实验结果表明,该算法匹配精确、效率高,且支持在线操作。     

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

入侵检测系统中的带权模式匹配算法

入侵检测系统（IDS）需要根据每个模式串的权值,计算给定主串的总权值并反馈给报警系统。传统的模式匹配算法在计算主串权值时效率低。为此,文中在Aho—Corasick算法的基础上,提出了带权模式匹配算法（WPM）及其改进算法（WPME）。算法优化了自动机的建立过程,对自动机每个节点的失配后继指针信息和匹配量信息进行预处理,从而避免了模式匹配阶段在计算主串权值时的回溯操作,降低了算法的时间复杂度。实验表明,改进后的算法具有效率高、匹配精确的特点。     

Efficient subsequence matching over large video databases

Video similarity matching has broad applications such as copyright detection, news tracking and commercial monitoring, etc. Among these applications, one typical task is to detect the local similarity between two videos without the knowledge on positions and lengths of each matched subclip pair. However, most studies so far on video detection investigate the global similarity between two short clips using a pre-defined distance function. Although there are a few works on video subsequence detection, all these proposals fail to provide an effective query processing mechanism. In this paper, we first generalize the problem of video similarity matching. Then, a novel solution called consistent keyframe matching (CKM) is proposed to solve the problem of subsequence matching based on video segmentation. CKM is designed with two goals: (1) good scalability in terms of the query sequence length and the size of video database and (2) fast video subsequence matching in terms of processing time. Good scalability is achieved by employing a batch query paradigm, where keyframes sharing the same query space are summarized and ordered. As such, the redundancy of data access is eliminated, leading to much faster video query processing. Fast subsequence matching is achieved by comparing the keyframes of different video sequences. Specifically, a keyframe matching graph is first constructed and then divided into matched candidate subgraphs. We have evaluated our proposed approach over a very large real video database. Extensive experiments demonstrate the effectiveness and efficiency of our approach.     

改进的QS模式匹配算法的性能分析

在详细分析QS匹配算法的基础上,提出了一种改进的算法I_QS算法。I_QS算法把模式串中每相邻两个字符构成一个字符串,由这些字符串组成字符串表并确定其位置,同时通过当前匹配窗口的后三个字符来确定下一次的右移量。为了分析I_QS算法的性能,从不同模式串数目角度,对I_QS算法进行匹配所需要的时间、所尝试的次数、所比较的字符个数三方面进行实验。实验结果表明,由于I_QS算法能够最大限度地向右移动,从而大大地减少移动次数和缩短匹配时间,有效地提高模式匹配速度。     

A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases

In this paper, an algorithm is proposed for subsequence matching that supports normalization transform in time-series databases. Normalization transform enables finding sequences with similar fluctuation patterns even though they are not close to each other before the normalization transform. Simple application of existing subsequence matching algorithms to support normalization transform is not feasible since the algorithms do not have information for normalization transform of subsequences of arbitrary lengths. Application of the existing whole matching algorithm supporting normalization transform to the subsequence matching is feasible, but requires an index for every possible length of the query sequence causing serious overhead on both storage space and update time. The proposed algorithm generates indexes only for a small number of different lengths of query sequences. For subsequence matching it selects the most appropriate index among them. Better search performance can be obtained by using more indexes. In this paper, the approach is called index interpolation. It is formally proved that the proposed algorithm does not cause false dismissal. The search performance can be traded off with storage space by adjusting the number of indexes. For performance evaluation, a series of experiments is conducted using the indexes for only five different lengths out of lengths 256512 of the query sequence. The results show that the proposed algorithm outperforms the sequential scan by up to 2.4 times on the average when the selectivity of the query is 10^–2 and up to 14.6 times when it is 10^–5. Since the proposed algorithm performs better with smaller selectivities, it is suitable for practical situations, where the queries with smaller selectivities are much more frequent.     

基于导数序列的时间序列同构关系发现

时间序列子序列匹配作为时间序列检索、聚类、分类、异常监测等挖掘任务的基础被广泛研究。但传统的时间序列子序列匹配都是对精确相同或近似相同的模式进行匹配,为此定义了一种全新的具有相似发展趋势的序列模式——时间序列同构关系,经过数学推导给出了时间序列同构关系判定的法则,并基于此提出了同构关系时间序列片段发现的算法。该算法首先对原始时间序列进行预处理,然后分段拟合后对各时间序列分段进行同构关系判定。针对现实背景数据难以满足理论约束的问题,通过定义一个同构关系容忍度参数使实际时间序列数据的同构关系挖掘成为可能。实验结果表明,该算法能有效挖掘出满足同构关系的时间序列片段。