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.