  RNA motifs typically consist of short, modular patterns that include basepairs formed within and between modules. Estimating the abundance of thesepatterns is of fundamental importance for assessing the statisticalsignificance of matches in genomewide searches, and for predicting whether agiven function has evolved many times in different species or arose from asingle common ancestor. In this manuscript, we review in an integrated andself-contained manner some basic concepts of automata theory, generatingfunctions and transfer matrix methods that are relevant to pattern analysis inbiological sequences. We formalize, in a general framework, the concept ofMarkov chain embedding to analyze patterns in random strings produced by amemoryless source. This conceptualization, together with the capability ofautomata to recognize complicated patterns, allows a systematic analysis ofproblems related to the occurrence and frequency of patterns in random strings.The applications we present focus on the concept of synchronization ofautomata, as well as automata used to search for a finite number of keywords(including sets of patterns generated according to base pairing rules) in ageneral text.
We formalize, in a general framework, the concept of Markov chain embedding to analyze patterns in random strings produced by a memoryless source. This conceptualization, together with the capability of automata to recognize complicated patterns, allows a systematic analysis of problems related to the occurrence and frequency of patterns in random strings.