论文摘要
Lempel-Ziv（LZ）复杂性是符号序列的根本属性之一。经过适当的粗粒化和符号化,生物大分子（DNA、RNA、蛋白质等）也可表示成一维符号序列的形式。通过对生物序列的LZ复杂性及其它相关特性进行分析、比较,可以为解决近年来生物信息学领域许多基于序列分析的重要问题提供新的计算方法和研究途径。论文首先研究了LZ复杂性的概念和基本性质,在此基础上提出符号序列最长后缀前缀（LSP）划分的概念,证明了LSP划分与LZ复杂性定义中完备生成划分的等价性。提出了通过非空符号序列的LSP划分来进行LZ复杂性计算的LSP-LZC算法。采用基于带后缀链接的后缀树构造算法作为主要的计算步骤,算法LSP-LZC总的计算复杂度为线性时间和线性空间,在时间效率上优于现有的LZ复杂性算法。LZ复杂性是单个符号序列的数值属性。为了刻画不同序列间的LZ复杂性关系,论文提出了条件LZ复杂性的概念。基于条件LZ复杂性,进一步提出度量序列间相似关系的LZ复杂性相似度,证明了LZ复杂性相似度满足相似性测度的正定、自反和对称等性质。论文将LZ复杂性相似度应用于分子系统进化树重构的研究中。分别以线粒体全基因组和病毒全基因组DNA序列作为计算数据,基于LZ复杂性相似度对29种有胎盘哺乳动物和SARS冠状病毒进行系统进化树的重构,都得到了具有合理生物学意义的结果。基于LZ复杂性相似度,论文提出了相似度矩阵特征变换的概念和LZ复杂性核及核矩阵的构造方法。证明了LZ复杂性核的正定性和LZ相似关系不变性。给出了基于LZ复杂性核的支持向量机模型在符号序列的模式分析中进行学习和预测的方法。利用上述方法,可以实现基于一级序列数据的蛋白质亚细胞位点类型的机器预测。在真实的分别由部分真核生物和原核生物组成的两个标准数据集上进行预测实验,都取得了良好的效果。论文还提出了基于蛋白质接触图间的LZ复杂性分析进行蛋白质三维结构比较的方法。因为蛋白质的三维结构数据不能表示成符号序列的形式,论文通过计算蛋白质三维结构的接触图,并计算蛋白质对应接触图间的LZ复杂性相似度来度量不同结构之间的相似性,间接实现蛋白质三维结构的比较。论文分别在由真实蛋白质结构数据组成的Chew-Kedem数据集和从SCOP蛋白质结构分类数据库中构造的4个结构超家族数据集上对论文所提出的方法进行结构比较的实验,都取得了理想的结果。
论文目录
摘要ABSTRACT第1章 绪论1.1 论文研究背景1.1.1 生物信息学1.1.2 生物序列的复杂性1.2 生物序列的LZ复杂性1.2.1 生物序列的粗粒化与符号化1.2.2 符号序列的LZ复杂性1.3 论文研究的主要内容1.4 论文的组织结构第2章 基于最长后缀前缀划分的LZ复杂性算法2.1 国内外LZ复杂性算法研究现状2.2 符号序列LZ复杂性的LSP-LZC算法2.2.1 符号序列的最长后缀前缀（LSP）划分2.2.2 LSP-LZC算法2.2.3 基于后缀树构造的STC-LSPsA算法2.3 计算复杂度分析2.3.1 时间复杂度2.3.2 空间复杂度2.4 实验比较2.4.1 实验环境2.4.2 实验结果2.5 小结第3章 基于LZ复杂性相似度的系统进化树重构3.1 引言3.1.1 系统进化与系统进化树3.1.2 国内外研究现状3.2 条件LZ复杂性3.2.1 条件LZ复杂性概念3.2.2 符号序列的CLSP划分3.2.3 条件LZ复杂性的CP-CLZC算法3.3 符号序列的LZ复杂性相似度3.3.1 条件LZ复杂性与序列相似性3.3.2 LZ复杂性相似度3.3.3 LZ复杂性相似度的实验分析3.4 基因组分子系统进化树的重构3.4.1 有胎盘哺乳动物的系统进化树重构3.4.2 SARS冠状病毒的系统进化树重构3.5 小结第4章 基于LZ复杂性核的蛋白质亚细胞位点类型预测4.1 引言4.1.1 蛋白质亚细胞位点类型及其预测4.1.2 国内外研究现状4.2 符号序列的LZ复杂性核4.2.1 基本概念4.2.2 构造LZ复杂性核矩阵4.2.3 基于LZ复杂性核的模式分析4.3 实验比较4.3.1 数据集4.3.2 评价指标与检验方式4.3.3 实验结果4.4 小结第5章 基于接触图间LZ复杂性分析的蛋白质三维结构比较5.1 引言5.1.1 蛋白质结构层次及三维结构比较5.1.2 国内外研究现状5.2 蛋白质三维结构接触图5.2.1 三维结构接触图5.2.2 三维结构接触图的空间信息5.3 基于接触图间LZ复杂性分析的蛋白质三维结构比较5.4 实验分析5.4.1 Chew-Kedem数据集上的实验5.4.2 SCOP数据库中4个数据集上的实验5.5 小结第6章 总结与展望6.1 工作总结6.2 研究展望参考文献致谢攻读学位期间发表论文情况
相关论文文献
标签：复杂性算法论文; 相似度论文; 核与核矩阵论文; 蛋白质论文;
