Using GPU to accelerate the pairwise structural RNA alignment with base pair probabilities
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Using GPU to accelerate the pairwise structural RNA alignment with base pair probabilities. / Sundfeld, Daniel; Teodoro, George; Havgaard, Jakob H.; Gorodkin, Jan; Melo, Alba C.M.A.
I: Concurrency Computation, Bind 32, Nr. 10, e5468, 2020.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Using GPU to accelerate the pairwise structural RNA alignment with base pair probabilities
AU - Sundfeld, Daniel
AU - Teodoro, George
AU - Havgaard, Jakob H.
AU - Gorodkin, Jan
AU - Melo, Alba C.M.A.
PY - 2020
Y1 - 2020
N2 - Structural alignments of Ribonucleic acid (RNA) sequences solved by the Sankoff algorithm are computationally expensive and often require constraints to be used in practice. Modern Graphics Processing Units (GPUs) contain more than 1000 cores, which compute in parallel to speed up applications. Here, we present a GPU-based solution to the RNA structural alignment problem that makes use of precalculated base pair probabilities on the individual sequences. We designed and developed an unconstrained version of the Sankoff algorithm, obtaining the optimal result and calculating the entire four-dimension dynamic programming matrix (4D DP). Our approach uses a two-level wavefront strategy to exploit parallelism. The 4D DP matrix is divided in one external matrix (EM) and several internal matrices (IM). We applied wavefront strategies on the EM and IMs in a two-level hierarchical way. At the first level, the wavefront is applied to the EM, calculating the cells that belong to the same diagonal in parallel. In the second level, since each cell in the EM is itself an IM matrix, the cells that belong to the same IM diagonal are calculated in parallel. The results obtained with real RNA sequences show that our GPU version is capable of outperforming a multicore CPU version of the unconstrained version of the Sankoff algorithm. Compared with the CPU-based version running on 32 cores, our approach is able to achieve a speedup of 7.81x on the NVidia Tesla P100. In this case, the execution time was reduced from 6 hours and 18 minutes (32 cores) to 48 minutes and 20 seconds (GPU).
AB - Structural alignments of Ribonucleic acid (RNA) sequences solved by the Sankoff algorithm are computationally expensive and often require constraints to be used in practice. Modern Graphics Processing Units (GPUs) contain more than 1000 cores, which compute in parallel to speed up applications. Here, we present a GPU-based solution to the RNA structural alignment problem that makes use of precalculated base pair probabilities on the individual sequences. We designed and developed an unconstrained version of the Sankoff algorithm, obtaining the optimal result and calculating the entire four-dimension dynamic programming matrix (4D DP). Our approach uses a two-level wavefront strategy to exploit parallelism. The 4D DP matrix is divided in one external matrix (EM) and several internal matrices (IM). We applied wavefront strategies on the EM and IMs in a two-level hierarchical way. At the first level, the wavefront is applied to the EM, calculating the cells that belong to the same diagonal in parallel. In the second level, since each cell in the EM is itself an IM matrix, the cells that belong to the same IM diagonal are calculated in parallel. The results obtained with real RNA sequences show that our GPU version is capable of outperforming a multicore CPU version of the unconstrained version of the Sankoff algorithm. Compared with the CPU-based version running on 32 cores, our approach is able to achieve a speedup of 7.81x on the NVidia Tesla P100. In this case, the execution time was reduced from 6 hours and 18 minutes (32 cores) to 48 minutes and 20 seconds (GPU).
KW - base-pairing probabilities
KW - GPUs
KW - high-performance computing
KW - RNA
KW - Sankoff algorithm
U2 - 10.1002/cpe.5468
DO - 10.1002/cpe.5468
M3 - Journal article
AN - SCOPUS:85070089691
VL - 32
JO - Concurrency Computation Practice and Experience
JF - Concurrency Computation Practice and Experience
SN - 1532-0626
IS - 10
M1 - e5468
ER -
ID: 226493114