Efficient GPU-based algorithm for aligning huge sequence database

Chun Yuan Lin; Che Lun Hung; Jen Cheng Huang

doi:10.1109/HPCC.and.EUC.2013.251

Efficient GPU-based algorithm for aligning huge sequence database

Chun Yuan Lin, Che Lun Hung, Jen Cheng Huang

Institute of Biomedical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Sequence alignment has been widely utilized in biological computing science. To obtain the optimal alignment results many algorithms adopts dynamic programming method to achieve this goal. Smith-Waterman algorithm is the famous in the sequence alignment approach. However, such dynamic programming algorithms are computation-consuming. It is impossible to use these algorithms to compare query sequence with a sequence database such as GenBank and PDB. Recently, GPU computing has been applied in many sequence alignment algorithms to enhance the performance. In this paper, we proposed a GPU-based Smith-Waterman algorithm by combining the CPU and GPU computing capabilities to accelerate alignments on a sequence database. In the proposed algorithm, a filtration mechanism using frequency distance is used to decrease the number of compared sequences. We implemented the Smith-Waterman alignments by CUDA on the NVIDIA Tesla C2050. The experimental results show that the highest speedup ratio is about 80 to 90 times over CPU-based Smith-Waterman algorithm.

Original language	English
Title of host publication	Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013
Publisher	IEEE Computer Society
Pages	1758-1762
Number of pages	5
ISBN (Print)	9780769550886
DOIs	https://doi.org/10.1109/HPCC.and.EUC.2013.251
State	Published - 2014
Event	15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013 - Zhangjiajie, Hunan, China Duration: 13 Nov 2013 → 15 Nov 2013

Publication series

Name	Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013

Conference

Conference	15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013
Country/Territory	China
City	Zhangjiajie, Hunan
Period	13/11/13 → 15/11/13

Keywords

GPU
Parallel processing
Sequence alignment
Smith-Waterman algorithm

Access to Document

10.1109/HPCC.and.EUC.2013.251

Cite this

Lin, C. Y., Hung, C. L., & Huang, J. C. (2014). Efficient GPU-based algorithm for aligning huge sequence database. In Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013 (pp. 1758-1762). Article 6832133 (Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013). IEEE Computer Society. https://doi.org/10.1109/HPCC.and.EUC.2013.251

Lin, Chun Yuan ; Hung, Che Lun ; Huang, Jen Cheng. / Efficient GPU-based algorithm for aligning huge sequence database. Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013. IEEE Computer Society, 2014. pp. 1758-1762 (Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013).

@inproceedings{7a7d02e3515e4b5ba317b5f6116c9bab,

title = "Efficient GPU-based algorithm for aligning huge sequence database",

abstract = "Sequence alignment has been widely utilized in biological computing science. To obtain the optimal alignment results many algorithms adopts dynamic programming method to achieve this goal. Smith-Waterman algorithm is the famous in the sequence alignment approach. However, such dynamic programming algorithms are computation-consuming. It is impossible to use these algorithms to compare query sequence with a sequence database such as GenBank and PDB. Recently, GPU computing has been applied in many sequence alignment algorithms to enhance the performance. In this paper, we proposed a GPU-based Smith-Waterman algorithm by combining the CPU and GPU computing capabilities to accelerate alignments on a sequence database. In the proposed algorithm, a filtration mechanism using frequency distance is used to decrease the number of compared sequences. We implemented the Smith-Waterman alignments by CUDA on the NVIDIA Tesla C2050. The experimental results show that the highest speedup ratio is about 80 to 90 times over CPU-based Smith-Waterman algorithm.",

keywords = "GPU, Parallel processing, Sequence alignment, Smith-Waterman algorithm",

author = "Lin, {Chun Yuan} and Hung, {Che Lun} and Huang, {Jen Cheng}",

year = "2014",

doi = "10.1109/HPCC.and.EUC.2013.251",

language = "English",

isbn = "9780769550886",

series = "Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013",

publisher = "IEEE Computer Society",

pages = "1758--1762",

booktitle = "Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013",

address = "美國",

note = "15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013 ; Conference date: 13-11-2013 Through 15-11-2013",

}

