Digital Commons Network^™

Fast Bitwise Pattern-Matching Algorithm For Dna Sequences On Modern Hardware, Giyasetti̇n Özcan, Osman Sabri̇ Ünsal

Turkish Journal of Electrical Engineering and Computer Sciences

We introduce a fast bitwise exact pattern-matching algorithm, which speeds up short-length pattern searches on large-sized DNA databases. Our contributions are two-fold. First, we introduce a novel exact matching algorithm designed specifically for modern processor architectures. Second, we conduct a detailed comparative performance analysis of bitwise exact matching algorithms by utilizing hardware counters. Our algorithmic technique is based on condensed bitwise operators and multifunction variables, which minimize register spills and instruction counts during searches. In addition, the technique aims to efficiently utilize CPU branch predictors and to ensure smooth instruction flow through the processor pipeline. Analyzing letter occurrence probability estimations …