一种带约束最长公共子序列快速算法

来源 :第三届中国数据挖掘学术会议(CCDM2009) | 被引量 : 0次 | 上传用户：cfsjy4

【摘要】

：

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为0(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2)。我们运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键

【作者】

：

业宁朱大铭张倩倩

【机构】

：

山东大学计算机科学与技术学院,济南,250061;南京林业大学信息科学技术学院,南京,210037

【出处】

：

第三届中国数据挖掘学术会议(CCDM2009)

【发表日期】

：

2009年1期

【关键词】

：

带约束最长公共子序列快速算法对偶算法

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

其他文献

基于词相似性与CRP的隐主题模型

主题模型(latent topic model)用于提取隐含在文档集中的主题，其中每个主题是语义相关的一些词的多项式分布。主题模型不但可以发现隐含在文档中的语义信息，而且能够按照主题的规模实现文档的维度约简。本文对主题模型的产生背景、研究现状、研究方法以及存在的问题做了较详细的阐述，在此基础上，提出了一种结合词相似性与CRP(Chinese Restaurant Process)的隐主题模型，该模

会议

LDACRP词相似性Dirichlet分布中医临床数据

简约支持向量聚类

针对传统支持向量聚类(Support Vector Clustering.SVC)的高耗费和低性能弊端,提出了简约支持向量聚类算法(Reduced Support Vector Clustering.RSVC).RSVC的核心是简约策略和新的簇划分方法.前者提取对模型生成有重要意义的数据构成简约子集,并在此子集之上完成优化过程.后者根据核函数特征空间的几何性质完成数据类别的指定.相关几何性质也给予

会议

支持向量聚类简约策略薛定谔方程新的簇划分方法特征空间几何性质

基于SVM的慢性胃炎脾虚证差异表达基因识别研究

利用基因表达谱建立分类模型，找出决定样本类别的一组特征基因是建立有效分类模型的关键.本文对慢性浅表性胃炎脾虚证与正常人、慢性浅表性胃炎脾虚证与脾胃湿热证两组胃肠粘膜配对样本的基因表达谱进行分析.在特征提取阶段分别利用Wilcoxon符号秩检验、组间和组内平方和比率(BSS/WSS)，对两组数据分别进行筛选，据此选出特征基因分别为17个和50个，最后基于相关距离的冗余分析方法过滤冗余基因，分别得到9

会议

脾虚证基因表达谱特征提取SVM

基于不对称贝叶斯学习的图像检索相关反馈算法研究

基于Bayesian理论的相关反馈技术是可有效提高图像检索性能的重要手段之一。然而,当前大多数的Bayesian反馈算法普遍受到小样本问题和训练样本不对称问题的制约。本文提出一种新的相关反馈算法,该算法将查询点移动(Query Point Movement,QPM)技术嵌入Bayesian框架中,并采用不对称的学习策略处理正、负反馈信息,故而称之为不对称Bayesian学习(Asymmetry B

会议

图像检索相关反馈不对称学习贝叶斯

基于相关性的多类分类器设计

典型相关分析(CCA)的目的是通过最大化两组数据间的相关性来抽取典型成分获得降维特征,供其后的分类学习和识别.因此CCA通常仅作为分类学习的特征预处理工具,独立于其后的分类器设计.如此提取的特征未必能保证对分类有利,因而不可避免地会影响分类器的性能.针对此不足,借助正则单纯形的几何特性设计类标号,并分别将其与输入样本作为适合相关处理的两组数据,通过直接最大化样本与其类标号间的个体相关性,设计出一个

会议

典型相关分析个体相关类标号编码分类器设计特征提取经验核映射

一种基于闭项集的无冗余关联规则挖掘方法

针对关联规则挖掘中存在的规则数量过多，难于理解和应用的问题，提出了一种基于闭项集的无冗余关联规则挖掘算法。首先，给出了无冗余关联规则的定义，并基于规则信任度的概念说明了该定义的合理性；其次，在生成子、闭项集和无冗余关联规则的基础上，给出了无冗余最小——最大精确规则基和无冗余最小——最大近似规则基的定义，并讨论了它们的剪枝策略。最后，论证了生成子的性质及其连接策略，并在包含索引的基础上，给出了一种宽

会议

数据挖掘无冗余关联规则生成子闭项集包含索引

基于相容关系集值粗糙集模型的近似集增量更新方法研究

集值信息系统可以用来表示不完备信息系统，得到了广泛地应用。本文分析了现有集值信息系统中的相容关系和拟序关系及其相应的近似集合和相关性质，给出了在相容关系和拟序关系下集值粗糙集模型的近似集增量更新方法。实例验证了方法的有效性。

会议

集值信息系统相容关系拟序关系增量更新

一种改进的制图数据模糊分级处理模型

通过对传统的制图数据分级方法进行分析研究，同时考虑现实分级问题中的模糊性，提出一种改进的制图数据分级方法——基于模糊统计分析模型的制图数据分级处理方法。首先，通过专家系统获取各模糊样本集，利用统计分析方法求得样本分布函数；然后，利用分布函数获得模糊隶属函数，通过隶属函数求取各模糊集的最模糊点；最后根据最模糊点获得各模糊集的区域划分，从而实现对制图数据的分级处理。该方法解决了传统的制图数据分级方法中

会议

模糊集隶属函数最模糊点制图数据分级处理统计分析P-P概率图

基于POMDP的网络入侵意图识别研究

入侵检测作为一种主动的信息安全保障措施，已成为计算机安全特别是网络安全领域的研究热点。将人工智能技术、机器学习技术引入入侵检测领域，以解决入侵日益分布化、智能化的问题，已经成为工业界和学术界关注的课题。本文将对手思维建模技术和计划识别思想引入入侵检测中来。针对入侵者和入侵环境存在的许多不确定性，本文引入部分可观测马尔可夫决策过程(POMDP)作为在环境状态和行动效果都不确定的条件下，通过一系列决策

会议

复合攻击攻击模式场景构建攻击路径图

大脑胶质瘤诊断中不均衡问题上的特征选择

The degree of malignancy in brain glioma dominates the way of treatment and is critical before brain surgery.Many learning methods are used like rule induction algorithm, single neural networks, suppo

会议

feature selectionimbalanced data setsensemble learningmutual informationdies

一种带约束最长公共子序列快速算法

与本文相关的学术论文