Compressed Pattern Matching in DNA Sequences Using Multithreaded Technology

Author

Lin, Piyuan ; Liu, Shaopeng ; Zhang, Lixia ; Huang, Peijie

Author_Institution

Coll. of Inf., South China Agric. Univ., Guangzhou, China

fYear

2009

fDate

11-13 June 2009

Firstpage

1

Lastpage

4

Abstract

Compressed pattern matching on large DNA sequences data is very important in bioinformatics. In this paper, in order to improve the performance by searching pattern in parallel time, multithreaded programming technique is used. Then, two novel multithreaded algorithms are proposed, named MTd-BM and MTd-Horspool. The first one is a mutation of d-BM algorithm, which is based on Boyer-Moore method. And the second one is designed in the similitude of MTd-BM, but using Horspool method as its foundation. The experimental results show that these two algorithms are nearly 2 times faster than the d-BM algorithm for long DNA pattern (length>50). Moreover, compression of DNA sequences gives a guaranteed space saving of 75%.

Keywords

DNA; bioinformatics; data compression; molecular biophysics; pattern matching; Boyer-Moore method; DNA sequences; MTd-BM; MTd-Horspool; bioinformatics; compressed pattern matching; multithreaded algorithms; multithreaded programming technique; searching pattern; Bioinformatics; DNA; Educational institutions; Encoding; Genetic mutations; Informatics; Parallel programming; Pattern matching; Sequences; Space technology;

fLanguage

English

Publisher

ieee

Conference_Titel

Bioinformatics and Biomedical Engineering , 2009. ICBBE 2009. 3rd International Conference on

Conference_Location

Beijing

Print_ISBN

978-1-4244-2901-1

Electronic_ISBN

978-1-4244-2902-8

Type

conf

DOI

10.1109/ICBBE.2009.5162550

Filename

5162550