TY - GEN
T1 - Darwin-WGA
T2 - 25th IEEE International Symposium on High Performance Computer Architecture, HPCA 2019
AU - Turakhia, Yatish
AU - Goenka, Sneha D.
AU - Bejerano, Gill
AU - Dally, WIlliam J.
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/3/26
Y1 - 2019/3/26
N2 - Whole genome alignment (WGA) is an indispensable tool in comparative genomics to study how different lifeforms have been shaped by evolution at the molecular level. Existing software whole genome aligners require several CPU weeks to compare a pair of mammalian genomes and still miss several biologically-meaningful, high-scoring alignment regions. These aligners are based on the seed-filter-and-extend paradigm with an ungapped filtering stage. Ungapped filtering is responsible for the low sensitivity of these aligners but is used because it is 200× faster than performing gapped alignment, using dynamic programming, in software. In this paper, we show that both performance and sensitivity can be greatly improved by using a hardware accelerator for WGA. Using the genomes of two roundworms (C. elegans and C. Briggsae) and four fruit flies (D. melanogaster, D. simulans, D. yakuba, and D. pseudoobscura), we show that replacing ungapped filtering with gapped filtering increases the number of matching base-pairs in alignments by up to 3×. Our accelerator, Darwin-WGA, is the first hardware accelerator for whole genome alignment and accelerates the gapped filtering stage. Darwin-WGA also employs GACT-X, a novel algorithm used in the extension stage to align arbitrarily long genome sequences using a small on-chip memory, that provides better quality alignments at 2× improvement in memory and speed over the previously published GACT algorithm. Implemented on an FPGA, Darwin-WGA provides up to 24× improvement (performance/$) in WGA over iso-sensitive software. An ASIC implementation of the proposed architecture on TSMC 40nm technology takes around 43W power with 36mm2 area. It achieves up to 10× performance/watt improvement on whole genome alignments over state-of-the-art software at higher sensitivity, and up to 1,500× performance/watt improvement compared to iso-sensitive software. Darwin-WGA is released under open-source MIT license and is available from https://github.com/gsneha26/Darwin-WGA.
AB - Whole genome alignment (WGA) is an indispensable tool in comparative genomics to study how different lifeforms have been shaped by evolution at the molecular level. Existing software whole genome aligners require several CPU weeks to compare a pair of mammalian genomes and still miss several biologically-meaningful, high-scoring alignment regions. These aligners are based on the seed-filter-and-extend paradigm with an ungapped filtering stage. Ungapped filtering is responsible for the low sensitivity of these aligners but is used because it is 200× faster than performing gapped alignment, using dynamic programming, in software. In this paper, we show that both performance and sensitivity can be greatly improved by using a hardware accelerator for WGA. Using the genomes of two roundworms (C. elegans and C. Briggsae) and four fruit flies (D. melanogaster, D. simulans, D. yakuba, and D. pseudoobscura), we show that replacing ungapped filtering with gapped filtering increases the number of matching base-pairs in alignments by up to 3×. Our accelerator, Darwin-WGA, is the first hardware accelerator for whole genome alignment and accelerates the gapped filtering stage. Darwin-WGA also employs GACT-X, a novel algorithm used in the extension stage to align arbitrarily long genome sequences using a small on-chip memory, that provides better quality alignments at 2× improvement in memory and speed over the previously published GACT algorithm. Implemented on an FPGA, Darwin-WGA provides up to 24× improvement (performance/$) in WGA over iso-sensitive software. An ASIC implementation of the proposed architecture on TSMC 40nm technology takes around 43W power with 36mm2 area. It achieves up to 10× performance/watt improvement on whole genome alignments over state-of-the-art software at higher sensitivity, and up to 1,500× performance/watt improvement compared to iso-sensitive software. Darwin-WGA is released under open-source MIT license and is available from https://github.com/gsneha26/Darwin-WGA.
KW - Co-processor
KW - Comparative Genomics
KW - Gapped Filtering
KW - Whole Genome Alignment
UR - http://www.scopus.com/inward/record.url?scp=85064191348&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064191348&partnerID=8YFLogxK
U2 - 10.1109/HPCA.2019.00050
DO - 10.1109/HPCA.2019.00050
M3 - Conference contribution
AN - SCOPUS:85064191348
T3 - Proceedings - 25th IEEE International Symposium on High Performance Computer Architecture, HPCA 2019
SP - 359
EP - 372
BT - Proceedings - 25th IEEE International Symposium on High Performance Computer Architecture, HPCA 2019
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 16 February 2019 through 20 February 2019
ER -