TY - JOUR
T1 - A 135-mW Fully Integrated Data Processor for Next-Generation Sequencing
AU - Wu, Yi Chung
AU - Chang, Chia Hua
AU - Hung, Jui-Hung
AU - Yang, Chia Hsiang
PY - 2017/12/1
Y1 - 2017/12/1
N2 - Next-generation sequencing (NGS) enables high-throughput sequencing, in which short DNA fragments can be sequenced in a massively parallel fashion. However, the essential algorithm behind the succeeding NGS data analysis, DNA mapping, is still excessively time consuming. DNA mapping can be partitioned into two parts: suffix array (SA) sorting and backward searching. Dedicated hardware designs for the less-complex backward searching have been proposed, but feasible hardware for the most complicated part, SA sorting, has never been explored. Based on the memory-efficient sBWT algorithm, this work is the first integrated NGS data processor for the entire DNA mapping. The κ-ordered Ferragina and Manzini index used in the sBWT algorithm is leveraged to improve storage capacity and reduce hardware complexity. The proposed NGS data processor realizes the sBWT algorithm through bucket sorting, suffix grouping, and suffix sorting circuits. Key design parameters are analyzed to achieve the optimal performance with respect to hardware cost and execution time. Fabricated in 40-nm CMOS, the NGS data processor dissipates 135 mW at 200 MHz from a 0.9-V supply. With 1-GB external memory, the chip can analyze human DNA within 10 min. This work achieves 43 065 × and 8 971 × [3208 × and 402× ] higher energy efficiency (throughput-to-area ratio) than the high-end CPU and GPU solutions, respectively.
AB - Next-generation sequencing (NGS) enables high-throughput sequencing, in which short DNA fragments can be sequenced in a massively parallel fashion. However, the essential algorithm behind the succeeding NGS data analysis, DNA mapping, is still excessively time consuming. DNA mapping can be partitioned into two parts: suffix array (SA) sorting and backward searching. Dedicated hardware designs for the less-complex backward searching have been proposed, but feasible hardware for the most complicated part, SA sorting, has never been explored. Based on the memory-efficient sBWT algorithm, this work is the first integrated NGS data processor for the entire DNA mapping. The κ-ordered Ferragina and Manzini index used in the sBWT algorithm is leveraged to improve storage capacity and reduce hardware complexity. The proposed NGS data processor realizes the sBWT algorithm through bucket sorting, suffix grouping, and suffix sorting circuits. Key design parameters are analyzed to achieve the optimal performance with respect to hardware cost and execution time. Fabricated in 40-nm CMOS, the NGS data processor dissipates 135 mW at 200 MHz from a 0.9-V supply. With 1-GB external memory, the chip can analyze human DNA within 10 min. This work achieves 43 065 × and 8 971 × [3208 × and 402× ] higher energy efficiency (throughput-to-area ratio) than the high-end CPU and GPU solutions, respectively.
KW - CMOS digital integrated circuits
KW - DNA mapping
KW - FM-index
KW - Next-generation sequencing (NGS)
KW - sBWT algorithm
KW - suffix array sorting
UR - http://www.scopus.com/inward/record.url?scp=85034433069&partnerID=8YFLogxK
U2 - 10.1109/TBCAS.2017.2760109
DO - 10.1109/TBCAS.2017.2760109
M3 - Article
C2 - 29293419
AN - SCOPUS:85034433069
SN - 1932-4545
VL - 11
SP - 1216
EP - 1225
JO - IEEE Transactions on Biomedical Circuits and Systems
JF - IEEE Transactions on Biomedical Circuits and Systems
IS - 6
M1 - 8094922
ER -