We present a new algorithm, BOBRO, for prediction of cis regulatory motifs in a given set of promoter sequences. The algorithm substantially improves the prediction accuracy and extends the scope of applicability of the existing programs based on two key new ideas: (a) we developed a highly effective method for reliably assessing the possibility for each position in each given promoter being the (approximate) start of a conserved sequence motif among the given promoters, facilitating accurate identification of each conserved motif by finding maximal cliques in a graph defined over sequence positions with high possibilities being the starts of conserved motifs; and (b) we developed a highly reliable way for recognition of actual motifs from the identified cliques based on the concept of motif closure. We have compared the prediction performance of BOBRO with those by five popular prediction programs on large- scale data sets in a systematic manner, and found that BOBRO outperforms these programs by a subsatntial margin across all the test datasets.