Lin, CY, Hung, CL & Huang, JC 2014, Efficient GPU-based algorithm for aligning huge sequence database. in Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013., 6832133, Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013, IEEE Computer Society, pp. 1758-1762, 15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013, Zhangjiajie, Hunan, China, 13/11/13. https://doi.org/10.1109/HPCC.and.EUC.2013.251

Efficient GPU-based algorithm for aligning huge sequence database. / Lin, Chun Yuan; Hung, Che Lun; Huang, Jen Cheng.
Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013. IEEE Computer Society, 2014. p. 1758-1762 6832133 (Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient GPU-based algorithm for aligning huge sequence database

AU - Lin, Chun Yuan

AU - Hung, Che Lun

AU - Huang, Jen Cheng

PY - 2014

Y1 - 2014

N2 - Sequence alignment has been widely utilized in biological computing science. To obtain the optimal alignment results many algorithms adopts dynamic programming method to achieve this goal. Smith-Waterman algorithm is the famous in the sequence alignment approach. However, such dynamic programming algorithms are computation-consuming. It is impossible to use these algorithms to compare query sequence with a sequence database such as GenBank and PDB. Recently, GPU computing has been applied in many sequence alignment algorithms to enhance the performance. In this paper, we proposed a GPU-based Smith-Waterman algorithm by combining the CPU and GPU computing capabilities to accelerate alignments on a sequence database. In the proposed algorithm, a filtration mechanism using frequency distance is used to decrease the number of compared sequences. We implemented the Smith-Waterman alignments by CUDA on the NVIDIA Tesla C2050. The experimental results show that the highest speedup ratio is about 80 to 90 times over CPU-based Smith-Waterman algorithm.

AB - Sequence alignment has been widely utilized in biological computing science. To obtain the optimal alignment results many algorithms adopts dynamic programming method to achieve this goal. Smith-Waterman algorithm is the famous in the sequence alignment approach. However, such dynamic programming algorithms are computation-consuming. It is impossible to use these algorithms to compare query sequence with a sequence database such as GenBank and PDB. Recently, GPU computing has been applied in many sequence alignment algorithms to enhance the performance. In this paper, we proposed a GPU-based Smith-Waterman algorithm by combining the CPU and GPU computing capabilities to accelerate alignments on a sequence database. In the proposed algorithm, a filtration mechanism using frequency distance is used to decrease the number of compared sequences. We implemented the Smith-Waterman alignments by CUDA on the NVIDIA Tesla C2050. The experimental results show that the highest speedup ratio is about 80 to 90 times over CPU-based Smith-Waterman algorithm.

KW - GPU

KW - Parallel processing

KW - Sequence alignment

KW - Smith-Waterman algorithm

UR - http://www.scopus.com/inward/record.url?scp=84903954249&partnerID=8YFLogxK

U2 - 10.1109/HPCC.and.EUC.2013.251

DO - 10.1109/HPCC.and.EUC.2013.251

M3 - Conference contribution

AN - SCOPUS:84903954249

SN - 9780769550886

T3 - Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013

SP - 1758

EP - 1762

BT - Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013

PB - IEEE Computer Society

T2 - 15th IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 11th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, EUC 2013

Y2 - 13 November 2013 through 15 November 2013

ER -

Lin CY, Hung CL, Huang JC. Efficient GPU-based algorithm for aligning huge sequence database. In Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013. IEEE Computer Society. 2014. p. 1758-1762. 6832133. (Proceedings - 2013 IEEE International Conference on High Performance Computing and Communications, HPCC 2013 and 2013 IEEE International Conference on Embedded and Ubiquitous Computing, EUC 2013). doi: 10.1109/HPCC.and.EUC.2013.251

Efficient GPU-based algorithm for aligning huge sequence database

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this