一种优化的蛋白质序列模式挖掘方法

蛋白质序列作为生物序列数据一个重要组成部分,对其的分析研究已经成为生物信息学中的一个重要的研究方向和内容.通过对序列进行模式挖掘,可以对蛋白质序列或某一蛋白质家族序列进行研究,因此蛋白质序列的模式挖掘已经成为蛋白质序列研究中的一项重要任务.MBioPM是一种最新的生物序列模式挖掘算法,该算法通过引入模式划分概念,提高算法的效率,但该算法在效率方面仍存在不足,而且挖掘结果存在冗余性的问题.因此,提出一种优化算法BioPMMH,通过带有模式划分特点的Hash链表结构来优化算法中的搜索空间及策略,并在算法过程中对重复模式进行过滤.实验表明,算法BioPMMH能有效提高模式挖掘的效率,并解决结果的冗余性问题.     

ProFaM:一个蛋白质序列家族挖掘算法

有效分析蛋白质家族是生物信息学的一项重要挑战,聚类成为解决这一问题的主要途径之一.基于传统序列比对方法定义蛋白质序列间相似关系时,假设了同源片断问的邻接保守性,与遗传重组相冲突.为更好地识别蛋白质家族,提出了一种蛋白质序列家族挖掘算法ProFaM.ProFaM首先采用前缀投影策略挖掘表征蛋白质序列的模式,然后基于模式及其权重信息构造相似度度量函数,并采用共享最近邻方法,实现了蛋白质序列家族聚类.解决了以往方法在蛋白质模式挖掘及相似度设计中的不足.在蛋白质家族数据库Pfam上的实验结果证实了ProFaM算法在蛋白质家族分析上有良好的结果.     

Hadoop框架下节点重要性算法实现蛋白质功能预测

论文从蛋白质序列数据的角度出发,通过序列相似度循环匹配构造蛋白质网络,并且通过网络节点重要性排序算法预测蛋白质功能.以节点重要性重要性作为研究对象,在蛋白质网络应用节点重要性算法PageRank计算网络中蛋白质节点PR值,在Hadoop平台上进行开发实现功能预测的并行计算,减小运行时间.最后通过准确率,召回率以及F1-measure三个指标来衡量结果,并对比传统的功能预测方法,验证结果的有效性.     

无线传感器网络中基于模式序列分类的分布式数据流过滤技术

研究了无线传感器网络中产生的分布式数据流的过滤技术.在传感器网络中,传感器感知到的是无限、连续、实时、快速的数据.然而,在一些实际的应用中,由于传感器能量的有限性,传感器传送所有感知数据是不实际的.针对这一问题,提出一种基于模式序列分类的数据过滤技术,来减少数据的传输量,从而达到节省资源的目的.基于模式序列分类的数据过滤技术不考虑内网聚集,在传感器的缓存中存有一些模式序列,给定一个相似度衡量阈值,对传感器在某一段时间里感知到的数据做出处理,在已有的模式序列中寻找与当前传感器采集感知到的这段数据的相似序列,传感器只用传送部分数据.通过实验验证了提出算法和策略的有效性.     

一种序列模式的相似性查询算法

数值型序列在很多应用中存在,如超市的POS销售记录和证券交易所的股票买卖数据等.在此类数据中查询与给定序列模式相似的子模式具有重要的现实意义.提出一种趋势融合的序列相似性查询算法NSS_QA,首先对所有序列进行单调区间的“融合”处理,然后根据各区间的长度比例和幅度比例产生序列模式的候选集,最后定义了一种新的相似性度量来...     

发现模糊状态演化模式

0 引言时间序列(Time Series)是指按时间顺序排列的一组数据。对时序数据进行分析,从中获取生成这些数据的系统的相关信息从而完成对系统的模型构造和对系统的未来的行为做出预测,具有重要的价值和意义。数据挖掘(也称为数据库中的知识发现),是指从数据中提取模式的过程,这些模式是有效的、新颖的、潜在可用的和易于理解的。当前数据挖掘领域对时间序列进行的研究主要限于时间序列的相似性研究,即从同一时序或者不同时序中发现相似模式。对于如何从一个时间序列中提取知识的问题,国内外尚很少见。本文首先从系统论的角度对时间序列问题进行了分析,然后将模糊性引入到时序处理中,提出了从时间序列中进行频繁状态演化模式挖掘的问题,然后论证并给出了其挖掘算法,最后在实际应用中对上述理论进行了分析和验证。     

