A greedy strategy for finding motifs from yes-no examples.
We define a motif as an expression Z1.Z2...Zn with sets Z1, Z2,..., Zn of strings in a specified family omega called the type. This notion can capture the most of the motifs in PROSITE as well as regular pattern languages. A greedy strategy is developed for finding such motifs with ambiguity just from positive and negative examples by exploiting the probabilistic argument. This paper concentrates on describing the idea of the greedy algorithm with its underlying theory. Its experimental results on splicing sites and E. coli promoters are also presented.
Tateishi
E
E
Department of Information Systems, Kyushu University, Kasuga, Japan. tateishi@rifis.kyushu-u.ac.jp
Miyano
S
S
D000465:Algorithms; D017398:Alternative Splicing; D000595:Amino Acid Sequence; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D019992:Databases as Topic; D004926:Escherichia coli / Q000235:genetics; D008957:Models, Genetic; D011336:Probability; D011401:Promoter Regions, Genetic; D011506:Proteins / Q000737:chemistry / Q000235:genetics; D012984:Software
D011506:Proteins