基于串核的蛋白质分类算法的研究与实现

论文摘要

生物信息学的一个关键问题是理解由染色体中的基因所决定的蛋白质的含义或者功能。对蛋白质进行分类是解决这个问题的有效途径之一。如何提高蛋白质分类的精确性,或在保证精确性不会有较大的降低的前提下,如何提高蛋白质分类算法的计算效率和降低对内存的需求量,一直是生物信息学领域关注的焦点问题之一。本文正是在对经典的蛋白质分类算法研究的基础上,寻求更好的特征映射方法和更快的串核计算方法。基于串核的支持向量机分类器是现今分类效果最好的蛋白质分类器之一,其中,基于谱核的分类器具有速度快,分类效果也比较好的特点。而后改进的不匹配核通过引入不精确匹配思想,在增加了核的计算时间后,取得了更好的分类效果。本文通过对典型的串核,以及基于trie-树的串核计算进行分析,提出了对其在特征映射和计算上的改进方法。本文的主要工作和创新点有:（1）针对串核在特征提取上的不足,本文采用了一类称为样本核的特征提取方法。样本核以训练样本为特征来定义核的特征空间,以串核或其它核为相关的特征映射。所以,样本核以其他的分类核为基础,并可以通过增加先验知识和改变特征空间来改变分类效果。随后,本文针对不同应用下样本核的设计、选取以及计算简要做了分析。（2）在针对串核的计算方法上,本文设计并采用了一种称为剪枝后缀树的数据结构。剪枝后缀树结合了后缀树的后缀链思想以及trie-树在根结点计算核值的方法,具有比后缀树更少的空间以及比trie-树更快的时间。然后,应用剪枝后缀树设计出了针对p-谱核的快速计算方法。（3）针对p-谱核在字符匹配上的不足,结合不匹配核的思想提出了另一种不精确匹配核——模糊谱核。模糊谱核同样加入了不精确匹配的思想,但不同于不匹配核,模糊谱核把不匹配定义在两个样本串上。而在模糊谱核的计算上,同样利用了剪枝后缀树提高了字符匹配的速度。最后,本文设计并实现了一个蛋白质分类模型,并通过该模型对上面几种核进行了测试,通过测试实验表明,样本核在对串核的分类效果上有明显的改善,而剪枝后缀树也大大提高了串核计算的速度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究的背景和意义
• 1.1.1 生物信息学
• 1.1.2 蛋白质结构分类
• 1.1.3 蛋白质分类算法
• 1.2 本文的研究内容
• 第2章 基于串核的支持向量机分类
• 2.1 引言
• 2.2 支持向量机
• 2.3 串核及其特征映射
• 2.3.1 序列空间映射
• 2.3.2 典型的串核及其定义
• 2.4 基于Trie-树的串核计算
• 2.4.1 基于trie-树的谱核计算
• 2.4.2 基于trie-树的不匹配谱核计算
• 2.5 本章小结
• 第3章 基于剪枝后缀树的核计算及样本核
• 3.1 引言
• 3.2 样本核
• 3.3 p-样本谱核及其计算
• 3.3.1 剪枝后缀树设计
• 3.3.2 P-谱核的计算
• 3.3.3 算法复杂度分析
• 3.4 模糊谱核和样本模糊谱核
• 3.4.1 （p,m）-模糊谱核
• 3.4.2 （p,m）-模糊谱核计算方法
• 3.4.3 （p,m）-样本模糊谱核
• 3.5 本章小结
• 第4章 蛋白质分类模型设计及实验分析
• 4.1 蛋白质分类模型设计
• 4.1.1 结构设计
• 4.1.2 系统功能
• 4.2 实验结果与分析
• 4.2.1 运行时间分析
• 4.2.2 分类效果分析
• 4.3 本章小结
• 结论
• 参考文献
• 致谢