pepReap: 基于支持向量机的肽鉴定算法

利用生物质谱技术进行肽/蛋白质鉴定是蛋白质组学研究中的关键问题. 提出了一种基于支持向量机(SVM)的肽鉴定算法pepReap.算法由粗细两层打分体系构成,粗打分利用匹配谱峰总强度和数目及肽长度等信息得到候选肽序列的列表,细打分通过SVM算法综合利用多项匹配指标如离子相关性、离子匹配误差、肽序列信息等对粗打分结果进行评价,得到更为可靠的肽鉴定结果.在SVM的参数选择过程中,采用马修斯相关系数来评价分类性能以适应不平衡数据集的情况.在公开发表的数据集上的实验表明,该算法与采用阈值评价方法的流行商业软件SEQUEST相比,在鉴定精度相当的情况下可以获得更高的鉴定灵敏度.     

一种新颖的蛋白质序列与其串联质谱的匹配打分算法

为了有效的利用蛋白质串联质谱数据,提高蛋白质鉴定的准确性,提出一种基于KNN的蛋白质序列与蛋白质串联质谱的匹配打分算法.蛋白质序列与蛋白质串联质谱的匹配打分是蛋白质数据库搜索鉴定过程中的关键技术.然而,现有的算法没有很好的利用蛋白质串联质谱中离子的强度信息.针对此问题,本文根据质谱中离子的类型给出了全体离子的一个合理的划分.进而抽象出一个高维的强度特征向量,在已知的高精度的数据集上建立了强度匹配知识集合,最后基于KNN技术构造了序列和质谱的匹配打分算法.实验结果表明,本文算法更加有效的利用了蛋白质串联质谱的结构信息,提高了蛋白质鉴定的准确性.     

基于打分矩阵的生物序列频繁模式挖掘*

从生物序列中发现有意义的频繁模式已经成为生物信息领域研究的重要任务.文中提出基于打分矩阵的生物序列频繁模式挖掘算法.首先构造近似匹配得分矩阵,用于处理带通配符间隔约束的模式匹配问题中插入、替换、删除操作.然后设计基于打分矩阵的近似模匹配方法获取模式在序列中的近似出现次数.最后采用数据驱动模式生成方法和Apriori-like剪枝策略避免产生过多不必要的候选模式.在蛋白质和DNA序列上的实验表明文中算法性能更优,可用于挖掘不同序列的共同频繁模式.     

基于肽序列标签的蛋白质翻译后修饰中的过滤算法

大量的质谱数据无法被鉴定或是鉴定的精度不够高,特别是在肽段数据库较大时,普通的算法精度下降很快。提出一种新的盲搜索算法,此算法基于一种全新的基于相似关系度量的打分模型。为了处理大规模问题,同时还应用了基于母离子质量和肽序列标签的前过滤方法,使得此算法在较大规模的数据库上精度得到很好的保证。实验结果表明,对于规模为10000, 20000, 50000的肽段数据库,其鉴定准确率分别为78.3%,74.2%,65.5%。随着数据库规模的增大,算法的鉴定准确率保持得较好。     

基于抽样路径的K-匿名隐私保护算法

K-匿名是信息隐私保护的一种常用技术,而使用K-匿名技术不可避免会造成发布数据的信息损失,因此,如何提高K-匿名化后数据集的可用性一直以来都是K-匿名隐私保护的研究重点。对此提出了一种基于抽样路径的局域泛化算法——SPOLG算法。该算法基于泛化格寻找信息损失较小的泛化路径,为减少寻径时间,引入等概率抽样的思想,选用等概率抽样中的系统抽样方法进行取样,利用样本代替数据集在泛化格上寻找目标泛化路径,最后在该路径上对数据集进行泛化。同时,本算法使用局域泛化技术,能够降低信息损失量,提高发布数据集的可用性。实验结果证明,本算法匿名化的数据集信息损失度低,数据可用性高。     

