一种基因参考序列的去冗余优化方法及系统

摘要

本发明公开了一种基因参考序列的去冗余优化方法及系统，针对基因参考序列，本发明通过按照指定步长遍历获取指定长度的连续参考序列Kmer，然后通过哈希桶将连续参考序列Kmer进行分散、选择性去冗余，再重新组装，从而在能够尽可能的减少参考序列Kmer的个数的同时保证连续参考序列Kmer的质量，本发明能够在保证尽量不减少压缩率的前提下减少基因参考序列的冗余度，精简出更适合的参考序列，使得优化后的基因参考序列体积更小，被用于做压缩参考索引时加载内存更快，从而提高基因数据的压缩效率。

说明书

技术领域

本发明涉及生物信息技术领域的FASTQ数据的压缩技术，具体涉及一种基因参考序列的去冗余优化方法及系统，用于实现基因参考序列的去冗余优化。

背景技术

通过FASTA生成的基因参考序列（ACTG），长度通常在10G至20G之间，存在下述技术问题：其一、档大，不利于存储；其二、当该档被用于做压缩参考索引时，将该文件从硬盘加载到内存需要消耗一定的时间，且服务器需要有足够的系统资源，这在一定程度上降低了压缩效率。

发明内容

本发明要解决的技术问题：针对现有技术的上述问题，提供一种基因参考序列的去冗余优化方法及系统，本发明能够在保证尽量不减少压缩率的前提下减少基因参考序列的冗余度，精简出更适合的参考序列，使得优化后的基因参考序列体积更小，被用于做压缩参考索引时加载内存更快，从而提高基因数据的压缩效率。

为了解决上述技术问题，本发明采用的技术方案为：

一种基因参考序列的去冗余优化方法，实施步骤包括：

1）针对基因参考序列通过按照指定步长遍历获取指定长度的连续参考序列Kmer；

2）计算各个连续参考序列Kmer的哈希值，然后将哈希值与（2ⁿ>n，n为自定义的自然数；

3）针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测，最终将冗余的连续参考序列Kmer删除，非冗余的连续参考序列Kmer保留且其对应的偏移量也需写入哈希桶对应的槽位；

4）基于保留下来的连续参考序列Kmer实现基因参考序列组装。

可选地，步骤2）中记录发生冲突的槽位具体是指针对发生冲突的槽位将对应的连续参考序列Kmer按照顺序采用链地址的方式记录；步骤3）中针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测的详细步骤包括：判断链地址中的各个连续参考序列Kmer是否冗余，如果任意连续参考序列Kmer在链地址为第一个元素，则判定该连续参考序列Kmer为非冗余；否则，在基因参考序列中从连续参考序列Kmer的起始位置获取指定长度N_read_size的基因序列A，从链地址其他所有连续参考序列Kmer的起始位置分别获取指定长度N_read_size的基因序列B(B1,..., Bn)，如果基因序列A与基因序列B(B1-Bn)中所有成员的海明距离都大于预设阈值则判定该连续参考序列Kmer为非冗余，否则判定该连续参考序列Kmer为冗余。

可选地，步骤4）的详细步骤包括：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer均为非冗余，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

可选地，步骤4）的详细步骤包括：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer为非冗余的比例大于预设阈值，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

本发明还提供一种基因参考序列的去冗余优化系统，包括计算机设备，所述计算机设备被程序设计以执行本发明前述基因参考序列的去冗余优化方法的步骤；或者所述计算机设备的存储介质中存储有被程序设计以执行本发明前述基因参考序列的去冗余优化方法的计算机程序。。

本发明还提供一种计算机可读存储介质，所述计算机可读存储介质中存储有被程序设计以执行本发明前述基因参考序列的去冗余优化方法的计算机程序。

本发明还提供一种基因参考序列的去冗余优化系统，包括：

Kmer遍历程式单元，用于针对基因参考序列通过按照指定步长遍历获取指定长度的连续参考序列Kmer；

Kmer分散程序单元，用于计算各个连续参考序列Kmer的哈希值，然后将哈希值与（2ⁿ>n，n为自定义的自然数；

Kmer去冗余程序单元，用于针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测，最终将冗余的连续参考序列Kmer删除，非冗余的连续参考序列Kmer保留且其对应的偏移量也需写入哈希桶对应的槽位；

新序列组装程序单元，用于基于保留下来的连续参考序列Kmer实现基因参考序列组装。

