An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences.
Statistical methodology for the identification and characterization of protein binding sites in a set of unaligned DNA fragments is presented. Each sequence must contain at least one common site. No alignment of the sites is required. Instead, the uncertainty in the location of the sites is handled by employing the missing information principle to develop an "expectation maximization" (EM) algorithm. This approach allows for the simultaneous identification of the sites and characterization of the binding motifs. The reliability of the algorithm increases with the number of fragments, but the computations increase only linearly. The method is illustrated with an example, using known cyclic adenosine monophosphate receptor protein (CRP) binding sites. The final motif is utilized in a search for undiscovered CRP binding sites.
Biometrics Laboratory, Wadsworth Center for Laboratories and Research, New York State Department of Health, Albany 12201.
C E
CE
Lawrence
A A
AA
Reilly
D000465:Algorithms; D001483:Base Sequence; D001665:Binding Sites; D004268:DNA-Binding Proteins / Q000235:genetics; D004926:Escherichia coli / Q000235:genetics; D007256:Information Systems; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D011953:Receptors, Cyclic AMP / Q000235:genetics* / Q000378:metabolism; D013223:Statistics as Topic
D004268:DNA-Binding Proteins; D011953:Receptors, Cyclic AMP