一种对多序列BWT索引构建进行并行加速的方法

摘要

本发明公开了一种多序列BWT索引构建的并行加速方法，目的是解决现有大规模序列集合BWT索引构建中对序列集合进行分块排序，然后通过两两合并再排序的方式不断递归合并排序的过程，造成BWT索引构建速度较慢，效率低下的问题。采用的技术方案是首先遍历序列集合R中各序列的所有后缀，检查各后缀的前l个字符,把具有相同前l个字符的后缀划分到同一个内存分块；之后并行地在各个分块内部独立地对该分块所包含的后缀进行排序；然后将各排好序的分块拼接起来，得到序列集合R中所有后缀的次序；最后按字典序从小到大的顺序依次取各后缀的BWT字符连接起来得到序列集合R的BWT索引。有益效果是有效提高多序列BWT索引的构建过程，减少全基因组组装所需时间约90％。