论文部分内容阅读
系统分析是目前生物信息学领域最重要的课题之一。分子系统分析是通过分析各生物分子序列之间的特征，进而构建出能阐明生物间进化关系的系统树或者系统发生网络。系统发生网络是系统树的一般形式。系统发生网络可以描述物种在进化过程中发生的网状进化事件（如重组），也可以表示多棵系统树所隐含的冲突进化信息。因此如何构建系统发生网络是一个重要的研究领域。为了研究系统发生网络构建算法，本文首先研究了序列间距离计算方法，其次是基于距离的系统树构建算法及系统发生网络空间上度量的定义，最后重点研究了基于有根系统树的系统发生网络构建算法。本文的主要内容包括：(1)提出了一种DNA序列间距离计算方法——JCV。给定一组物种的DNA序列，JCV首先将每个物种的DNA序列表示为一个特征向量，然后基于特征向量计算物种间距离。计算得到的距离矩阵被用于构建系统树，以此进行分子系统分析。JCV绕过了计算多序列比对的复杂性，故JCV可以为任何长度大小的DNA序列数据计算距离。同时基于JCV方法的进化分析避免了基于单个基因构建物种树的歧义性。(2)提出了基于距离的系统树构建方法——FastJoin。邻接法是一种基于距离的系统树构建方法，由于其精确性高及运行速度快，被广泛使用。邻接法是基于理论：当输入的距离矩阵是完全可加时，通过距离矩阵计算得到的和矩阵S中的最小值Si0j0对应的两个分类单元（即物种） i0和j0是一对真正的邻接。故邻接法的建树过程是迭代地选取一对分类单元合并为一个新的分类单元，直到仅剩的分类单元个数≤3为止。经过对邻接法的深入研究，扩展了其理论并得到：当输入的距离矩阵是完全可加时，S中还存在另一对真正的邻接，即，S中去掉最小值Si0j0所在行和列后剩下元素中的最小值对应的两个分类单元。基于此理论，改进了邻接法。因此，邻接法改进算法的建树过程是迭代地选取出两对分类单元分别合并为两个新的分类单元，直到仅剩的分类单元个数≤3为止。实验证明邻接法改进算法比邻接法的运行速度快。将邻接法改进算法与RapidNJ的搜索策略及ERapidNJ的外存方式相结合得到了系统树构建方法——FastJoin。实验证明FastJoin是非常有效的，尤其在处理大数据时。(3)定义了部分简化系统发生网络空间上的度量。传统意义上，物种的进化史是被描述成一棵有根系统树。对于从不同的数据集（如不同的基因）构建得到的有根系统树，他们包含的进化信息通常是冲突的。冲突的进化信息不能被表示为一棵系统树。然而，系统发生网络可以表示这些冲突的进化信息。在系统发生网络的构建过程中，需要计算系统发生网络间的距离，例如计算得到的网络与仿真网络或者真实网络之间的距离。目前已经定义了许多用来量化两系统发生网络之间的拓扑差异度，其中的每一个被证明是在系统发生网络某一子空间上的度量。本文定义了部分简化系统发生网络空间，该空间包含已定义度量的子空间。并且本文在部分简化系统发生网络空间上定义了多项式时间内可计算的度量。(4)提出了基于有根系统树的系统发生网络构建方法——LNETWORK及BIMLR。目前已经有许多从有根系统树集构建系统发生网络的方法。CASS是目前较有效的系统发生网络构建方法，它所构建的网络比其他方法更简单，但是对于大数据集或者是那些需要很多网络节点表示的数据集，此方法运行速度极其慢。而且CASS构建的网络极大地依赖于输入数据顺序，即，对于同一数据集，当输入顺序不同时，CASS常常构建出不同的系统发生网络。本文首先基于种子增长算法定义了分离物种，其次基于分离物种及不相容物种提出了CASS的两种改进算法：LNETWORK及BIMLR。实验表明LNETWORK和BIMLR加速了CASS构建网络过程，而且有效地消弱了输入数据顺序的影响。同时LNETWORK和BIMLR所构建的网络比其他方法更简单，并且更能体现原始输入数据的进化信息。