一种基于多阶畸变子模式相似性学习的序列识别方法

序列识别研究对于诸多应用研究领域有重要的意义。在序列识别中,由于多种因素的影响,同一类别标记的序列往往不具有严格的相似性。变化序列相似性描述的尺度对序列的相似性进行描述有利于获得更准确的序列相似性描述结果,为此提出了基于多阶畸变序列子模式的序列识别方法。通过定义序列多阶畸变子模式特征空间及其核变换函数,设计线性开销算法有效实现了序列畸变子模式高维特征向量的计算,进而利用半定规划对多阶畸变序列子模式的核变换矩阵进行优化。基于多阶畸变子模式相似性描述优化结果,支持向量机生成的识别方法比较好地适应了序列之间的不同程度的相似性畸变,而且具有柔性边界特征。本方法在蛋白质基准数据SCOP 1.37 PDB90上进行了实验,普遍提高了该数据集上33个不同家族蛋白质序列的识别结果。     

一种有效的蛋白质序列聚类分析方法

提出了一种有效的基于仿射传播聚类算法和后处理方法的蛋白质序列聚类方法.在聚类分析蛋白质序列时,为了优化仿射传播聚类算法的聚类结果,采用后处理的方式来提高聚类结果的质量.为了度量蛋白质序列之间的相似度,给出了一种改进的无比对计算方法.在6个蛋白质序列数据集上进行对比实验,实验结果表明,所给出的方法能够有效地分析蛋白质序列.     

多变量时间序列模式挖掘的研究

多变量时间序列数据集合在许多领域中存在,由于其观测变量之间的相互关联性,往往需要进行综合分析.使用基于时间序列相似性的多变量时间序列模式挖掘方法,从历史数据中寻找出相似的多变量时间序列.将多变量的数据集分段平均为连续矩阵,并采用基于主成分分析和奇异值分解的方法来对矩阵进行相似性比较,最后通过相邻片断的合并以组成更高层次的时序片断,以提高模式的匹配的范围.并在地震前兆数据进行了实现.     

时间序列序列模式的相似性研究

时间序列序列模式相似性的度量是从时间序列中获取时序关联规则的重要环节。一般情况下,距离度量法只能度量相同长度序列模式的相似性。借用动态时间弯曲距离的思想,这种基于非线性弯曲技术的算法可以获得很高的识别、匹配精度。在定义元模式相似性的基础上,定义了序列模式的动态时间弯曲距离,最后用两个不同时间序列进行仿真实验,可以得到不同长度的序列的相似度。     

一种寻找最近子串的快速种子集求精算法

寻找序列中的最近子串对挖掘基因中特殊的功能位点和了解基因调控关系有着重要意义。提出了一种新的基于种子集求精的改进的期望最大化算法SCEM来对基因序列中的最近子串进行寻找。通过对输入序列聚类,将数据集分解为若干种子集,再使用改进的期望最大化算法对各种子集进行求精,SCEM最终可寻找到序列中的最近子串。真实数据和模拟数据实验表明,SCEM算法可以寻找到真实的最近子串,与随机投影等流行算法相比也能保证较高的性能和效率,并且可以有效解决较长的最近子串寻找问题。     

基于小波变换的时间序列相似模式匹配

提出了一种新的时序相似模式匹配方法，它采用小波分析的方法实现时间序列数据的降维，采用小波序列表示原序列，将小波序列组织为多维索引结构R-tree存储，在该索引结构基础上，基于一种表示相似性的距离函数，定义了范围查询和最近邻查询算法，实验结果证明这种方法性能优于传统的基于傅立叶变换的相似模式匹配方法。     

带任意长度通配符的模式匹配

