Print Email Facebook Twitter GPU Acceleration of DNA Alignment Algorithms of Long Reads for DNA Assembly Title GPU Acceleration of DNA Alignment Algorithms of Long Reads for DNA Assembly Author Qiu, Tongdong (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Al-Ars, Zaid (mentor) Degree granting institution Delft University of Technology Programme Computer Engineering Date 2018-12-11 Abstract Third generation sequencing machines produce reads with tens of thousands of base pairs.To perform de novo assembly, all reads must be compared with every other read to find overlaps.Finding overlaps with the optimal Smith-Waterman is not feasible, since the complexity of Smith-Waterman is quadratic with the length of the reads.Heuristics are designed be faster, but are not guaranteed to give the optimal solution.Two heuristic DNA aligners are Daligner and Darwin.Daligner uses an edit graph based algorithm that has an O(ND) complexity, where N is the read length, and D the number of differences between the two aligned reads.Darwin creates overlapping tiles to search promising areas of the Smith-Waterman matrix, and is empirically shown to be optimal.This work implements these algorithms on a GPU, and compares the two with respect to sensitivity and specificity.Daligner is not suitable for GPU acceleration, but Darwin has shown speedup of 109x vs 8 CPU threads, using a Tesla K40.The speedup increases to 148x when the Smith-Waterman scores are not calculated.Despite large speedups for Darwin, Daligner is 2-6x faster than Darwin, and slightly more sensitive and specific.An advantage of Darwin is that is produces generally longer overlaps, calculates the Smith-Waterman score, and is able to report the aligned sequences, where Daligner only reports the start and end of the overlap. Subject GPUDNAAlignmentAccelerationDalignerDarwinCUDA To reference this document use: http://resolver.tudelft.nl/uuid:589a0a2c-cfec-434c-8740-651b5ae5cc40 Part of collection Student theses Document type master thesis Rights © 2018 Tongdong Qiu Files PDF MSc_Thesis_Tong_Dong_Qiu.pdf 5.55 MB Close viewer /islandora/object/uuid:589a0a2c-cfec-434c-8740-651b5ae5cc40/datastream/OBJ/view