PatSearch: a pattern matcher software that finds functional elements in nucleotide and protein sequences and assesses their statistical significance

Motivation: The identification of sequence patterns involved in gene regula tion and expression is a major challenge in molecular biology. In this pape r we describe a novel algorithm and the software for searching nucleotide a nd protein sequences for complex nucleotide patterns including potential se condary structure Elements, also allowing for mismatches/mispairings below a user fixed threshold, and assessing the statistical significance of their occurrence through a Markov chain simulation. Results: The application of the proposed algorithm allowed the identificati on of some functional elements, such as the Iron Responsive Element, the Hi stone stem-loop structure and the Selenocysteine Insertion Sequence, locate d in the mRNA untranslated regions of post-transcriptionally regulated gene s with the assessment of sensitivity and selectivity of the searching metho d.