Pattern matching between two non-aligned random sequences.
Given two independent sequences of letters, we seek the probability distribution of the length of the longest matching word. This word can be in different positions in the two sequences and we consider both perfect and nearly perfect matching. We derive bounds and approximations for the probability and compare them with other bounds and approximations. The results can be applied to DNA sequences in molecular biology and generalized matching between two independent random sequences.
Sheng
K N
KN
Department of Statistics, Rutgers, State University of New Jersey, New Brunswick 08903.
Naus
J I
JI
D001483:Base Sequence; D004247:DNA / Q000737:chemistry*; D008433:Mathematics; D015233:Models, Statistical; D010363:Pattern Recognition, Automated; D011336:Probability; D011897:Random Allocation
D004247:DNA