一种可用于生物序列分析的轻量级索引结构

针对目前可用于重复片断查询的索引结构所需空间过大的问题,通过对序列中重复片断的分析提出一种轻量级数据结构———后继数组,它是基于基数排序方法建立的.后继数组也适用于多序列分析.理论分析表明了后继数组及多序列后继数组在存储空间上的优势.实验结果表明后继数组仅需要约原序列长度5倍的存储空间,在建立时间上后继数组也要优于后缀树等索引结构.     

基于相对编辑相似度的近似重复视频检索和定位

为有效对近似重复视频进行检索和定位,提出了一种基于相对编辑相似度的检索和定位算法.算法包括基于局部特征的视频编码和基于相对编辑相似度的在线检索和定位两部分.基于局部特征的视频编码首先提取数据库视频的关键帧,然后在关键帧中提取Root-SIFT特征描述符并应用层次K-Means聚类算法构建词典,之后将关键帧量化至词袋模型的单词并编码.基于相对编辑相似度的在线检索和定位首先对查询视频进行编码,然后应用相对编辑相似度算法,筛选近似重复视频并对近似重复片段进行定位.实验结果表明,LD算法比Yeh等提出的算法在平均F₁评价准则上效果要高8.55%,并且NDCR降低为原来的29%,效果提升明显.      

基于高分片段对的双序列比对分治算法SPDCA

针对传统双序列比对算法的高时空复杂性,在动态规划比对算法的基础上,引入了片段对和分治思想,提出了一个新型的基于高分片段对的分治算法.模拟结果表明:该算法在降低了双序列比对算法的时空需求的同时,还能发现双序列之间微弱的相似关系,可适用于序列数据库相似性的搜索.     

一种基于内容相似性的重复视频片段检测方法

针对互联网视频内容的复杂性,选择能够表征视频内容的特征,首先通过LSH哈希算法对特征进行索引,并由此确定视频之间的帧匹配序列,然后对于计算出的帧匹配序列,采用随机抽样一致性算法进行拟合,从而得到有效的帧匹配序列.视频之间的相似度依据有效帧匹配序列的相似度计算,由相似度进行互联网视频片段的消重.实验表明,对于大量内容相似的互联网视频片段,该方法能较好地描述相似性,并能有效提高检测准确率.     

基于GPU的大规模基因片段并行匹配的方法

后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20%~30%.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.     

中文短文本语法语义相似度算法

通过分析中文短文本的特征,提出了一种基于语法语义的短文本相似度算法.该算法结合中文语句语义的相似性以及语句语法的相似性,即计算具有相同句法结构的短文本的相似度以及考虑语句词组顺序对相似度的贡献,对中文短文本相似度进行计算.实验表明,本文提出的算法在中文短文本相似度计算结果上更加接近人们的主观判断并且拥有比较好的精确率与召回率.     

有效的XML检索结果的相似性度量

相似性度量是聚类等问题中的核心问题.本文研究了XML检索结果的相似性度量,提出了一种新的结构的和内容的XML检索结果相似性度量.首先,在结构方面,提出了两个结构相似性度量:纵向结构相似度和横向结构相似度,它们基于不同的特征集,体现了结构的不同方面的相似度.在内容方面,提出用带有结构的内容模型来描述内容,基于这一内容模型提出了内容相似度.最后进行了实验,在实际数据集和合成数据集上的实验结果都显示,结构相似度和内容相似度都具有很好的准确性.     

面向报警根源分析的历史相似数据段查找

当工业现场发生报警时,操作员需要快速找到报警根源,从而采取正确的措施消除报警。为了更好地帮助操作员进行报警根源分析,提出一种多变量的历史相似数据段查找方法。首先,改进一种单变量相似数据段查找算法,消除其在查找相似数据段时存在的误差;然后,提出一种新的基于距离分布来确定时间窗口宽度的方法,用来定义被查找数据段的时长;最后,对多变量历史数据进行相似性查找,并对数据段的相似程度进行排序。通过TE(Tennessee Eastman)过程的仿真实验,验证了该方法相对于传统算法具有更好的有效性和快速性。     

基于重叠信息的基因组测序短片段定位算法

提出了一种新的测序短片段定位算法Umap,算法引入核心片段逐步扩展延伸的基本思想,通过短片段间的重叠信息定位短片段.首先找出所有在参考基因组上只出现一次的短片段,称为唯一短片段.然后以唯一短片段为基础,利用短片段间的重叠信息,使用贪婪算法对唯一短片段进行扩展,进而确定其他非唯一短片段的准确位置.实验表明,该算法对短片段...     

基于文本相似性匹配的计算机辅助翻译软件研究

提出并实现了一个基于文本相似性查找的计算机辅助翻译软件的解决方案。采用文本相似度算法较好的实现了检索的匹配程度,并运用云计算和并行运行等方法提高响应速度。通过典型案例应用对计算机辅助翻译软件进行了匹配度与响应速度测试,测试结果表明该方案实现的计算机辅助翻译软件查准率与响应速度完全满足用户需求。     

二进制粒在旱涝序列相似性匹配中的应用