可选地，所述Kmer分散程序单元记录发生冲突的槽位具体是指针对发生冲突的槽位将对应的连续参考序列Kmer按照顺序采用链地址的方式记录；所述Kmer去冗余程序单元包括用于针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测的子程序单元，所述子程序单元被程序设计以执行下述步骤：判断链地址中的各个连续参考序列Kmer是否冗余，如果任意连续参考序列Kmer在链地址为第一个元素，则判定该连续参考序列Kmer为非冗余；否则，在基因参考序列中从连续参考序列Kmer的起始位置获取指定长度N_read_size的基因序列A，从链地址其他所有连续参考序列Kmer的起始位置分别获取指定长度N_read_size的基因序列B(B1,..., Bn)，如果基因序列A与基因序列B(B1-Bn)中所有成员的海明距离都大于预设阈值则判定该连续参考序列Kmer为非冗余，否则判定该连续参考序列Kmer为冗余。

可选地，所述新序列组装程序单元被程序设计以执行下述步骤：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer均为非冗余，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

可选地，所述新序列组装程序单元被程序设计以执行下述步骤：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer为非冗余的比例大于预设阈值，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

和现有技术相比，本发明具有下述优点：本发明针对基因参考序列通过按照指定步长遍历获取指定长度的连续参考序列Kmer，然后通过哈希桶将连续参考序列Kmer进行分散、去冗余，然后根据去冗余的连续参考序列Kmer对连续参考序列Kmer中指定长度N_read_size的区间进行选择性组装，从而能够尽可能的减少连续参考序列Kmer的个数的同时保证连续参考序列Kmer的质量，本发明能够在保证尽量不减少压缩率的前提下减少基因参考序列的冗余度，精简出更适合的参考序列，使得优化后的基因参考序列体积更小，被用于做压缩参考索引时加载内存更快，从而提高基因数据的压缩效率。

附图说明

图1为本发明实施例一方法的基本流程示意图。

图2为本发明实施例一中获取连续参考序列Kmer的原理示意图。

图3为本发明实施例一中将连续参考序列Kmer分散的原理示意图。

图4为本发明实施例一中将连续参考序列Kmer去冗余的原理示意图。

图5为本发明实施例一中将连续参考序列Kmer去冗余得到的结果示意图。

具体实施方式

实施例一：

如图1所示，本实施例基因参考序列的去冗余优化方法的实施步骤包括：

1）针对基因参考序列通过按照指定步长（step）遍历获取指定长度的连续参考序列Kmer；

基因参考序列由一连串A、C、T、G组成，为了便于分析和处理数据，本文引入了连续参考序列Kmer的概念。连续参考序列Kmer是对一小段连续的ACTG参考序列的命名，每隔step步长取固定长度的ACTG参考序列，本实施例基因参考序列的去冗余优化方法称之为一个连续参考序列Kmer，连续参考序列Kmer的长度N_kmer可自行定义。假定基因参考序列总长度为N_total，那么对应整个基因参考序列，共有连续参考序列Kmer的个数为N_total - N_kmer+ 1，本实施例基因参考序列的去冗余优化方法的目标就是通过算法尽可能的减少连续参考序列Kmer的个数，但同时必须保证连续参考序列Kmer的质量。

参见图2，本实施例中通过遍历依次得到的连续参考序列Kmer包括Kmer(1)～Kmer(7)等，本实施例中，指定步长step具体取值为1，假定连续参考序列Kmer的长度为150位，则第一次遍历得到的连续参考序列Kmer为0～149位，第二次遍历得到的连续参考序列Kmer为1～150位，依次类推。此外也可以根据需要取值为2或者更大的值等。

2）计算各个连续参考序列Kmer的哈希值，然后将哈希值与（2ⁿ>n，n为自定义的自然数；参见图3，分别将各个连续参考序列Kmer（Kmer(1)～Kmer(7)等）通过哈希函数计算哈希值，然后将哈希值与（2ⁿ>

3）针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测，最终将冗余的连续参考序列Kmer删除，非冗余的连续参考序列Kmer保留且其对应的偏移量（offset）也需写入哈希桶对应的槽位；

本实施例中，步骤2）中记录发生冲突的槽位具体是指针对发生冲突的槽位将对应的连续参考序列Kmer按照顺序采用链地址的方式记录，此外也可以根据需要采用他处理hash冲突的方式记录。

本实施例中，步骤3）中针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测的详细步骤包括：判断链地址中的各个连续参考序列Kmer是否冗余，如果任意连续参考序列Kmer在链地址为第一个元素，则判定该连续参考序列Kmer为非冗余；否则，在基因参考序列中从连续参考序列Kmer的起始位置获取指定长度N_read_size的基因序列A，从链地址其他所有连续参考序列Kmer的起始位置分别获取指定长度N_read_size的基因序列B(B1,..., Bn)，如果基因序列A与基因序列B(B1-Bn)中所有成员的海明距离都大于预设阈值则判定该连续参考序列Kmer为非冗余，否则判定该连续参考序列Kmer为冗余。

