SBWT: Memory efficient implementation of the hardware-acceleration-friendly Schindler transform for the fast biological sequence mapping

Chia Hua Chang, Min Te Chou, Yi Chung Wu, Ting Wei Hong, Yun Lung Li, Chia Hsiang Yang, Jui-Hung Hung

研究成果: Article同行評審

6 引文 斯高帕斯(Scopus)

摘要

Motivation: The Full-text index in Minute space (FM-index) derived from the Burrows-Wheeler transform (BWT) is broadly used for fast string matching in large genomes or a huge set of sequencing reads. Several graphic processing unit (GPU) accelerated aligners based on the FM-index have been proposed recently; however, the construction of the index is still handled by central processing unit (CPU), only parallelized in data level (e.g. by performing blockwise suffix sorting in GPU), or not scalable for large genomes. Results: To fulfill the need for a more practical, hardware-parallelizable indexing and matching approach, we herein propose sBWT based on a BWT variant (i.e. Schindler transform) that can be built with highly simplified hardware-acceleration-friendly algorithms and still suffices accurate and fast string matching in repetitive references. In our tests, the implementation achieves significant speedups in indexing and searching compared with other BWT-based tools and can be applied to a variety of domains.

原文English
頁(從 - 到)3498-3500
頁數3
期刊Bioinformatics
32
發行號22
DOIs
出版狀態Published - 15 十一月 2016

指紋 深入研究「SBWT: Memory efficient implementation of the hardware-acceleration-friendly Schindler transform for the fast biological sequence mapping」主題。共同形成了獨特的指紋。

引用此