Background rareness-based iterative multiple sequence alignment algorithm for regulatory element detection.
BACKGROUND
Experimental methods capable of generating sets of co-regulated genes have become commonplace, however, recognizing the regulatory motifs responsible for this regulation remains difficult. As a result, computational detection of transcription factor binding sites in such data sets has been an active area of research. Most approaches have utilized either Gibbs sampling or greedy strategies to identify such elements in sets of sequences. These existing methods have varying degrees of success depending on the strength and length of the signals and the number of available sequences. We present a new deterministic iterative algorithm for regulatory element detection based on a Markov chain background. As in other methods, sequences in the entire genome and the training set are taken into account in order to discriminate against commonly occurring signals and produce patterns, which are significant in the training set.


RESULTS
The results of the algorithm compare favorably with existing tools on previously known and newly compiled data sets. The iteration based search appears rather rigorous, not only finding the binding sites, but also showing how the binding site stands out from genomic background. The approach used to score the results is critical and a discussion of various scoring schemes and options is also presented. Benchmarking of several methods shows that while most tools are good at detecting strong signals, Gibbs sampling algorithms give inconsistent results when the regulatory element signal becomes weak. A Markov chain based background model alleviates the drawbacks of MAP (maximum a posteriori log likelihood) scores.


BACKGROUND
Available on request from the authors.


BACKGROUND
Data and the results presented in this paper are available on the web at http://compbio.ornl.gov/mira/index.html
Narasimhan
Chandrasegaran
C
Life Sciences Division, Oak Ridge National Laboratory, PO Box 3480, Oak Ridge, TN 37830, USA.
LoCascio
Philip
P
Uberbacher
Edward
E
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics; D001665:Binding Sites; D020869:Gene Expression Profiling / Q000379:methods*; D005786:Gene Expression Regulation / Q000235:genetics*; D005809:Genes, Regulator / Q000235:genetics*; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D017434:Protein Structure, Tertiary; D015203:Reproducibility of Results; D012441:Saccharomyces cerevisiae / Q000235:genetics / Q000378:metabolism; D029701:Saccharomyces cerevisiae Proteins / Q000235:genetics / Q000378:metabolism; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*
D029701:Saccharomyces cerevisiae Proteins