Finding motifs from all sequences with and without binding sites

Motivation: Finding common patterns, motifs, from a set of promoter regions of coregulated genes is an important problem in molecular biology. Most existing motif-finding algorithms consider a set of sequences bound by the transcription factor as the only input. However, we can get better results by considering sequences that are not bound by the transcription factor as an additional input. Results: First, instead of using the simple hyper-geometric analysis, we propose to calculate the likelihood based on a more precise probabilistic analysis which considers motif length, sequence length and number of binding sites as input parameters for testing whether motif is found. Second, we adopt an heuristic algorithm bases on our analysis to find motifs. For the simulated and real datasets, our algorithm ALSE compares favorably against common motif-finding programs such as SeedSearch and MEME in all cases and performs very well, especially when each input sequence contains more than one binding site. © 2006 Oxford University Press.link_to_subscribed_fulltex