Hybrid Gibbs-sampling algorithm for challenging motif discovery: GibbsDST.
The difficulties of computational discovery of transcription factor binding sites (TFBS) are well represented by (l, d) planted motif challenge problems. Large d problems are difficult, particularly for profile-based motif discovery algorithms. Their local search in the profile space is apparently incompatible with subtle motifs and large mutational distances between the motif occurrences. Herein, an improved profile-based method called GibbsDST is described and tested on (15,4), (12,3), and (18,6) challenging problems. For the first time for a profile-based method, its performance in motif challenge problems is comparable to that of Random Projection. It is noteworthy that GibbsDST outperforms a pattern-based algorithm, WINNOWER, in some cases. Effectiveness of GibbsDST using a biological dataset as an example and its possible extension to more realistic evolution models are also introduced.
Shida
Kazuhito
K
Tohoku University Biomedical Engineering Research Organization, Sendai 980-8575, Japan. shida@cir.tohoku.ac.jp
D000465:Algorithms; D020816:Amino Acid Motifs / Q000235:genetics*; D001665:Binding Sites; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D016384:Consensus Sequence; D004926:Escherichia coli / Q000235:genetics; D016680:Genome, Bacterial; D008957:Models, Genetic; D015233:Models, Statistical; D009154:Mutation; D010363:Pattern Recognition, Automated; D011485:Protein Binding; D018085:Regulon; D017386:Sequence Homology, Amino Acid; D014157:Transcription Factors / Q000235:genetics*
D014157:Transcription Factors