Universität Bielefeld Electronic Collections animiertes Foto Universität Bielefeld

Zugang zum Dokument



High Performance Pattern Matching on Heterogeneous Platform

Soroushnia, Shima ; Daneshtalab, Masoud ; Plosila, Juha ; Pahikkala, Tapio ; Liljeberg, Pasi

Journal of Integrative Bioinformatics - JIB (ISSN 1613-4516)



Abstract:
Pattern discovery is one of the fundamental tasks in bioinformatics and pattern recognition is a powerful technique for searching sequence patterns in the biological sequence databases. Fast and high performance algorithms are highly demanded in many applications in bioinformatics and computational molecular biology since the significant increase in the number of DNA and protein sequences expand the need for raising the performance of pattern matching algorithms. For this purpose, heterogeneous architectures can be a good choice due to their potential for high performance and energy efficiency. In this paper we present an efficient implementation of Aho-Corasick (AC) which is a well known exact pattern matching algorithm with linear complexity, and Parallel Failureless Aho-Corasick (PFAC) algorithm which is the massively parallelized version of AC algorithm without failure transitions, on a heterogeneous CPU/GPU architecture. We progressively redesigned the algorithms and data structures to fit on the GPU architecture. Our results on different protein sequence data sets show that the new implementation runs 15 times faster compared to the original implementation of the PFAC algorithm.


Beteiligte Einrichtung: Technische Fakultät, Arbeitsgruppen der Informatik
DDC-Sachgruppe: Datenverarbeitung, Informatik

Zitat-Vorschlag:
Soroushnia, Shima ; Daneshtalab, Masoud ; Plosila, Juha ; Pahikkala, Tapio ; Liljeberg, Pasi  (2014)  High Performance Pattern Matching on Heterogeneous Platform. Journal of Integrative Bioinformatics - JIB (ISSN 1613-4516)

Online-Journal: http://journal.imbio.de/article.php?aid=253
URL: http://biecoll.ub.uni-bielefeld.de/volltexte/2014/5345



 Fragen und Anregungen an: publikationsdienste.ub@uni-bielefeld.de
 Letzte Änderung: 15.2.2011
 Impressum
OPUS-Logo     OAI-zertifiziert      Universitätsbibliothek Bielefeld
OAI-Logo