基于k-mer相异度算法在系统进化关系中的应用

发布时间：2020-05-03 18:50

【摘要】：系统发育学是研究生物进化关系的一门学科,在系统发育学中,最常用于研究进化关系的方法就是系统进化树。基于多序列比对法的经典的系统进化树构建算法速度太慢,无法在大规模数据上进行运行,序列非比对法中基于k-mer的相异度算法构建系统进化树则不受这些限制影响,因而具有更广泛的应用前景。近些年来,基于k-mer的相异度算法被强调为基于系统发育推断中多重序列比对法的替代方法。基于k-mer的相异度算法属于序列非比对法中的一种,正处于快速发展的阶段,在不同的进化情景下使用基于k-mer的相异度算法系统地评估系统发育推理的准确性成为当前研究的一个热点和难点。本论文利用自己开发的软件包SeqDistK及一种比较经典的CAFE软件包实现了d2S等7种基于k-mer的相异度算法的距离矩阵,并在此基础上结合UPGMA构建系统进化树或进行聚类。基于一个已知进化关系的16S rRNA验证数据集(57条分子序列,称之为标准树),我们验证了基于k-mer的7种相异度算法构建系统进化树的准确度。与已知的真实进化关系相比较,我们发现基于k-mer的d2、d2S、d2star、Ma、Eu、Hao等多个相异度算法所得的系统进化树与标准树差异不大(Ch有一定的误差),特别是d2、d2star、d2S和Eu算法在k=5时有极其优异的性能,所得系统进化树与标准树相差无几。其中相异度算法d2S选取马尔可夫阶次为2时的算法可达到最高精准度(对称差仅有12)。本论文还利用软件包SeqDistK对63条16S rRNA序列所得的距离矩阵进行菌类聚类验证,发现所得聚类结果与生物分类学基本一致,其中d2S(k=5,M=2)的表现最为优秀,能准确的对样本序列聚类以及分类。另外我们发展的基于k-mer相异度算法的软件包SeqDistK无论是构建系统进化树还是菌类聚类具有运算速度快、精确度高的特点,适合于研究宏基因组大数据中的复杂系统发育关系的推理。使用基于k-mer相异度算法结合UPGMA研究基因组的复杂进化关系,这可能潜在地为系统进化提供新的见解,并改变我们传统的进行系统发育的研究方式,潜在地推进下一代系统发育学的发展。
【图文】：

序列,距离矩阵,系统进化树,出现次数

华南理工大学硕士学位论文10图2-1 简化的工作流程说明：我们对4条序列构建系统进化树为例说明（1）从四条序列中搜索k-mer (k=5，例GCCGT)（2）四条序列中所有k-mer (k=5)出现次数的统计（3）四条序列的距离矩阵图（4）用UPGMA画出四条序列的系统进化树基于k-mer的序列相异度算法近年来不断地被提出来，索引k-mer并且统计其频次的技术已经日趋成熟，并且k-mer的实际应用已经非常地多而且取得了不错的成效，本论文提及的7种相异度算法就是基于k-mer的频次，基于k-mer的相异度算法的第一步就是把由A、C、G、T四个字母构成的序列通过k-mer频次计数的方法化为一个k-mer频度向量，这也是这种算法的关键部分，我们可以用这个向量来表示序列的k-mer频度分布特征

界面图,软件运行,界面,相异度

图2-2 SeqDistK软件运行界面基于C#本研究小组自行开发了基于k-mer统计的相异度算法软件包SeqDistK，可寻https://github.com/htczero/SeqDistK，具有计算速度快，简洁，占用空间小的特点。们软件包的界面简化图如图2-2。SeqDistK通过对输入的序列文件的k-mer进行统计，对不同序列的k-mer频率进行较，再用不同的相异度算法算出序列间的相异度。最后SeqDistK可以输出距离矩阵文，矩阵文件可以与UPGMA软件包相兼容，方便得出系统进化树。SeqDistK有多个功能自由设置k-mer的k值和相异度算法d2S，d2star的马尔可夫阶次M可以完成一条序列N条序列的比对或者N条序列的两两比对。SeqDistK包含了7种相异度算法，Euclidi离，Manhattan，Chebyshev距离，Hao（也叫CVTree），d2，d2S及d2star。该软件包所时间与输入文件的大小与选择的k值及M值相关，运行程序的内存只与k的取值有关SeqDistK软件包具有以下优势：（1）通过多次优化，充分利用多线程编程提高CPU利
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：Q111;TP301.6

【参考文献】