Pattern matching between two non-aligned random sequences

Ke Ning Sheng, Joseph I. Naus

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1143-1162
Number of pages20
JournalBulletin of Mathematical Biology
Issue number6
StatePublished - Nov 1994

All Science Journal Classification (ASJC) codes

  • Agricultural and Biological Sciences(all)
  • Environmental Science(all)
  • Mathematics(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Neuroscience(all)
  • Pharmacology
  • Computational Theory and Mathematics
  • Immunology


Dive into the research topics of 'Pattern matching between two non-aligned random sequences'. Together they form a unique fingerprint.

Cite this