Mathematics – Probability
Scientific paper
2007-04-24
Mathematics
Probability
Final version to appear in the Journal of Mathematical Biology
Scientific paper
RNA motifs typically consist of short, modular patterns that include base pairs formed within and between modules. Estimating the abundance of these patterns is of fundamental importance for assessing the statistical significance of matches in genomewide searches, and for predicting whether a given function has evolved many times in different species or arose from a single common ancestor. In this manuscript, we review in an integrated and self-contained manner some basic concepts of automata theory, generating functions and transfer matrix methods that are relevant to pattern analysis in biological sequences. 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. The applications we present focus on the concept of synchronization of automata, as well as automata used to search for a finite number of keywords (including sets of patterns generated according to base pairing rules) in a general text.
Betterton M. D.
Knight Rob
Lladser Manuel
No associations
LandOfFree
Multiple pattern matching: A Markov chain approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multiple pattern matching: A Markov chain approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple pattern matching: A Markov chain approach will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-225772