Title (eng)
Acceleration of exact pairwise protein sequence alignment
Parallel title (deu)
Beschleunigung von exaktem paarweisen Proteinsequenzalignment
Author
Johannes Elias Tüchler
Advisor
Thomas Rattei
Assessor
Thomas Rattei
Abstract (deu)
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 (eng)
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.
Keywords (deu)
BioinformatikProteinsequenzalignmentSmith-WatermanParallelisierungBenchmark
Keywords (eng)
BioinformaticsProtein sequence alignmentSmith-WatermanParallelizationBenchmark
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1627654
rdau:P60550 (deu)
vi, 52 Seiten : Illustrationen
Number of pages
60
Association (deu)
Title (eng)
Acceleration of exact pairwise protein sequence alignment
Parallel title (deu)
Beschleunigung von exaktem paarweisen Proteinsequenzalignment
Author
Johannes Elias Tüchler
Abstract (deu)
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 (eng)
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.
Keywords (deu)
BioinformatikProteinsequenzalignmentSmith-WatermanParallelisierungBenchmark
Keywords (eng)
BioinformaticsProtein sequence alignmentSmith-WatermanParallelizationBenchmark
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1631673
Number of pages
60
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0