Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-29T16:59:16.208Z Has data issue: false hasContentIssue false
  • English
  • Français

Renewal theory for several patterns

Published online by Cambridge University Press:  14 July 2016

Stephen Breen ,
Michael S. Waterman  and
Ning Zhang
Stephen Breen*
Affiliation:
University of Southern California
Michael S. Waterman*
Affiliation:
University of Southern California
Ning Zhang*
Affiliation:
University of Southern California
*
Postal address for all authors: Department of Mathematics, University of Southern California, DRB 306, University Park, Los Angeles, CA 90089–1113, USA.
Postal address for all authors: Department of Mathematics, University of Southern California, DRB 306, University Park, Los Angeles, CA 90089–1113, USA.
Postal address for all authors: Department of Mathematics, University of Southern California, DRB 306, University Park, Los Angeles, CA 90089–1113, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Discrete renewal theory is generalized to study the occurrence of a collection of patterns in random sequences, where a renewal is defined to be the occurrence of one of the patterns in the collection which does not overlap an earlier renewal. The action of restriction enzymes on DNA sequences provided motivation for this work. Related results of Guibas and Odlyzko are discussed.

Keywords

DISCRETE RENEWAL THEORYGENERATING FUNCTIONSDNA SEQUENCES
Type
Short Communications
Information
Journal of Applied Probability , Volume 22 , Issue 1 , March 1985 , pp. 228 - 234
Copyright
Copyright © Applied Probability Trust 1985 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

∗

Work supported by a grant from the System Development Foundation.

References

Boyer, R. S. and Moore, J. S. (1977) A fast string searching algorithm. Comm. ACM 20, 762–772.CrossRefGoogle Scholar
Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. 1, 3rd edn. Wiley, New York.Google Scholar
Guibas, L. J. and Odlyzko, A. M. (1980) Long repetitive patterns in random sequences. Z. Wahrscheinlichkeitsth. 53, 241–262.Google Scholar
Guibas, L. J. and Odlyzko, A. M. (1981) String overlaps, pattern matching, and nontransitive games. J. Combinatorial Theory A 30, 183–208.CrossRefGoogle Scholar
Leslie, R. T. (1967) Recurrent composite events. J. Appl. Prob. 4, 34–61.Google Scholar
Penney, W. (1969) Problem: penney-ante. J. Recreational Math. 2, 241.Google Scholar
Waterman, M. S. (1983) Frequencies of restriction sites. Nucleic Acids Res. 11, 8951–8956.CrossRefGoogle ScholarPubMed
Watson, J. D. (1977) Molecular Biology of the Gene, 3rd edn. W. A. Benjamin, Menlo Park, CA.Google Scholar