基于AVX指令集BWT算法在DNA序列比對中應用

孫紅敏，杜博雅，鄭萍，李東野，曹延杰，侯星辰

（1.東北農業大學電氣與信息學院，哈爾濱 150030；2.武漢理工大學計算機科學與技術學院，武漢 430070）

基于AVX指令集BWT算法在DNA序列比對中應用

孫紅敏1，杜博雅1，鄭萍1，李東野2，曹延杰1，侯星辰1

（1.東北農業大學電氣與信息學院，哈爾濱 150030；2.武漢理工大學計算機科學與技術學院，武漢 430070）

新一代高通量測序技術發展產生大規模DNA序列片段，快速準確地將短序列比對到參考基因組成為生物信息學重要研究課題之一。針對BWT索引技術序列比對算法研究，提出基于Intel微架構AVX指令集優化BWT算法，通過改進計算方式實現算法并優化。結果表明，應用AVX指令集可減少CPU訪存次數，降低算法時間復雜度，提高序列比對效率，為基因數據分析提供更高效快速序列比對方法，加快對全基因組序列處理。

序列比對；AVX指令集；BWT算法；并行優化

隨著新一代測序平臺（NGS）廣泛使用，測序通量高、時間和成本下降使DNA序列數據顯著增加，產生TB級測序片段。快速準確地將大規模DNA序列比對到參考基因組上成為生物信息學亟待解決難題[1]。將短序列與參考基因組序列比對并在參考基因組上定位，根據比對結果分析預測序列間相似性，可為后續開展表達量分析、預測SNP位點、選擇性剪接分析、疾病相關性、藥物研發、鑒定基因組中功能基因等研究奠定基礎[2]。DNA序列比對現已成為生物信息學重要內容之一[3]。

在常用比對算法中，根據索引結構不同，采用空位種子片段索引算法Maq時間效率較低，序列中插入缺失（Indel）處理困難[4]；……