Repository logo

MR-CUDASW - GPU accelerated Smith-Waterman algorithm for medium-length (meta)genomic data

dc.contributor.advisorKusalik, Anthony J.en_US
dc.contributor.committeeMemberMcQuillan, Ianen_US
dc.contributor.committeeMemberKeil, Marken_US
dc.contributor.committeeMemberRueda, Luis G.en_US
dc.creatorMuhammadzadeh, Amiren_US 2014en_US
dc.description.abstractThe idea of using a graphics processing unit (GPU) for more than simply graphic output purposes has been around for quite some time in scientific communities. However, it is only recently that its benefits for a range of bioinformatics and life sciences compute-intensive tasks has been recognized. This thesis investigates the possibility of improving the performance of the overlap determination stage of an Overlap Layout Consensus (OLC)-based assembler by using a GPU-based implementation of the Smith-Waterman algorithm. In this thesis an existing GPU-accelerated sequence alignment algorithm is adapted and expanded to reduce its completion time. A number of improvements and changes are made to the original software. Workload distribution, query profile construction, and thread scheduling techniques implemented by the original program are replaced by custom methods specifically designed to handle medium-length reads. Accordingly, this algorithm is the first highly parallel solution that has been specifically optimized to process medium-length nucleotide reads (DNA/RNA) from modern sequencing machines (i.e. Ion Torrent). Results show that the software reaches up to 82 GCUPS (Giga Cell Updates Per Second) on a single-GPU graphic card running on a commodity desktop hardware. As a result it is the fastest GPU-based implemen- tation of the Smith-Waterman algorithm tailored for processing medium-length nucleotide reads. Despite being designed for performing the Smith-Waterman algorithm on medium-length nucleotide sequences, this program also presents great potential for improving heterogeneous computing with CUDA-enabled GPUs in general and is expected to make contributions to other research problems that require sensitive pairwise alignment to be applied to a large number of reads. Our results show that it is possible to improve the performance of bioinformatics algorithms by taking full advantage of the compute resources of the underlying commodity hardware and further, these results are especially encouraging since GPU performance grows faster than multi-core CPUs.en_US
dc.subjectSequence Alignmenten_US
dc.subjectSmith-Waterman Algorithmen_US
dc.subjectGPU Computingen_US
dc.subjectSequence Assemblyen_US
dc.titleMR-CUDASW - GPU accelerated Smith-Waterman algorithm for medium-length (meta)genomic dataen_US
dc.type.materialtexten_US Scienceen_US Scienceen_US of Saskatchewanen_US of Science (M.Sc.)en_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
4.26 MB
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
1011 B
Plain Text