Matching among multiple random sequences

Joseph I. Naus, Ke Ning Sheng

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In searching for strong homologies between multiple nucleic acid or protein sequences, researchers commonly look at fixed-length segments in common to the sequences. Such homologies form the foundation of segment- based algorithms for multiple alignment of protein sequences. The researcher uses settings of 'unusualness of multiple matches' to calibrate the algorithms. In applications where a researcher has found a multiple matching word, statistical significance helps gauge the unusualness of the observed match. Previous approximations for the unusualness of multiple matches are based on large sample theory, and are sometimes quite inaccurate. Section 2 illustrates this inaccuracy, and provides accurate approximations for the probability of a common word in R out of R sequences. Section 3 generalizes the approximation to multiple matching in R out of S sequences. Section 4 describes a more complex approximation that incorporates exact probabilities and yields excellent accuracy; this approximation is useful for checking the simpler approximations over a range of values.

Original languageEnglish (US)
Pages (from-to)483-496
Number of pages14
JournalBulletin of Mathematical Biology
Issue number3
StatePublished - May 1997

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Matching among multiple random sequences'. Together they form a unique fingerprint.

Cite this