高阶马尔科夫模型在生物发育树重建和模体发现中的应用

摘要

传统的生物序列分析方法是建立在序列比对基础之上。而序列比对有其自身的局限：核酸和氨基酸替换矩阵选择没有统一的标准；对分化程度很高的序列比如基因调控序列的比对失效；由于时间消耗量大，针对新一代测序技术产生的海量数据，基于序列比对的方法已不切实际。因此在后基因组时代，生物序列分析急需更快速高效的非比对方法。马尔科夫模型是刻画随机过程的重要模型，在生物序列分析的应用有很长的历史。比如，CpG岛识别和基因发现的很多经典方法都使用了马尔科夫模型。但过去往往是利用低阶马尔科夫模型，本文将讨论高阶马尔科夫模型在生物序列分析中的应用。主要工作如下：
　　1.马尔科夫香农熵最大化（MME)定阶法。马尔科夫模型在生物序列分析中的应用很广，但是对其阶的识别问题关注较少，一般用x2统计量推断或者用AIC/BIC信息标准方法识别。针对生物序列比较问题，如果利用高阶马尔科夫模型，则希望序列的信息尽可能多的被表征出来。本文我们首次提出了马尔科夫香农熵最大化（MME)的定阶方法。多个数据集的测试表明这种方法识别的阶比AIC/BIC信息标准法识别的阶高，并且在生物序列比较方面有明显优势。
　　2.一维混沌游戏表示。Jeffrey提出的基于函数迭代的D N A序列的混沌游戏表示是一种一对一的二维图形表示方法，它将DNA序列转换成二维平面中的单位正方形区域的点集，由此将序列中不同长度的多聚体的频率特异性表现为散点图的不同区域的疏密特异性，还能将多聚体的不同层次的组合偏好性体现为散点图的分形特征。因此DNA序列的混沌游戏表示被广泛应用于DNA序列的特征描述。但是Jeffrey的混沌游戏是为DNA序列量身定做的表示方法，至多只能处理定义在包含k2个字符的集合上的序列。一维混沌游戏表示是基于类似函数迭代的一种一对一的数值表示方法，是将定义于任何有限字符集的符号序列映射为一维数轴上单位区间的数值序列，不仅可以处理DNA序列和RNA序列，还可以应用于包含20种氨基酸的蛋白质序列，甚至包含26个字母的英文文本序列。除了可视化效果，一维混沌游戏表示继承了Jeffrey的混沌游戏的其它所有特征。我们首次提出了一维混沌游戏表示的反演公式和用于生物序列k-串表示的结构指数，并讨论了一维混沌游戏表示与高阶马尔科夫模型的关系。应用高阶马尔科夫模型的两个关键问题是阶的识别和大规模参数的估计。一维混沌游戏表示的这些性质有助于高阶马尔科夫模型的阶的识别和参数估计。
　　3.进化树重建。利用生物序列构建系统发育树，传统的方法是在分子钟假设之下对某种基因进行比对，根据核酸或氨基酸替换矩阵获得基因之间的进化距离从而构建基因树。这些基因一般具有相当的保守性，比如16SrRNA，18S rRNA等等，但是在很多情况下，基于不同基因的基因树并没有一致性。由于基于比对针的方法的局限性，出现了很多无比对方法。广泛应用的组分矢量（CV)法是利用固定字长的词频作为刻画基因组或蛋白组的特征向量，其中用到背景概率是利用高阶马尔科夫模型获得的。受此启发，我们首次提出直接利用高阶马尔科夫模型表示全蛋白质组或者全基因组，将相应的转移概率矩阵作为刻画序列的特征向量。其中阶的识别是利用我们新提出的马尔科夫香农熵最大化（MME)定阶方法。多个全蛋白质组和全基因组数据集的结果证实了这种非比对的发育树重建方法很有效。
　　4.模体发现。基因是DNA序列中具有遗传信息的基本单元，而影响和控制基因的转录和表达的是转录因子通过与基因调控元件（启动子，增强子，沉默子等）中结合位点相结合实现的，这些结合位点是相对固定又重复出现的5-20bp长度的DNA序列模式，称之为模体。理解基因表达是生物学中的重大挑战，而基因调控元件的识别特别是模体的识别是这个挑战中的一个重要课题。受Tompa等的方法的启发，我们提出利用高阶马尔科夫模型的新k-串法。首先利用高阶马尔科夫模型描述该背景序列集，在背景高阶马尔科夫模型下，确定每个k-串在序列集中的期望频数。再由实际频数与期望频数的相对偏离率，判断k-串是来自随机背景序列还是来自模体的样例。我们用多个HT-SELEX数据集证实了这种k-串法的有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章生物信息学

§ 1. 1 生物信息学的发展和研究内容

§ 1.2 本文的工作

第二章马尔科夫模型

§2.1 马尔科夫链

§2 .1.1 —阶马尔科夫模型

§2 .1.2 局阶马尔科夫模型

§2.2 马尔科夫模型统计推断问题

§2 .2 .1 转移概率和初始概率估计

§ 2 .2 .2皮尔逊卡方检验法

§2.2.3 AIC/BIC信息标准定阶法

§ 2 .2 .4马尔科夫信息熵最大化定阶法

§2.3 马尔科夫模型在生物序列分析中的应用

第三章混沌游戏表示

§ 3.1 二维混沌游戏表示

§3.2 一维混沌游戏表示

§3.2.1 一维混沌游戏表示的反演公式

§3.2.2 —维混沌游戏表示的结构指数

§3.3 —维混沌游戏表示与马尔科夫模型的关系

第四章系统发育树重建

§4 . 1 系统发育树

§4 .2 基于非比对的生物发育分析

§4 .3 高阶马尔科夫模型在生物发育树重建中的应用

§ 4 .3 .1参数估计

§ 4 .3 .2距离矩阵的计算

§ 4 .3 .3发育树重建和树的比较

§ 4 .3 .4块自助法

§4 .4 结果分析

第五章模体发现

§ 5 .1 模体及其表示

§ 5 .2 模体发现算法

§ 5 .3 高阶马尔科夫模型在模体发现中的应用

§ 5 .3 .1基于高阶马尔科夫模型的方法

§5.3.2 HT-SELEX试验数据结果

第六章工作总结和展望

参考文献

致谢

附录