Methods for calculating the probabilities of finding patterns in sequences

This paper describes the use of probability-generating functionsfor calculating the probabilities of finding motifs in nucleicacid and protein sequences. Equations and algorithms are givenfor calculating the probabilities associated with nine differentways of defining motifs. Comparisons are made with searchesof random sequences. A higher level structure-the pattern-isdefined as a list of motifs. A pattern also specifies the permittedranges of spacing allowed between its constituent motifs. Equationsfor calculating the expected numbers of matches to patternsare given. Received on March 1, 1988; accepted on September 30, 1988