论文部分内容阅读
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个结构超家族数据集上对论文所提出的方法进行结构比较的实验,都取得了理想的结果。