本发明属于生物信息领域，涉及系统发育学研究中的发育树分析与构建，具体涉及一种基于syncmer的进化距离估计及系统发育树构建方法。
背景技术：
1、系统发育学研究的是物种之间的进化历史和关系，而系统发育树的构建是生物信息领域的一个基本问题，也是系统发育学的研究结论的一个重要表现形式。通过系统发育树中的分支模式，可以反映出物种或其他种群是如何从一系列共同祖先演化而来的关系，可以更直观的通过去观察系统发育树对物种间相互关系进行判断。为生物学家研究物种起源、发展以及未来变化趋势提供了重要的依据。
2、目前在学术界对于系统发育树的构建方法主要分为三种(1)基于距离的系统发育树构建方法(2)基于最大简约法的系统发育树构建方法以及(3)基于最大似然法的系统发育树构建方法。其中基于距离的系统发育树构建方法与多序列比对紧密相关，传统的基于距离的系统发育树构建方法主要是通过比较序列之间的进化距离来推断他们之间的进化关系，而进化距离通常是使用多序列比对的方式去计算序列之间的相似性或差异性得出，但随着物种个数的增加，传统基于距离的系统发育树构建方法展现出现了弊端，随着数据量增加，时间复杂度、空间复杂度呈指数级增加，资源消耗增加。
3、近年来提出了一些新的构建系统发育树的方法，这些方法大多数依赖于精确匹配的变体，直接将序列转换为距离，而无需事先比对，将得到的结果再通过upgma或邻接法等算法将其转换为系统发育树。主要包括有brian d.ondov等人设计的mash、fabian klotzl等人设计的phylonium、shahab sarmashghi等人设计的skmer、bernhard haubold等人设计的andi、naser anjum等人设计的cd-maws等系列工具，这一类工具构建系统发育树的方法主要是通过计算序列间距离，得到结果后在选择合适的方法将距离矩阵转换构建为系统发育树。fang wang等人设计的mike、xuemei liu等人设计的ksak、runbin tang等人设计的kinn等系列工具则是将计算进化距离和构建系统发育树两步相结合直接进行系统发育推断，构建系统发育树。
4、他们的共同特点在于都采用了无需对序列进行精确比对的方法来计算进化距离，并将计算得到的进化距离矩阵通过算法转换为系统发育树。其中mash首次将minhash算法引入到了生物序列比对领域，minhash的主要原理是通过哈希技术来简化和加速大规模数据的相似性计算，在进化距离计算上，主要表现为利用minhash去近似计算两条序列之间的jaccard相似指数并将其转换为进化距离。
5、但是当前的系统发育树构建方法仍存在随着序列数据集增加导致资源消耗增加、计算效率降低、计算准确度降低且面对序列局部突变时结果出现较大波动的现象，有的方法通过增加空间上或时间上的消耗来换取精度上的提升，或通过舍弃精度来换取计算资源消耗的降低，且多数方法无法在面对序列局部突变的情况下维持稳定，并随着序列数据的增加出现计算错误，从而影响到最终构建的系统发育树。在面对新增数据集时，多数工具采用的方式是对当前所有序列重新计算，导致多数序列被多次用于计算，带来了额外的成本开销。
技术实现思路
1、本发明的目的在于提供一种基于syncmer的进化距离估计及系统发育树构建方法，旨在提高计算效率，减少计算资源消耗，增强在局部突变情况下的稳定性，并适应未来多基因组构建系统发育树的趋势。
2、本发明是这样实现的，一种基于syncmer的进化距离估计及系统发育树构建方法包括如下步骤：
3、步骤一、读取序列文件并将序列进行初步处理；
4、步骤二、遍历序列上所有长度为k的kmer，找到kmer上hash值最小的smer并判断；
5、步骤三、遵循minhash算法最终保留hash值最小的n个syncmer构成草图；
6、步骤四、草图相互比对计算进化距离矩阵；
7、步骤五、将距离矩阵转换为系统发育树。
8、进一步，所述的步骤一通过读取fasta格式文件的序列信息并去除其中的非碱基字符，得到正确序列后进行存储用于后续处理，同时根据序列大小确定后续的参数大小。
9、进一步，所述的步骤二遍历序列上所有kmer，找到kmer上hash值最小的smer并判断是否为syncmer：
10、步骤一、遍历序列上的所有kmer，并对每个kmer单独进行一次遍历；
11、步骤二、遍历kmer，并保留每个kmer上hash值最小的smer信息；
12、步骤三、遍历kmer结束后对得到的最小hash值smer进行判断。
13、进一步，所述的步骤三遵循minhash算法最终保留hash值最小的n个syncmer构成草图：
14、步骤一、创建一个存储syncmer的容器，并记录容器内最大hash值syncmer；
15、步骤二、容器内存储个数小于n时直接存储到容器中，大于n将syncmer加入候选队列；
16、步骤三、对候选队列中syncmer进行判定，最终保留hash值最小的n个syncmer。
17、进一步，所述的步骤四将所有序列构建的草图进行比对，计算jaccard相似指数并根据jaccard相似指数进行进化距离计算，得到进化距离矩阵。
18、进一步，所述的步骤五将计算得到的距离矩阵选择(mashtree、treedist)其一构建系统发育树，并使用可视化工具得到树图。
19、本发明的有益效果如下：
20、(1)本发明所使用的计算进化距离矩阵的方法，采用的是一种minhash算法和syncmer相结合生成较小的草图来表示整条序列。显著减少了数据的规模，再通过比对草图的方式来计算进化距离矩阵，能够节省大量计算资源，适用于大规模多序列数据集。
21、(2)本发明使用的syncmer，在面对序列局部突变的情况下仍能较好的维持原始的序列特征，使用syncmer构建草图能保证较稳定的相似性计算，使得计算出来的进化距离更准确，构建的系统发育树更加精确。
22、(3)本发明所涉及到的系统发育树构建方法可拓展性强，每条序列转换为草图后数据方便存储，后续加入新的序列也只需专门对新的序列进行草图构建，可与之前已构建的草图直接进行比对，提高了计算效率，避免了冗余计算，有利于大规模数据集下系统发育树构建。
1.一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的基于syncmer的进化距离估计及系统发育树构建方法包括如下步骤：
2.如权利要求1所述的一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的步骤一通过读取fasta格式文件的序列信息并去除其中的非碱基字符，得到正确序列后进行存储用于后续处理，同时根据序列大小确定后续的参数大小。
3.如权利要求1所述的一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的步骤二遍历序列上所有长度为k的kmer，找到kmer上hash值最小的smer并判断，其具体步骤如下：
4.如权利要求1所述的一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的步骤三遵循minhash算法最终保留hash值最小的n个syncmer构成草图，其具体步骤如下：
5.如权利要求1所述的一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的步骤四将所有序列构成的草图进行比对，计算草图之间的jaccard相似指数并根据jaccard相似指数进行进化距离计算，得到进化距离矩阵。
6.如权利要求1所述的一种基于syncmer的进化距离估计及系统发育树构建方法，其特征在于，所述的步骤五将计算得到的距离矩阵选择(mashtree、treedist)其一构建系统发育树，并使用可视化工具得到树图。
