Method for calculation of probability of matching a bounded regular expression in a random data string.
A method is presented for determining within strict bounds the probability of matching a regular expression with a match start point in a given section of a random data string. The method in general requires time and space exponential in the number of optional characters in the regular expression, but in practice was used to determine bounds for probabilities of matching all the ProSite patterns without difficulty.
D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D004247:DNA / Q000737:chemistry*; D016208:Databases, Factual; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated; D011336:Probability; D011506:Proteins / Q000737:chemistry*; D011897:Random Allocation
D011506:Proteins; D004247:DNA