Detailansicht
Acceleration of exact pairwise protein sequence alignment
Johannes Elias Tüchler
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Bioinformatik
Betreuer*in
Thomas Rattei
DOI
10.25365/thesis.73098
URN
urn:nbn:at:at-ubw:1-29454.44412.578939-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das paarweise Alignment von Proteinsequenzen ist eine zentrale Aufgabe der Bioinformatik, das dazu beiträgt, biologische Verwandtschaft zwischen Proteinsequenzen zu erkennen. Alignments können mit schnellen Heuristiken oder mit dem exakten Smith-Waterman-Algorithmus durchgeführt werden, welcher garantiert das optimale lokale Alignment zwischen zwei Sequenzen findet. Aufgrund der quadratischen Zeitkomplexität des Smith-Waterman-Algorithmus, sind für große Proteinvergleiche schnelle Implementierungen erforderlich. Daher wurden für den Smith-Waterman-Algorithmus verschiedene Parallelisierungsmethoden und Anpassungen für Hardwarebeschleuniger (GPU, FPGA, Xeon Phi) entwickelt. In dieser Arbeit wird die Geschwindigkeit einiger der schnellsten Smith-Waterman-Methoden für CPU und GPU unter verschiedenen Parametereinstellungen verglichen. Das zentrale Ergebnis ist, dass die schnellste CPU-Methode SWIPE die schnellste GPU-Methode CUDASW++ 3 auf einem vollen Rechenknoten mit 24 CPU-Kernen und 6 GPUs übertrifft. Im SIMAP-Projekt (Similarity Matrix of Proteins) werden Ähnlichkeiten zwischen Proteinen kompletter Genome mit Hilfe des Smith-Waterman-Algorithmus mit compositional score adjustment berechnet. Aufgrund der hohen Laufzeit des SIMAP-Workflows, werden in dieser Arbeit Möglichkeiten zur Verringerung der Laufzeit untersucht. Durch die Erstellung eines Laufzeitprofils für den SIMAP-Workflow wurde eine ineffiziente Kompilierung eines Skripts festgestellt und nach Optimierung des Kompilierungsprozesses konnte die Laufzeit auf etwa ein Drittel reduziert werden.
Abstract
(Englisch)
The pairwise alignment of protein sequences is a central task in bioinformatics, which helps to identify biological relationships between protein sequences. Alignments can be performed with fast heuristics or with the exact Smith-Waterman algorithm, which is guaranteed to find the optimal local alignment between two sequences. Because of the quadratic time complexity of the Smith-Waterman algorithm, fast implementations are needed for large-scale protein similarity searches. Therefore, various parallelization approaches and adaptions for hardware accelerators (GPU, FPGA, Xeon Phi) have been developed for the Smith-Waterman algorithm. In this work, the performance of some of the fastest CPU and GPU Smith-Waterman methods are compared under various parameter settings. The main result is that the fastest CPU method SWIPE outperforms the fastest GPU method CUDASW++ 3 on a full compute node with 24 CPU cores and 6 GPUs. In the SIMAP (Similarity Matrix of Proteins) project, similarities between proteins of complete genomes are computed using the Smith-Waterman algorithm with compositional score adjustment. Because of the high runtime of the SIMAP workflow, in this work, possibilities of reducing the runtime are explored. Runtime profiling of the SIMAP workflow identified an inefficient compilation of a script and by optimizing the compilation process the runtime could be reduced to about a third.
Schlagwörter
Schlagwörter
(Deutsch)
Bioinformatik Proteinsequenzalignment Smith-Waterman Parallelisierung Benchmark
Schlagwörter
(Englisch)
Bioinformatics Protein sequence alignment Smith-Waterman Parallelization Benchmark
Autor*innen
Johannes Elias Tüchler
Haupttitel (Englisch)
Acceleration of exact pairwise protein sequence alignment
Paralleltitel (Deutsch)
Beschleunigung von exaktem paarweisen Proteinsequenzalignment
Publikationsjahr
2023
Umfangsangabe
vi, 52 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Thomas Rattei
Klassifikationen
42 Biologie > 42.13 Molekularbiologie ,
54 Informatik > 54.80 Angewandte Informatik
AC Nummer
AC16773428
Utheses ID
65944
Studienkennzahl
UA | 066 | 875 | |