Show simple item record

dc.contributor.authorLi, Connor
dc.date.accessioned2021-03-01T17:56:16Z
dc.date.available2021-03-01T17:56:16Z
dc.identifier.urihttp://hdl.handle.net/10464/15019
dc.description.abstractDue to the many advances made in designing algorithms, especially the ones used in bioinformatics, it is becoming harder and harder to improve their efficiencies. Therefore, hardware acceleration using General-Purpose computing on Graphics Processing Unit has become a popular choice. BWA-MEM is an important part of the BWA software package for sequence mapping. Because of its high speed and accuracy, we choose to parallelize the popular short DNA sequence mapper. BWA has been a prevalent single node tool in genome alignment, and it has been widely studied for acceleration for a long time since the first version of the BWA package came out. This thesis presents the Big Data GPGPU distributed BWA-MEM, a tool that combines GPGPU acceleration and distributed computing. The four hardware parallelization techniques used are CPU multi-threading, GPU paralleled, CPU distributed, and GPU distributed. The GPGPU distributed software typically outperforms other parallelization versions. The alignment is performed on a distributed network, and each node in the network executes a separate GPGPU paralleled version of the software. We parallelize the chain2aln function in three levels. In Level 1, the function ksw\_extend2, an algorithm based on Smith-Waterman, is parallelized to handle extension on one side of the seed. In Level 2, the function chain2aln is parallelized to handle chain extension, where all seeds within the same chain are extended. In Level 3, part of the function mem\_align1\_core is parallelized for extending multiple chains. Due to the program's complexity, the parallelization work was limited at the GPU version of ksw\_extend2 parallelization Level 3. However, we have successfully combined Spark with BWA-MEM and ksw\_extend2 at parallelization Level 1, which has shown that the proposed framework is possible. The paralleled Level 3 GPU version of ksw\_extend2 demonstrated noticeable speed improvement with the test data set.en_US
dc.language.isoengen_US
dc.publisherBrock Universityen_US
dc.subjectBWA-MEMen_US
dc.subjectGPGPUen_US
dc.subjectBig Dataen_US
dc.subjectSparken_US
dc.titleIMPROVING BWA-MEM WITH GPU PARALLEL COMPUTINGen_US
dc.typeElectronic Thesis or Dissertationen_US
dc.degree.nameM.Sc. Computer Scienceen_US
dc.degree.levelMastersen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.degree.disciplineFaculty of Mathematics and Scienceen_US


Files in this item

Thumbnail
Name:
Brock_Li_Connor_2021.pdf
Size:
6.098Mb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record