A Gibbs sampler for identification of symmetrically structured, spaced DNA motifs with improved estimation of the signal length.
BACKGROUND
Transcription regulatory protein factors often bind DNA as homo-dimers or hetero-dimers. Thus they recognize structured DNA motifs that are inverted or direct repeats or spaced motif pairs. However, these motifs are often difficult to identify owing to their high divergence. The motif structure included explicitly into the motif recognition algorithm improves recognition efficiency for highly divergent motifs as well as estimation of motif geometric parameters.


RESULTS
We present a modification of the Gibbs sampling motif extraction algorithm, SeSiMCMC (Sequence Similarities by Markov Chain Monte Carlo), which finds structured motifs of these types, as well as non-structured motifs, in a set of unaligned DNA sequences. It employs improved estimators of motif and spacer lengths. The probability that a sequence does not contain any motif is accounted for in a rigorous Bayesian manner. We have applied the algorithm to a set of upstream regions of genes from two Escherichia coli regulons involved in respiration. We have demonstrated that accounting for a symmetric motif structure allows the algorithm to identify weak motifs more accurately. In the examples studied, ArcA binding sites were demonstrated to have the structure of a direct spaced repeat, whereas NarP binding sites exhibited the palindromic structure.


BACKGROUND
The WWW interface of the program, its FreeBSD (4.0) and Windows 32 console executables are available at http://bioinform.genetika.ru/SeSiMCMC
Favorov
A V
AV
Laboratory for Bioinformatics, State Scientific Centre GosNIIGenetika, 1st Dorozhny pr. 1, Moscow, 117545, Russia. favorov@sensi.org
Gelfand
M S
MS
Gerasimova
A V
AV
Ravcheev
D A
DA
Mironov
A A
AA
Makeev
V J
VJ
D000465:Algorithms; D001425:Bacterial Outer Membrane Proteins / Q000235:genetics*; D001483:Base Sequence; D004268:DNA-Binding Proteins / Q000235:genetics*; D029968:Escherichia coli Proteins / Q000235:genetics*; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D012091:Repetitive Sequences, Nucleic Acid / Q000235:genetics; D012097:Repressor Proteins / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D001425:Bacterial Outer Membrane Proteins; D004268:DNA-Binding Proteins; D029968:Escherichia coli Proteins; D012097:Repressor Proteins; C041610:arcA protein, E coli; C081466:narP protein, E coli