Cargando…
A Review of Parallel Implementations for the Smith–Waterman Algorithm
ABSTRACT: The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, Smith–Waterman algorithm is used to...
Autores principales: | , , , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer Singapore
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8419822/ https://www.ncbi.nlm.nih.gov/pubmed/34487327 http://dx.doi.org/10.1007/s12539-021-00473-0 |
_version_ | 1783748833891581952 |
---|---|
author | Xia, Zeyu Cui, Yingbo Zhang, Ang Tang, Tao Peng, Lin Huang, Chun Yang, Canqun Liao, Xiangke |
author_facet | Xia, Zeyu Cui, Yingbo Zhang, Ang Tang, Tao Peng, Lin Huang, Chun Yang, Canqun Liao, Xiangke |
author_sort | Xia, Zeyu |
collection | PubMed |
description | ABSTRACT: The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, Smith–Waterman algorithm is used to find the best subsequence match between given sequences. However, the high time complexity makes the algorithm time-consuming. A lot of approaches have been developed to accelerate and parallelize it, such as vector-level parallelization, thread-level parallelization, process-level parallelization, and heterogeneous acceleration, but the current researches seem unsystematic, which hinders the further research of parallelizing the algorithm. In this paper, we summarize the current research status of parallel local alignments and describe the data layout in these work. Based on the research status, we emphasize large-scale genomic comparisons. By surveying some typical alignment tools’ performance, we discuss some possible directions in the future. We hope our work will provide the developers of the alignment tool with technical principle support, and help researchers choose proper alignment tools. GRAPHIC ABSTRACT: [Image: see text] |
format | Online Article Text |
id | pubmed-8419822 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Springer Singapore |
record_format | MEDLINE/PubMed |
spelling | pubmed-84198222021-09-07 A Review of Parallel Implementations for the Smith–Waterman Algorithm Xia, Zeyu Cui, Yingbo Zhang, Ang Tang, Tao Peng, Lin Huang, Chun Yang, Canqun Liao, Xiangke Interdiscip Sci Review ABSTRACT: The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, Smith–Waterman algorithm is used to find the best subsequence match between given sequences. However, the high time complexity makes the algorithm time-consuming. A lot of approaches have been developed to accelerate and parallelize it, such as vector-level parallelization, thread-level parallelization, process-level parallelization, and heterogeneous acceleration, but the current researches seem unsystematic, which hinders the further research of parallelizing the algorithm. In this paper, we summarize the current research status of parallel local alignments and describe the data layout in these work. Based on the research status, we emphasize large-scale genomic comparisons. By surveying some typical alignment tools’ performance, we discuss some possible directions in the future. We hope our work will provide the developers of the alignment tool with technical principle support, and help researchers choose proper alignment tools. GRAPHIC ABSTRACT: [Image: see text] Springer Singapore 2021-09-06 2022 /pmc/articles/PMC8419822/ /pubmed/34487327 http://dx.doi.org/10.1007/s12539-021-00473-0 Text en © International Association of Scientists in the Interdisciplinary Areas 2021 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic. |
spellingShingle | Review Xia, Zeyu Cui, Yingbo Zhang, Ang Tang, Tao Peng, Lin Huang, Chun Yang, Canqun Liao, Xiangke A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title | A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title_full | A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title_fullStr | A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title_full_unstemmed | A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title_short | A Review of Parallel Implementations for the Smith–Waterman Algorithm |
title_sort | review of parallel implementations for the smith–waterman algorithm |
topic | Review |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8419822/ https://www.ncbi.nlm.nih.gov/pubmed/34487327 http://dx.doi.org/10.1007/s12539-021-00473-0 |
work_keys_str_mv | AT xiazeyu areviewofparallelimplementationsforthesmithwatermanalgorithm AT cuiyingbo areviewofparallelimplementationsforthesmithwatermanalgorithm AT zhangang areviewofparallelimplementationsforthesmithwatermanalgorithm AT tangtao areviewofparallelimplementationsforthesmithwatermanalgorithm AT penglin areviewofparallelimplementationsforthesmithwatermanalgorithm AT huangchun areviewofparallelimplementationsforthesmithwatermanalgorithm AT yangcanqun areviewofparallelimplementationsforthesmithwatermanalgorithm AT liaoxiangke areviewofparallelimplementationsforthesmithwatermanalgorithm AT xiazeyu reviewofparallelimplementationsforthesmithwatermanalgorithm AT cuiyingbo reviewofparallelimplementationsforthesmithwatermanalgorithm AT zhangang reviewofparallelimplementationsforthesmithwatermanalgorithm AT tangtao reviewofparallelimplementationsforthesmithwatermanalgorithm AT penglin reviewofparallelimplementationsforthesmithwatermanalgorithm AT huangchun reviewofparallelimplementationsforthesmithwatermanalgorithm AT yangcanqun reviewofparallelimplementationsforthesmithwatermanalgorithm AT liaoxiangke reviewofparallelimplementationsforthesmithwatermanalgorithm |