"天河二号"上一种dna序列denovo拼接方法的并行优化策略

基于stringgraph理论的序列拼接工具sga是当前国际上的一种新型序列拼接工具.首先,形式化证明了sga的序列拼接问题是一个np完全问题,然后对sga的拼接效率进行了分析,发现与业界同类拼接软件相比,sga在内存开销方面具有优势,但却有更大的时间开销,其中构建索引占了60%~70%的比例.基于此,设计了一种并行优化策略,并实现了面向天河二号体系结构的并行策略来解决这一问题.分别在普通机群和天河二号上进行性能测试,针对小规模数据,优化后的索引构建时间比之前的最佳性能提高了3.06倍,中等规模数据提高了1.60倍,实验结果表明,其优化效果明显,且并行构建局部索引过程具有良好的线性扩展性.其中用到的优化方法和策略对相关问题的研究有一定的借鉴意义.这也表明,天河二号的超级计算能力能够很好地助力生命科学领域的相关研究.