参见图4，当前正在插入的连续参考序列Kmer(6)，对应偏移量5，在当前槽位16中已经有Kmer(4)，对应偏移量3，插入时从连续参考序列Kmer(6) 的起始位置获取指定长度N_read_size的基因序列A，从连续参考序列Kmer(4) 的起始位置获取指定长度N_read_size的基因序列B，如果基因序列A、基因序列B之间的海明距离小于预设阈值则当前插入Kmer(6)是冗余的，因为当前槽位中Kmer(4)已经与Kmer(6)是相似的。本实施例中将连续参考序列Kmer(6) 不保留，如虚线圆圈所示。假如A和B海明距离大于预设阀值，则需要再继续遍历该槽位中所有其他的Kmer，如果都没有与Kmer(6)相似的Kmer，则Kmer(6)才保留，否则是冗余的。

参见图5，最终本实施例中判断连续参考序列Kmer(5)（偏移值为4）、连续参考序列Kmer(6) （偏移值为5）为冗余被删除。删除的方式既可以选择将偏移值不插入哈希桶，也可以选择将偏移值插入到哈希桶中，但是增加删除标记。

4）基于保留下来的连续参考序列Kmer实现基因参考序列组装。

本实施例中，步骤4）的详细步骤包括：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer均为非冗余，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

本实施例还提供一种基因参考序列的去冗余优化系统，包括计算机设备，计算机设备被程序设计以执行本实施例前述基因参考序列的去冗余优化方法的步骤。

本实施例还提供一种基因参考序列的去冗余优化系统，包括带有存储介质的计算机设备，该存储介质中存储有被程序设计以执行本实施例前述基因参考序列的去冗余优化方法的计算机程序。

本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有被程序设计以执行本实施例前述基因参考序列的去冗余优化方法的计算机程序。

本实施例还提供一种基因参考序列的去冗余优化系统，包括：

Kmer遍历程式单元，用于针对基因参考序列通过按照指定步长遍历获取指定长度的连续参考序列Kmer；

Kmer分散程序单元，用于计算各个连续参考序列Kmer的哈希值，然后将哈希值与（2ⁿ>n，n为自定义的自然数；

Kmer去冗余程序单元，用于针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测，最终将冗余的连续参考序列Kmer删除，非冗余的连续参考序列Kmer保留且其对应的偏移量也需写入哈希桶对应的槽位；

新序列组装程序单元，用于基于保留下来的连续参考序列Kmer实现基因参考序列组装。

本实施例中， Kmer分散程序单元记录发生冲突的槽位具体是指针对发生冲突的槽位将对应的连续参考序列Kmer按照顺序采用链地址的方式记录；Kmer去冗余程序单元包括用于针对发生冲突的槽位的各个连续参考序列Kmer进行冗余检测的子程序单元，子程序单元被程序设计以执行下述步骤：判断链地址中的各个连续参考序列Kmer是否冗余，如果任意连续参考序列Kmer在链地址为第一个元素，则判定该连续参考序列Kmer为非冗余；否则，在基因参考序列中从连续参考序列Kmer的起始位置获取指定长度N_read_size的基因序列A，从链地址其他所有连续参考序列Kmer的起始位置分别获取指定长度N_read_size的基因序列B(B1,..., Bn)，如果基因序列A与基因序列B(B1-Bn)中所有成员的海明距离都大于预设阈值则判定该连续参考序列Kmer为非冗余，否则判定该连续参考序列Kmer为冗余。

本实施例中，新序列组装程序单元被程序设计以执行下述步骤：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer均为非冗余，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

实施例二：

本实施例与实施例一基本相同，其主要区别点为组装新的基因参考序列的方式有所不同：本实施例中，步骤4）的详细步骤包括：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer为非冗余的比例大于预设阈值（该预设阈值可以根据需要自定义），则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。对应地，本实施例基因参考序列的去冗余优化系统中，新序列组装程序单元被程序设计以执行下述步骤：以指定长度N_read_size为单位遍历基因参考序列，如果某个指定长度N_read_size的区间内所有连续参考序列Kmer为非冗余的比例大于预设阈值，则将该指定长度N_read_size的区间的基因序列组装进新的基因参考序列，遍历完毕后最终得到新的基因参考序列。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。