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

《基于串核的蛋白质分类算法的研究与实现论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、工学硕士学位论文基于串核的蛋白质分类算法的研究与实现唐德昌哈尔滨工业大学2008年6月国内图书分类号：TP301.6国际图书分类号：681.3.06工学硕士学位论文基于串核的蛋白质分类算法的研究与实现硕士研究生：唐德昌导师：张岩副教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2008年6月授予学位单位：哈尔滨工业大学ClassifiedIndex：TP301.6U.D.C.:681.3.06DissertationfortheMasterDegreeofEngineeringTHERESEARCHANDIMPLEMENTATIONOFPRO

2、TEINCLASSIFICATIONALGORITHMONTHEBASICOFSTRINGKERNELCandidate：TangDechangSupervisor:AssociateProf.ZhangYanAcademicDegreeAppliedfor：MasterofEngineeringSpecialty：ComputerScienceandTechnologyAffiliation:SchoolofComputerScienceandTechnologyDateofDefence：June,2008University：HarbinInstituteofTechnolog

3、y哈尔滨工业大学工学硕士学位论文摘要生物信息学的一个关键问题是理解由染色体中的基因所决定的蛋白质的含义或者功能。对蛋白质进行分类是解决这个问题的有效途径之一。如何提高蛋白质分类的精确性，或在保证精确性不会有较大的降低的前提下，如何提高蛋白质分类算法的计算效率和降低对内存的需求量，一直是生物信息学领域关注的焦点问题之一。本文正是在对经典的蛋白质分类算法研究的基础上，寻求更好的特征映射方法和更快的串核计算方法。基于串核的支持向量机分类器是现今分类效果最好的蛋白质分类器之一，其中，基于谱核的分类器具有速度快，分类效果也比较好的特点。而后改进的不匹配核通过引入不精确匹配思想，在增加了核的计算

4、时间后，取得了更好的分类效果。本文通过对典型的串核，以及基于trie-树的串核计算进行分析，提出了对其在特征映射和计算上的改进方法。本文的主要工作和创新点有：（1）针对串核在特征提取上的不足，本文采用了一类称为样本核的特征提取方法。样本核以训练样本为特征来定义核的特征空间，以串核或其它核为相关的特征映射。所以，样本核以其他的分类核为基础，并可以通过增加先验知识和改变特征空间来改变分类效果。随后，本文针对不同应用下样本核的设计、选取以及计算简要做了分析。（2）在针对串核的计算方法上，本文设计并采用了一种称为剪枝后缀树的数据结构。剪枝后缀树结合了后缀树的后缀链思想以及trie-树在根结点

5、计算核值的方法，具有比后缀树更少的空间以及比trie-树更快的时间。然后，应用剪枝后缀树设计出了针对p-谱核的快速计算方法。（3）针对p-谱核在字符匹配上的不足，结合不匹配核的思想提出了另一种不精确匹配核——模糊谱核。模糊谱核同样加入了不精确匹配的思想，但不同于不匹配核，模糊谱核把不匹配定义在两个样本串上。而在模糊谱核的计算上，同样利用了剪枝后缀树提高了字符匹配的速度。最后，本文设计并实现了一个蛋白质分类模型，并通过该模型对上面几种核进行了测试，通过测试实验表明，样本核在对串核的分类效果上有明显的改善，而剪枝后缀树也大大提高了串核计算的速度。关键词蛋白质结构分类；串核；谱核；后缀树-

6、I-哈尔滨工业大学工学硕士学位论文AbstractAnimportantresearchtopicinbioinformaticsistounderstandthemeaningandfunctionofeachproteinencodedintothegenome.Oneofthemostsuccessfulapproachestothisproblemisviaproteinclassification.Ithasforlongplayedacentralroleonhowtoimproveresultsoftheclassification,orimprovethecomput

7、ingefficiencyandreducingthememoryrequirementontheconditionthattheresultswillnotbereducedtoomuch.Forcingonthisproblem,weseektogetthebetterfeaturemapandthefastercomputingmeansonthebasicoftheresearchtotheproteinclassificationalgorith