SIMD PARALLELIZATION OF THE WORDUP ALGORITHM FOR DETECTING STATISTICALLY SIGNIFICANT PATTERNS IN DNA-SEQUENCES

The development of new techniques in sequencing nucleic acids has prod uced a great amount of sequence data and has led to the discovery of n ew relationships. In this paper, we study a method for parallelizing t he algorithm WORDUP, which detects the presence of statistically signi ficant patterns in DNA sequences. WORDUP implements an efficient metho d to identify the presence of statistically significant oligomers in a nonhomologous group of sequences. It is based on a modified version o f the Boyer-Moore algorithm, which is one of the fastest algorithms fo r string matching available in the literature. The aim of the parallel version of WORDUP presented here is to speed up the computational tim e and allow the analysis of a greater set of longer nucleotide sequenc es, which is usually impractical with sequential algorithms.