基因序列中,许多病毒并不是简单的直接复制自己,而是相邻字符间插入或者删除序列片段,如何从序列数据中检索这些病毒具有重要的研究价值.提出了一个更普遍的问题,带任意长度通配符的模式匹配问题(Pattern matching with arbitrary-length wildcards,PMAW),这里模式中不仅可以有多个通配符约束,而且每个通配符的约束可以是两个整数,也可以从整数到无穷大.给定序列S和带通配符的模式P,目标是从S中检索P的所有出现和每一次出现的匹配位置,并且要求任意两次出现不能共享序列中同一位置.为了有效地解决该问题,设计了两个基于位并行的匹配算法MOTW (Method of ocurrence then window)算法和MWTO (Method of window then ocurrence)算法.同时,MWTO算法进行细微改动就可以满足全局长度约束.实验结果既验证了算法求解问题的正确性,又验证了比相关的模式匹配算法具有更好的时间性能.     

无重复投影数据库扫描的序列模式挖掘算法

序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan.     

一种改进的序贯模式算法在地震学中的应用

结合地震预报的领域知识,面向具体的应用,提出了一种改进的基于滑动时间窗口的序贯模式挖掘算法,用来发现广义的地震序列。与地震学中地震序列研究相比,将数据挖掘的应用拓展到地震预报中,通过序贯模式来研究广义地震序列。实验测试结果表明：该算法能够发现一些有意义的广义的地震序列。     

Multi-sorting algorithm for finding pairs of similar short substrings from large-scale string data

Finding similar substrings/substructures is a central task in analyzing huge string data such as genome sequences, Web documents, log data, feature vectors of pictures, photos, videos, etc. Although the existence of polynomial time algorithms for such problems is trivial since the number of substrings is bounded by the square of their lengths, straightforward algorithms do not work for huge databases because of their high degree order of the computation time. This paper addresses the problem of finding pairs of strings with small Hamming distances from huge databases composed of short strings of a fixed length. Comparison of long strings can be solved by inputting all their substrings of fixed length so that we can find candidates of similar non-short substrings. We focus on the practical efficiency of algorithms, and propose an algorithm that runs in time almost linear in the input/output size. We prove that the computation time of its variant is linear in the database size when the length of the short strings is constant, and computational experiments for genome sequences and Web texts show its practical efficiency. Slight modifications adapt to the edit distance and mismatch tolerance computation. An implementation is available at the author’s homepage.     

改进的序列模式挖掘在医院转诊中的应用

为了研究患者在不同医院间的转诊行为模式, 可以使用序列模式挖掘算法. 类Apriori算法是序列模式挖掘中的常用算法, 但该算法存在一些不足之处, 如产生候选序列的数目较多、需要频繁扫描数据库. 针对类Apriori算法存在的不足, 本文提出了相应的改进措施, 采用新的剪枝策略并减少不必要的数据库扫描操作. 实验证明, 改进后的算法能更高效地挖掘频繁转诊序列.     

Efficient algorithms for the longest common subsequence in k-length substrings

Finding the longest common subsequence in k-length substrings (LCSk) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences A and B are replaced with matching non-overlapping substrings of length k from A and B. We propose several algorithms for LCSk, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length k from one sequence in the other sequence.     

基于后缀树的带有通配符的模式匹配研究

由于在生物序列分析、文本索引、网络入侵检测等领域的应用需求,带有通配符的模式匹配问题一直是研究 的热点。针对已有的研究工作中通配符和长度约束具有较强的局限性问题,研究带有灵活通配符的模式匹配问题,其 中通配符可以在模式的任意两子串间出现且可以指定灵活的长度约束。采用非线性数据结构—后缀树,设计了求 解模式所有解的完备算法PAS"I'。预处理阶段采用在线增量式算法构建具有文本先验知识的后缀树,搜索阶段结合 动态规划的思想,逐个匹配模式中字符,最终得到完备解。在基因序列上的实验表明,PAST比其他算法具有更好的 时间性能。     

一种改进的BM字符串匹配算法

经典字符串匹配算法的本质都是从左向右或者从右向左顺序进行字符匹配的,在主串中存在大量子串与模式串前缀或者后缀相同时效率较低,并且模式串最大右移长度为模式串长度。改进算法采用二分匹配字符串的方法,有效地避免了由主串中大量子串与模式串前缀相同或者后缀相同引起的无意义比较次数。模式串的移动距离根据改进的坏字符规则进行计算,增大了模式串的移动距离。实验结果表明,改进的字符串匹配算法可以有效地减少字符串的匹配次数和移动次数,达到了提高算法效率的目的。