CUDA-TP:基于GPU的自顶向下完整蛋白质鉴定并行算法

蛋白质及蛋白质翻译后修饰(post-translational modifications, PTMs)的鉴定是蛋白质组学研究的基础,对整个领域的进一步发展有着十分重要的意义.近年来,质谱设备的快速发展使得获取“自顶向下”(top-down,TD)的高精度完整蛋白质质谱数据成为可能.目前基于TD质谱数据的完整蛋白质鉴定算法虽然在匹配精度、PTM位点的推断上取得了一些成效,但它们运行时间还有很大的不足和提升空间.利用图形处理器(graphics processing unit, GPU)可以将大规模的重复计算并行化,提高串行程序的执行速度.CUDA-TP算法基于通用并行计算架构(compute unified device architecture, CUDA)来计算蛋白质与TD质谱数据的匹配分数.首先,对每一个质谱数据,CUDA-TP利用优化的MS-Filter算法在蛋白质数据库中过滤出其对应的少数候选蛋白质集合,然后通过AVL(adelson-velskii and landis)树加速质谱匹配过程.GPU中的多线程技术被用来并行化谱图网格及最终数组中所有元素的前驱结点的求解.同时,该算法还使用target-decoy策略来控制蛋白质与质谱图匹配结果的错误发现率(false discovery rate, FDR).实验结果表明：CUDA-TP算法能够有效地加速完整蛋白质的鉴定,速度分别比MS-TopDown和MS-Align+快10倍与2倍.到目前为止,这是唯一能够利用CUDA架构来加速完整蛋白质鉴定的研究工作.CUDA-TP源代码公布在https://github.com/dqiong/CUDA-TP.     

多重序列比对的蚁群算法

序列多重比对是生物信息学特别是生物序列分析中的一个重要的操作.提出了一种解决多重序列比对的蚁群算法,利用了人工蚂蚁逐个选择各个序列中的字符进行配对.在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力.实验显示,该算法可以有效解决多重序列比对问题.     

求解多重序列比对问题的蚁群算法

多重序列比对是生物信息学特别是生物序列分析中一个重要的基本操作。提出求解多重序列比对问题的蚁群算法,利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中字符的概率,通过信息素的更新与调节相结合的策略较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力。另外在该算法的基础上,提出了基于分治策略的多序列比对蚁群求解算法,不但减少了原算法的计算时间,而且显著改善了算法所求得的解的质量。     

基于频繁序列挖掘的文件系统缓存算法设计

传统缓存算法存在命中率低、交换率高等问题,且现有缓存算法在分布式大数据存储系统中并不适用,为此提出了一种基于频繁序列挖掘的自适应缓存策略。该方法使用数据挖掘算法挖掘历史访问窗口内的频繁序列,将频繁序列模糊合并后构建匹配模式集合以供查询。当新的访问来临时,将固定访问长度内的子序列与匹配模式集合进行匹配,然后根据匹配结果预取数据,同时结合修改后的S4LRU(4-segmented least recently used)数据结构进行缓存数据换出。在公开的大数据处理trace集上进行了仿真实验,实验结果表明,在不同的缓存大小下,提出算法与现有典型缓存算法相比,平均命中率提高了0.327倍,平均交换率降低了0.33倍,同时具有低开销和高时效的特点。此结果表明,该方法较传统替换算法而言是一个更为有效的缓存策略。     

自适应目标与内容匹配的层级图像分割算法

