GibbsST: a Gibbs sampling method for motif discovery with enhanced resistance to local optima.
BACKGROUND
Computational discovery of transcription factor binding sites (TFBS) is a challenging but important problem of bioinformatics. In this study, improvement of a Gibbs sampling based technique for TFBS discovery is attempted through an approach that is widely known, but which has never been investigated before: reduction of the effect of local optima.


RESULTS
To alleviate the vulnerability of Gibbs sampling to local optima trapping, we propose to combine a thermodynamic method, called simulated tempering, with Gibbs sampling. The resultant algorithm, GibbsST, is then validated using synthetic data and actual promoter sequences extracted from Saccharomyces cerevisiae. It is noteworthy that the marked improvement of the efficiency presented in this paper is attributable solely to the improvement of the search method.


CONCLUSIONS
Simulated tempering is a powerful solution for local optima problems found in pattern discovery. Extended application of simulated tempering for various bioinformatic problems is promising as a robust solution against local optima problems.
Shida
Kazuhito
K
TUBERO (Tohoku University Biomedical Engineering Research Organization) 980-8575, Sendai, Japan. shida@cir.tohoku.ac.jp
D000465:Algorithms; D020816:Amino Acid Motifs; D001665:Binding Sites; D011485:Protein Binding; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software; D014157:Transcription Factors / Q000235:genetics*
D014157:Transcription Factors