本发明涉及基因测序，具体为基于图压缩的序列到图比对方法、系统、装置、存储介质。
背景技术：
1、基因组测序技术在基因功能识别、疾病诊断与治疗、进化与系统发育研究等方面具有重要意义，随着测序基因组数据的爆发式增长，基于泛基因组的序列比对方法得到应用，其中序列到图比对作为泛基因组比对的重要步骤，制约着泛基因组比对效率和准确性。
2、目前已有将序列到图的比对问题转换为最短路径问题，进而进行启发式搜索以寻找最优比对结果的方法，虽然能够提高计算速度，但是无法保证找到最优的比对结果；也有利用偏序比对方法进行序列到图的比对，但是仅依靠此方法无法有效处理泛基因组序列比对研究中的海量序列比对问题。
3、所以，需要一种同时兼顾准确性和计算速度的序列到图比对方法。
技术实现思路
1、本发明提供了一种基于图压缩的序列到图比对方法。
2、本发明技术方案如下：
3、一种基于图压缩的序列到图比对方法，包括以下步骤：
4、s1、获取基因组图和测序序列；
5、s2、基因组图图压缩：遍历基因组图中的所有结点，获取只有一个前驱结点和一个后继结点的结点为待合并结点，如果存在若干个待合并结点拥有共同的前驱结点和后继接结点，则若干个待合并结点为可合并结点，将基因组图中所述可合并结点进行合并，生成合并结点，对基因组图进行更新后得到压缩图；
6、s3、编码：基于四位二进制标记位对压缩图中的合并结点和非合并结点中的碱基进行编码，得到编码后的压缩图；
7、基于四位二进制标记位对测序序列中的每个碱基进行编码，得到编码后的测序序列；
8、s4、序列到图比对：对编码后的压缩图进行拓扑排序，与编码后的测序序列进行偏序比对，基于比对结果、预先设定的匹配罚分和不匹配罚分引入碱基置换罚分，基于引入的碱基置换罚分分别得到线性罚分、仿射罚分和双仿射罚分模式下的比对分数，
9、基于比对分数确定编码后的压缩图拓扑排序后最末端的结点和编码后的测序序列中最末端碱基的比对分数为最佳比对分数；
10、s5、基于所述比对分数构建二维方向的回溯矩阵，基于最佳比对分数位置确定回溯起点，基于回溯起点依次在其相邻位置中选择其比对分数来源方向作为回溯方向进行回溯，得到最佳比对路径，基于最佳比对路径进行序列到图的比对。
11、具体地，所述s4中引入的碱基置换罚分，计算公式为：
12、，
13、其中，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的碱基置换罚分，为用户输入的匹配罚分，为用户输入的不匹配罚分，为位与函数。
14、进一步地，所述s4中基于引入的碱基置换罚分得到线性罚分模式下的比对分数，具体为：
15、，
16、其中，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的比对分数，为结点的所有的前驱结点和编码后的测序序列中第j-1个碱基的比对分数，为结点的所有的前驱结点和序列中第j个碱基的比对分数，为结点和序列中第j-1个碱基的比对分数，为缺失罚分，为插入罚分，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的碱基置换罚分，结点为结点的前驱结点，为结点的前驱结点集合， max为取最大值。
17、进一步地，所述s4中基于引入的碱基置换罚分得到仿射罚分模式下的比对分数，具体为：
18、，
19、其中，m为未进行罚分的状态，x为进行缺失罚分的状态，y为进行插入罚分的状态，为拓扑排序第i位的结点和编码后的测序序列中第j个碱基的m状态下的分数，为结点的所有的前驱结点和编码后的测序序列中第j-1个碱基在 m状态下的比对分数，为结点的所有的前驱结点和编码后的测序序列中第j-1个碱基在 x状态下的比对分数，为结点的所有的前驱结点和编码后的测序序列中第j-1个碱基在 y状态下的比对分数，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的碱基置换罚分，结点为结点的前驱结点，为结点的前驱结点集合；为拓扑排序第位的结点和编码后的测序序列中第j个碱基的 x状态下的比对分数，和分别为结点的所有的前驱结点和序列中第j个碱基的 m状态下和 x状态下分数，为第一个空位的缺失罚分，为延伸缺失罚分；为拓扑排序第i位的结点和编码后的测序序列中第j个碱基的 y状态下的比对分数，和分别为结点和序列中第j-1个碱基的m状态下和y状态下的比对分数，为第一个空位的插入罚分，为延伸插入罚分，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的比对分数， max为取最大值。
20、具体地，所述s5中基于回溯起点依次在其相邻位置中选择其比对分数来源方向作为回溯方向进行回溯，具体为：
21、在线性罚分中：
22、如果，那么，
23、如果，那么 ，
24、如果，那么，
25、在仿射罚分中：
26、如果，那么，
27、如果，那么 ，
28、如果，那么，
29、在双仿射罚分中：
30、如果，那么，
31、如果，那么 ，
32、如果，那么，
33、如果，那么，
34、如果，那么，
35、其中，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的比对分数，为结点的所有的前驱结点和编码后的测序序列中第j-1个碱基的比对分数，为结点的所有的前驱结点和序列中第j个碱基的比对分数，为结点和序列中第j-1个碱基的比对分数，为缺失罚分，为插入罚分，为编码后的压缩图拓扑排序后第 i位的结点和编码后的测序序列中第j个碱基的碱基置换罚分，为编码后的压缩图拓扑排序后第i位结点和编码后的测序序列中第j个碱基对应得分矩阵单元的回溯方向，为前驱结点的次序，为拓扑排序第i位的结点和编码后的测序序列中第j个碱基的m状态下的分数，、、分别为拓扑排序第i位的结点和编码后的测序序列中第j个碱基的 x、 x 1、 x 2状态下的比对分数，、、分别为拓扑排序第i位的结点和编码后的测序序列中第j个碱基的 y、y 1 、y 2状态下的比对分数。
36、具体地，所述s2中获取只有一个前驱结点和一个后继结点的结点为待合并结点后，还包括：将待合并结点的一组前驱结点和后继结点作为哈希表的键，同时将待合并结点的id作为值存入哈希表，遍历哈希表，如果键对应的值列表长度大于1，则判断对应的若干个待合并结点拥有共同的前驱结点和后继接结点，为可合并结点。
37、具体地，所述s3中基于四位二进制标记位对压缩图合并结点和非合并结点进行碱基编码，为：如果标记位为1，表示合并前的合并结点和非合并结点存在该碱基；如果标记位为0，表示合并前的合并结点和非合并结点不存在该碱基。
38、本发明还提供了一种基于图压缩的序列到图比对系统，包括：
39、数据获取模块：用于获取基因组图和测序序列；
40、图压缩模块：用于遍历基因组图中的所有结点，获取只有一个前驱结点和一个后继结点的结点为待合并结点，如果存在若干个待合并结点拥有共同的前驱结点和后继接结点，则若干个待合并结点为可合并结点，将基因组图中所述可合并结点进行合并，生成合并结点，对基因组图进行更新后得到压缩图；
41、编码模块：用于基于四位二进制标记位对压缩图中的合并结点和非合并结点中的碱基进行编码，得到编码后的压缩图；基于四位二进制标记位对测序序列中的每个碱基进行编码，得到编码后的测序序列；
42、序列到图比对模块：用于对编码后的压缩图进行拓扑排序，与编码后的测序序列进行偏序比对，基于比对结果、预先设定的匹配罚分和不匹配罚分引入碱基置换罚分，基于引入的碱基置换罚分分别得到线性罚分、仿射罚分和双仿射罚分模式下的比对分数，基于比对分数得到编码后的压缩图拓扑排序后最末端的结点和编码后的测序序列中最末端碱基的比对分数为最佳比对分数；
43、回溯模块：基于所述比对分数构建二维方向的回溯矩阵，基于最佳比对分数位置确定回溯起点，基于回溯起点依次在其相邻位置中选择其比对分数来源方向作为回溯方向进行回溯，得到最佳比对路径，基于最佳比对路径进行序列到图的比对。
44、另外，本发明提供了一种基于图压缩的序列到图比对装置，包括处理器和存储器，其中，所述处理器执行所述存储器中保存的计算机程序时实现如上所述的基于图压缩的序列到图比对方法。
45、本发明还提供了一种计算机可读存储介质，存有计算机程序，该程序被处理器执行时可实现如上所述的基于图压缩的序列到图比对方法的步骤。
46、本发明的有益效果在于：
47、1、通过对基因组图结点数据的压缩，将序列到图的比对问题转换为序列到压缩图的比对问题，减少了计算过程中基因组图结点数目，减少了计算量，有效提高了比对速度；
48、2、在进行序列到图比对时，对压缩后的基因组图和测序序列基于四位二进制标记位进行编码，可以有效减少图数据规模，减少内存空间消耗；
49、3、引入碱基置换罚分，提供在线性罚分、仿射空位罚分、双仿射空位罚分多种罚分模式下的比对分数，基于比对分数确定最佳最佳比对分数位置后进行回溯，得到最佳比对路径，具有较高比对有效性和准确性。
1.一种基于图压缩的序列到图比对方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s4中引入的碱基置换罚分，计算公式为：
3.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s4中基于引入的碱基置换罚分得到线性罚分模式下的比对分数，具体为：
4.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s4中基于引入的碱基置换罚分得到仿射罚分模式下的比对分数，具体为：
5.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s5中基于回溯起点依次在其相邻位置中选择其比对分数来源方向作为回溯方向进行回溯，具体为：
6.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s2中获取只有一个前驱结点和一个后继结点的结点为待合并结点后，还包括：将待合并结点的一组前驱结点和后继结点作为哈希表的键，同时将待合并结点的id作为值存入哈希表，遍历哈希表，如果键对应的值列表长度大于1，则判断对应的若干个待合并结点拥有共同的前驱结点和后继接结点，为可合并结点。
7.根据权利要求1所述的基于图压缩的序列到图比对方法，其特征在于，所述s3中基于四位二进制标记位对压缩图合并结点和非合并结点进行碱基编码，为：如果标记位为1，表示合并前的合并结点和非合并结点存在该碱基；如果标记位为0，表示合并前的合并结点和非合并结点不存在该碱基。
8.一种基于图压缩的序列到图比对系统，其特征在于，包括：
9.一种基于图压缩的序列到图比对装置，其特征在于，包括处理器和存储器，其中，所述处理器执行所述存储器中保存的计算机程序时实现如权利要求1-7中任一项所述的基于图压缩的序列到图比对方法。
10.一种计算机可读存储介质，其特征在于，用于存储计算机程序，其中，所述计算机程序被处理器执行时实现如权利要求1-7中任一项所述的基于图压缩的序列到图比对方法。