针对超度量轮廓图(ultrametric contour map,UCM)层级图像分割算法对轮廓适应性弱、层级匹配能力较弱且分割碎片较多等问题,提出了一种自适应目标与内容匹配的改进UCM层级图像分割算法。该算法首先使用"轮廓盒子"提取图像关键轮廓,然后使用加权分水岭算法合并区域,提升轮廓适应性,并产生UCM层级树;随后,采用动态规划的方式自适应完成目标与内容匹配,最后使用调整尺度后的UCM层级树完成图像分割。在BSDS500数据集上进行了分割实验,实验结果表明提出的算法在各项分割指标上获得了显著的提升。分割掩盖率(segment cover,SC)、概率边缘指标(probabilistic region index,PRI)和信息变化率(information variation,IV)三个衡量指标分别在最优数据集尺度(optimal dataset scale,ODS)和最优图像尺度(optimal image scale,OIS)上获得了最佳的效果。UCM层级树通过尺度的调整,能够保证相同尺度的层级分割为同一层,减少了分割碎片,保证了层级匹配。该算法在分割精度上超越了当前大多数主流图像分割算法,同时保证时间复杂度在同一个级别。     

蛋白质数据库中匹配间隙序列标签的自动机算法

对于肽和蛋白质的分析鉴别,串联质谱（MS／MS）是极其重要的方法。解释MS／MS数据的一种方法是de novo序列,它正变得越来越准确和重要了。但de novo序列通常只能准确地判定序列的一部分,而对于不确定的部分只能通过“质量间隙”来表示,我们称这样部分确定的序列为间隙序列标签。对于蛋白质的分析鉴别,当在数据库中查询一个间隙序列标签时,其中确定的部分应与数据库蛋白质序列完全匹配,而对于每一个质量间隙也应匹配一个氨基酸子串,这些氨基酸子串的质量和应与质量间隙的质量和相等。在这种情况之下,标准的串匹配算法已经不再适用。在本文中,我们将提出一个新的且有效的算法,用以在蛋白质数据库中找到与间隙序列标签所匹配的序列。     

An evaluation of multidimensional fingerprinting in the context of clinical proteomics

Multidimensional fingerprinting (MDF) utilizes measurable peptide characteristics to identify proteins. In this study, 3‐D fingerprinting, namely, parent protein molecular weight, peptide mass, and peptide retention time on RPLC, is used to identify 331 differentially expressed proteins between normal and human colon cancer plasma membrane samples. A false discovery rate (FDR) procedure is introduced to evaluate the performance of MDF on the colon cancer dataset. This evaluation establishes a false protein identification rate below 15% for this dataset. Western blot analysis is performed to validate the differential expression of the MDF‐identified protein VDAC1 on the original tissue samples. The limits of MDF are further assessed by a simulation study where key parameters such as database size, query size, and mass accuracy are varied. The results of this simulation study demonstrate that fingerprinting with three dimensions yields low FDR values even for large queries on the complete human proteome without the need for prior peptide sequencing by tandem mass spectrometry. Specifically, when mass accuracy is 10 ppm or lower, full human proteome searches can achieve FDR values of 10% or less.     

Peptide sequencing program

A computer program has been devised to automate rationalization of peptide fragmentation patterns. The program systematically generates all possible linear amino acid sequences which might be attributable to a peptide with a known amino acid composition. The generated sequences are then searched to find those that most closely match the spectrum of an unknown sequence.     

一种基于压缩感知和动态时间规整的信号肽特征提取新算法

准确识别出信号肽对蛋白质的研究和定位有着非常重要的意义。压缩感知技术能够在保留生物序列主要信息的同时降低冗余信息,将高维信息投影到低维空间上进行特征提取。因此本文基于压缩感知技术再结合动态时间规整算法提取出新的特征向量,提出一种高鉴别性的信号肽特征提取新方法。该算法所提取的特征不但体现了信号肽中的氨基酸组成、排列顺序、结构等重要信息,还能把信号肽的不同区域在时间维度中非线性地弯曲对整,为机器学习算法提供有效的信号肽特征表达。实验结果显示,新方法提取的特征向量在3个数据集Eukaryotes, Gram+ bacteria, Gram-bacteria上的识别率分别达到99.65%, 98.05%和98.56%,并且这种方法能简单地运用到其他生物序列的识别过程中。     

双流增强融合网络微表情识别

