Semiglobal Sequence Alignment with Gaps using GPU.



Carroll, Thomas C, Ojiaku, Jude-Thaddeus and Wong, Prudence WH ORCID: 0000-0001-7935-7245
(2019) Semiglobal Sequence Alignment with Gaps using GPU. IEEE/ACM transactions on computational biology and bioinformatics.

[img] Text
GapsMisJournal.pdf - Accepted Version

Download (613kB) | Preview

Abstract

In this paper we consider the pair-wise semiglobal sequence alignment problem with gaps.The problem has been studied before for single gap and bounded number of gaps. For single gap, there is a GPU-based algorithm proposed. In our work we propose a GPU-based algorithm for the bounded number of gaps case, calledGPUGapsMis. We implement the algorithm and compare the performance with the CPU-based algorithm, called CPUGapsMis. The algorithm has two distinct stages: the alignment phase, and the backtrack phase. We investigate several different approaches, in order to determine the most favourable for this problem, by means of a Hybrid model or a wholly-GPU based model, as well as the alignment of single text sequences or multiple text sequences on the GPU at a time. We show that the alignment phase of the algorithm is a good candidate for parallelisation, with peak speedup of 11 times. We show that although the backtracking phase is sequential, it is more beneficial to perform it the GPU, as opposed to returning to the CPU and performing there. When performing both phases on the GPU, GPUGapsMis achieves a peak speedup of 10.4 times against CPUGapsMis. Our data parallel GPU algorithm achieves results which are an improvement on those of an existing GPU data parallel implementation.

Item Type: Article
Depositing User: Symplectic Admin
Date Deposited: 02 May 2019 13:30
Last Modified: 29 Sep 2020 08:21
DOI: 10.1109/tcbb.2019.2914105
URI: http://livrepository.liverpool.ac.uk/id/eprint/3039311