串联质谱谱库搜索鉴定技术综述

介绍蛋白质质谱鉴定领域的串联质谱谱库搜索技术,分析谱库搜索技术的基本原理,从多个角度阐述当前主流的谱库搜索方法,并对其优缺点进行比较,针对目前蛋白质质谱鉴定技术所存在的优缺点,设计其改进思路,论述目前谱库搜索技术所面临的问题以及未来的研究趋势。     

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.     

面向FPGA的RNA二级结构预测并行算法研究

动态规划是RNA二级结构预测最主要的算法,文中提出一种对动态规划矩阵采用分块技术的细粒度并行算法,通过对数据依赖关系的分析,引入了流水的策略,提高了算法的效率,在时钟模拟器上验证了算法的正确性,获得了一系列关于并行加速比、空泡率、存储访问带宽等问题的模拟结果,确定了FPGAPE阵列设计中的基本参数,为FPGA成功实现奠定了基础。     

基于特征比对算法的蛋白质质谱鉴定仿真

为了满足质谱鉴定领域的高通量、高准确度的需求,传统的人工鉴定方法不理想,准确性差.为了提高定量精度,提出了利用计算机仿真手段,实现蛋白质质谱快速准确性鉴定.根据分析蛋白质质谱鉴定原理,建立有关模型,然后采用特征比对的方法,对质谱数据进行特征提取和比对分析,设计适合于蛋白质质谱鉴定的特征比对算法,并进行鉴定仿真.仿真结果表明,利用特征比对质谱鉴定方法在鉴定速度及鉴定准确度方面优于传统的方法,验证了使用特征比对方法对蛋白质质谱鉴定的有效性,并为蛋白质鉴定系统优化设计研究提供参考.     

正则表达式分组的1/(1-1/k)-近似算法

对正则表达式集合进行分组是解决DFA状态膨胀问题的一种重要方法.已有的分组算法大都是启发式的或蛮力的,分组效果很差.分析了DFA状态膨胀的原因,总结了某些正则表达式间的冲突状况.证明了当冲突非负和冲突独立时,正则表达式集合的最优k分组问题可归结为最大k割问题,从而说明该问题是NP-Hard的.基于局部搜索的思想,提出了一种分组算法GRELS来解决分组问题,并证明对最大k割问题,该算法的近似比是1/(1-1/k)与已有的分组算法相比,当分组数目相同时,GRELS算法分组结果的状态总数最少,并且集合发生变化时所需的更新时间最短.     

文本的图表示初探

文本表示是文本信息处理中的基础问题,以向量空间模型(VSM) 为代表的多数文本表示模型没有考虑文本中特征项之间的序关系,这样的表示造成文本语义信息的损失。我们尝试在文本表示中引入序关系,用图结构来表示文本,提出了一种新的文本表示模型—图表示模型,并对该模型的表示效果进行了验证。实验结果表明目前我们的表示模型仍达不到VSM模型所取得的表示效果。本文总结了文本表示过程,提出了一种新颖的用于度量文本表示模型表示能力的方法,同时也提出了一系列与文本图表示相关的值得探讨的问题。     

一种针对名义尺度变量的优化聚类算法

经典的聚类分析技术如系统聚类法和K-means等主要是处理间隔尺度的变量，而对于名义尺度变量则不适合。文章借鉴认知心理学和优化学习的思想，对名义尺度变量的聚类问题进行了研究，定义了名义尺度变量的距离度量——翻转距离，在此基础上，提出了一种目标函数优化制导的聚类算法，并演示了对名义尺度变量进行聚类的过程。实验表明，我们的算法结果可以得到合理的解释。     

蛋白质中残基远程相互作用预测算法研究综述

蛋白质是由多个氨基酸残基顺序连接而成的长链.在天然状态下,蛋白质并不是无规则的自由状态,而是自发形成特定的空间结构,以执行其特定的生物学功能.驱动蛋白质形成特定空间结构的主要因素是残基间的非共价相互作用,包括疏水作用、静电相互作用、范德华力等.因此,对残基之间远程相互作用的准确预测将有助于对蛋白质空间结构的预测,进而有助于对蛋白质生物学功能的了解.在蛋白质进化过程,有相互作用残基对之间存在一种“共进化”模式,即当一个残基发生变异时,与其有相互作用的残基也要发生相应的变异,以维持相互作用,进而维持整体空间结构以及生物学功能.基于上述生物学观察,研究者开发了多个统计模型和算法以预测残基对之间的相互作用:1)概述残基之间远程相互作用的两大类基本预测算法,包括无监督学习方法和监督学习方法;2)使用蛋白质结构预测CASP比赛结果来客观比较上述各类算法的性能,分析各个算法的特点和优势;3)从生物学观察和统计模型2个角度分析总结了未来的发展趋势.     

聚类/分类中的粒度原理

从信息粒度的角度来剖析聚类和分类技术，试图使用信息信息粒度原理的框架来统一聚类和分类，从信息粒度的观点来看，聚类是在一个统一的粒度下进行计算，而分类却是在不同的粒度下进行计算，该文还根据粒度原理设计了一个种崭新的分类算法，在大规模中文文本分类的应用实践表明这种分类算法有较强的泛化能力。     

2-3-SAT问题相变现象剖析及其应用

3-SAT问题有一个非常奇妙的相变现象.对于固定的变量数N，合取范式的可满足概率随着子句个数K的变化而发生剧烈的变化;当K≈4.3*N 时,可满足概率急剧地从1变为0.相变现象决定了问题的难易分布,对于快速求解算法的设计有着非常重要的意义.文章着重讨论了SAT问题的更一般形式，即2-3-SAT问题的相变现象.研究了相变点处的2-子句和3-子句个数的关系，发现了2-子句和3-子句在约束能力意义下的当量关系，并提出了如何有效地利用2-3-SAT的相变现象.