为解决微表情识别领域数据集样本数量少,样本类型分布不均导致识别率鲁棒性差的问题,提出了一种基于双流增强网络的微表情识别模型。该模型基于单帧RGB图像流及光流图像流的双流卷积神经网络,以权威数据集为基础,数据增强为基准,构建微表情识别模型。通过在SoftMax逻辑回归层融合单帧空域信息和光流时域信息,对两个独立流的网络性能进行提升,并通过引入基于带循环约束的生成对抗网络的图像生成方式对数据集进行扩充。通过将输入微表情视频帧序列进行分解,将其分割为双流网络的灰度单帧序列与光流单帧序列,对两类序列图进行数据增强,再进行微表情识别模型构建的方法,有效提高了微表情识别率。基于双流增强网络的微表情识别模型可以较好提升微表情识别准确度,鲁棒性较好,泛化状态较稳定。     

边缘智能背景下的手写数字识别

随着边缘智能的快速发展,现有手写数字识别卷积网络模型的发展已越来越不适应边缘部署、算力下降的要求,且存在小样本泛化能力较差和网络训练成本较高等问题。借鉴卷积神经网络（CNN）经典结构、Leaky_ReLU算法、dropout算法和遗传算法及自适应和混合池化思想构建了基于LeNet-DL改进网络的手写数字识别模型,分别在大样本数据集MNIST和小样本真实数据集REAL上与LeNet、LeNet+sigmoid、AlexNet等算法进行对比实验。改进网络的大样本识别精度可达99.34%,性能提升约0.83%;小样本识别精度可达78.89%,性能提升约8.34%。实验结果表明,LeNet-DL网络相较于传统CNN在大样本和小样本数据集上的训练成本更低、性能更优且模型泛化能力更强。     

Generalizing predicates with string arguments

The least general generalization (LGG) of strings may cause an over-generalization in the generalization process of the clauses of predicates with string arguments. We propose a specific generalization (SG) for strings to reduce over-generalization. SGs of strings are used in the generalization of a set of strings representing the arguments of a set of positive examples of a predicate with string arguments. In order to create a SG of two strings, first, a unique match sequence between these strings is found. A unique match sequence of two strings consists of similarities and differences to represent similar parts and differing parts between those strings. The differences in the unique match sequence are replaced to create a SG of those strings. In the generalization process, a coverage algorithm based on SGs of strings or learning heuristics based on match sequences are used. Ilyas Cicekli received a Ph.D. in computer science from Syracuse University in 1991. He is currently a professor of the Department of Computer Engineering at Bilkent University. From 2001 till 2003, he was a visiting faculty at University of Central Florida. His current research interests include example-based machine translation, machine learning, natural language processing, and inductive logic programming. Nihan Kesim Cicekli is an Associate Professor of the Department of Computer Engineering at the Middle East Technical University (METU). She graduated in computer engineering at the Middle East Technical University in 1986. She received the MS degree in computer engineering at Bilkent University in 1988; and the PhD degree in computer science at Imperial College in 1993. She was a visiting faculty at University of Central Florida from 2001 till 2003. Her current research interests include multimedia databases, semantic web, web services, data mining, and machine learning.     

注意力机制结合残差收缩网络对遥感图像分类

针对遥感场景图像中背景复杂、类内差异大以及类间相似度高问题所导致的分类效果欠佳情况,提出一种基于有监督对比学习的注意力机制和残差收缩单元算法。首先对有效通道注意力机制（ECA）进行改进,优化对待识别图像特征的提取;然后提出一种协同残差收缩单元算法,利用算法对图像进行冗余信息的筛选消除;再用有监督对比学习算法,增强算法的泛化能力。最后在遥感图像数据集进行实验,并与最新算法如增强注意算法、尺度注意力机制算法进行对比实验。实验表明,该算法在20%训练比例的AID数据集中分类精度提高了1.75%和2.5%。