通过采用二进制数表示旱涝事件序列中的事件,描述了基于二进制信息粒的运算及二进制粒事件序列相似性匹配的相关定义,提出了基于二进制粒事件序列上的多层次全序列匹配算法及相关定义;经实验验证分析,说明了研究的有效性,为研究地域气候相似和局地小气候相似提供了新方法。     

基于拼音索引的中文模糊匹配算法

主流商业搜索引擎主要基于关键词精确匹配技术。为提高在用户的输入错误时的检索效率,提出了有索引的汉语模糊匹配算法。该算法采用汉字、拼音和拼音改良的编辑距离这3种汉字相似程度的不同度量方式,对用户查询进行扩展,将模糊匹配转化为多个精确匹配,对精确匹配的结果按与查询串的相似程度进行排序。在实验中,将该方法应用于网页文本语料库中。在使用基于拼音改良的编辑距离度量方式时,在时间和空间复杂度增长不大的情况下,该方法取得了60.42%的准确率与50.41%召回率。     

采用填充字符的频繁序列模式挖掘算法

具有固定通配符间隔的频繁序列模式挖掘算法应具有删属性,从而保证在实际应用中能挖掘出有意义的长模式．而原有的问题定义集合存在一定的不足阻碍了该属性的实现．通过引入填充字符改变部分问题定义,解决原定义引起的一些极端性问题,并在模式挖掘过程中保证了完整性和有效性．将基于新定义集合提出的硒孙l算法与基于原定义集合的MMP算法分别在DNA序列上进行实验,结果表明算法实现了Apfiofi属性．     

一种新的高效大型音乐数据库查询算法

在基于哼唱的音乐信息检索领域中，查询处理算法一直是一个重要的研究课题。根据人对乐曲相似理解的实验结果，设计了新的基于单侧连续匹配的可容错的近似匹配的算法．此算法采用n—gram的顺序hash索引，加快了可容错的查询处理速度．还设计了一系列包括各种类型和各种数量错误的查询的实验，来比较该算法和其他两种常用算法的查询处理速度和容错能力．当测试数据集为78000首网上收集的MIDI乐曲段，包含各种错误的查询为1000个时，该算法取得79％的前3位命中率和87％的前10位命中率．这些结果表明，该方法的性能高于现有的算法．表2，参8。     

基于两点的时间序列相似性研究

目前,时间序列相似性判定大多采用欧式距离和动态时间弯曲DTW（DynamicTimeWar．ping）方法,这两种方法均存在一定缺陷。欧式距离要求序列长度一样,垂直移动序列将影响相似性判定和阈值设置的经验性;动态弯曲距离对欧式距离进行了优化,避免了欧式长度的一致性,但其他两个缺点仍然存在且计算复杂度增加。提出了一种新的基于两点时间序列相似性算法,可计算任意两序列的相似度。首先分析了两点组成的序列形态,提出了相似性判定方法TPSS（TwoPointsSegmentationSimilarity）;其次为提高相似性判定的鲁棒性,减少人为阈值设置的影响,对TPSS进行了拓展;最后给出了算法及实验分析。实验结果表明,该算法能很好地判定任意序列的相似性,提高了鲁棒性及减少人为干预,对数据挖掘中的聚类与预测有很好的帮助作用。     

一类新的混合变分不等式

研究了一类新的混合变分不等式,建立了其解的一个存在性定理,构造了一个寻求其近似解的带有误差的算法,证明了近似解序列强收敛于一个精确解．所得结果推广和改进了Ｄｉｎｇ,Ｎｏｏｒ,Ｈｕａｎｇ,Ｚｈａｎｇ等人的最新结果     

一种新的相似度标准及其相关的聚类算法

分析了CHAMELEON聚类算法的不足,定义一种基于k最临近集和共享k最临近集的相似度函数,在此基础上提出了一种结合分类算法的新聚类算法,经过对模拟的复杂数据组和KDD Cup'99网络非法入侵数据的实验,证明该算法能有效的对由大量噪音和不同形状、大小及密度的类组成的高维数据进行聚类.     

A measure of semantic similarity between gene ontology terms based on semantic pathway covering

Semantic similarity between Gene Ontology (GO) terms is critical in resolving semantic heterogeneousness when integrating heterogeneous biological databases. Traditionally, distance based and information content based measures are two major methods. In this paper, a new method based on semantic pathway covering is proposed and an algorithm, COMBINE algorithm, is presented, which considers information contents of two given nodes and those of all nodes included in the two nodes’ pathways. Experiments show that COMBINE algorithm obtains the highest correlation index compared with those distance based and information content based algorithms.     

基于杂草算法的DNA编码序列研究

在DNA自组装过程中,DNA序列的设计是影响DNA组装在可靠性和稳定性问题上的重要因素。为降低DNA组装时出现碱基错误匹配的概率,提出了一种用于DNA序列设计的入侵杂草优化(IWO)算法。采用汉明距离约束、相似度约束、连续性约束、发卡结构约束及解链温度约束建立一个多目标函数优化的数学模型,将DNA序列集设计问题抽象为带有约束条件的多目标优化问题。通过将该算法产生的编码序列和其它两种优化算法产生的序列进行对比分析,证实了该算法的有效性,并拓展了算法在离散空间中的应用。