Limits...
Discriminative motif discovery in DNA and protein sequences using the DEME algorithm.

Redhead E, Bailey TL - BMC Bioinformatics (2007)

Bottom Line: Using artificial data, we show that DEME is more effective than a non-discriminative approach when there are "decoy" motifs or when a variant of the motif is present in the "negative" sequences.With real data, we show that DEME is as good, but not better than non-discriminative algorithms at discovering yeast transcription factor binding motifs.We also show that DEME can find highly informative thermal-stability protein motifs.

View Article: PubMed Central - HTML - PubMed

Affiliation: Institute for Molecular Bioscience, University of Queensland, Brisbane, Qld, 4072 Australia. e.redhead@imb.uq.edu.au

ABSTRACT

Background: Motif discovery aims to detect short, highly conserved patterns in a collection of unaligned DNA or protein sequences. Discriminative motif finding algorithms aim to increase the sensitivity and selectivity of motif discovery by utilizing a second set of sequences, and searching only for patterns that can differentiate the two sets of sequences. Potential applications of discriminative motif discovery include discovering transcription factor binding site motifs in ChIP-chip data and finding protein motifs involved in thermal stability using sets of orthologous proteins from thermophilic and mesophilic organisms.

Results: We describe DEME, a discriminative motif discovery algorithm for use with protein and DNA sequences. Input to DEME is two sets of sequences; a "positive" set and a "negative" set. DEME represents motifs using a probabilistic model, and uses a novel combination of global and local search to find the motif that optimally discriminates between the two sets of sequences. DEME is unique among discriminative motif finders in that it uses an informative Bayesian prior on protein motif columns, allowing it to incorporate prior knowledge of residue characteristics. We also introduce four, synthetic, discriminative motif discovery problems that are designed for evaluating discriminative motif finders in various biologically motivated contexts. We test DEME using these synthetic problems and on two biological problems: finding yeast transcription factor binding motifs in ChIP-chip data, and finding motifs that discriminate between groups of thermophilic and mesophilic orthologous proteins.

Conclusion: Using artificial data, we show that DEME is more effective than a non-discriminative approach when there are "decoy" motifs or when a variant of the motif is present in the "negative" sequences. With real data, we show that DEME is as good, but not better than non-discriminative algorithms at discovering yeast transcription factor binding motifs. We also show that DEME can find highly informative thermal-stability protein motifs. Binaries for the stand-alone program DEME is free for academic use and is available at http://bioinformatics.org.au/deme/

Show MeSH

Related in: MedlinePlus

Effect of the Bayesian motif prior on local search accuracy. The plot shows the average accuracy of the motif models discovered by conjugate gradient alone as a function of A, the total pseudocounts applied when deriving the PSFM from W. The starting point for conjugate gradient is derived from the consensus sequence for the planted motif using a value of B = 0.25. All experiments use the Random Negative Problem and DNA sequences and the OOPS data model. Each data point is the arithmetic mean (± standard error) for 100 independent experiments. Panel a shows results using FM motifs and panel b shows results using PSFM motifs.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2194741&req=5

Figure 2: Effect of the Bayesian motif prior on local search accuracy. The plot shows the average accuracy of the motif models discovered by conjugate gradient alone as a function of A, the total pseudocounts applied when deriving the PSFM from W. The starting point for conjugate gradient is derived from the consensus sequence for the planted motif using a value of B = 0.25. All experiments use the Random Negative Problem and DNA sequences and the OOPS data model. Each data point is the arithmetic mean (± standard error) for 100 independent experiments. Panel a shows results using FM motifs and panel b shows results using PSFM motifs.

Mentions: Using the Bayesian motif prior results in a substantial improvement in the accuracy of the motif models learned by conjugate gradient on DNA datasets containing planted FM motifs (Fig. 2a). With FM motifs, values of A (refer to Eqn. 11) smaller than eight resulted in less accurate prediction of planted motifs sites (lower training set PC) and much less accurate prediction of motif sites and sequence class (lower test set PC and test set ACC, respectively). This is a strong indication that conjugate gradient over-fits the data when the motifs are FM-like. The extreme case is when A = 0, which is similar to the Sharan-Segal use of conjugate gradient. In this case, PC for the training set for FM motifs is 0.86 while PC for the test set is 0.49 and test set ACC is 0.67, compared with training set PC of 0.90, test set PC of 0.91 and ACC of 0.92 when the optimal value of the motif prior is applied. Similarly, training and test set PC for PSFM motifs are 0.49 and 0.46 respectively and test set ACC is 0.68, compared with training set PC of 0.72, test set PC of 0.69 and ACC of 0.78 for the optimal motif prior weight.


Discriminative motif discovery in DNA and protein sequences using the DEME algorithm.

Redhead E, Bailey TL - BMC Bioinformatics (2007)

Effect of the Bayesian motif prior on local search accuracy. The plot shows the average accuracy of the motif models discovered by conjugate gradient alone as a function of A, the total pseudocounts applied when deriving the PSFM from W. The starting point for conjugate gradient is derived from the consensus sequence for the planted motif using a value of B = 0.25. All experiments use the Random Negative Problem and DNA sequences and the OOPS data model. Each data point is the arithmetic mean (± standard error) for 100 independent experiments. Panel a shows results using FM motifs and panel b shows results using PSFM motifs.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2194741&req=5

Figure 2: Effect of the Bayesian motif prior on local search accuracy. The plot shows the average accuracy of the motif models discovered by conjugate gradient alone as a function of A, the total pseudocounts applied when deriving the PSFM from W. The starting point for conjugate gradient is derived from the consensus sequence for the planted motif using a value of B = 0.25. All experiments use the Random Negative Problem and DNA sequences and the OOPS data model. Each data point is the arithmetic mean (± standard error) for 100 independent experiments. Panel a shows results using FM motifs and panel b shows results using PSFM motifs.
Mentions: Using the Bayesian motif prior results in a substantial improvement in the accuracy of the motif models learned by conjugate gradient on DNA datasets containing planted FM motifs (Fig. 2a). With FM motifs, values of A (refer to Eqn. 11) smaller than eight resulted in less accurate prediction of planted motifs sites (lower training set PC) and much less accurate prediction of motif sites and sequence class (lower test set PC and test set ACC, respectively). This is a strong indication that conjugate gradient over-fits the data when the motifs are FM-like. The extreme case is when A = 0, which is similar to the Sharan-Segal use of conjugate gradient. In this case, PC for the training set for FM motifs is 0.86 while PC for the test set is 0.49 and test set ACC is 0.67, compared with training set PC of 0.90, test set PC of 0.91 and ACC of 0.92 when the optimal value of the motif prior is applied. Similarly, training and test set PC for PSFM motifs are 0.49 and 0.46 respectively and test set ACC is 0.68, compared with training set PC of 0.72, test set PC of 0.69 and ACC of 0.78 for the optimal motif prior weight.

Bottom Line: Using artificial data, we show that DEME is more effective than a non-discriminative approach when there are "decoy" motifs or when a variant of the motif is present in the "negative" sequences.With real data, we show that DEME is as good, but not better than non-discriminative algorithms at discovering yeast transcription factor binding motifs.We also show that DEME can find highly informative thermal-stability protein motifs.

View Article: PubMed Central - HTML - PubMed

Affiliation: Institute for Molecular Bioscience, University of Queensland, Brisbane, Qld, 4072 Australia. e.redhead@imb.uq.edu.au

ABSTRACT

Background: Motif discovery aims to detect short, highly conserved patterns in a collection of unaligned DNA or protein sequences. Discriminative motif finding algorithms aim to increase the sensitivity and selectivity of motif discovery by utilizing a second set of sequences, and searching only for patterns that can differentiate the two sets of sequences. Potential applications of discriminative motif discovery include discovering transcription factor binding site motifs in ChIP-chip data and finding protein motifs involved in thermal stability using sets of orthologous proteins from thermophilic and mesophilic organisms.

Results: We describe DEME, a discriminative motif discovery algorithm for use with protein and DNA sequences. Input to DEME is two sets of sequences; a "positive" set and a "negative" set. DEME represents motifs using a probabilistic model, and uses a novel combination of global and local search to find the motif that optimally discriminates between the two sets of sequences. DEME is unique among discriminative motif finders in that it uses an informative Bayesian prior on protein motif columns, allowing it to incorporate prior knowledge of residue characteristics. We also introduce four, synthetic, discriminative motif discovery problems that are designed for evaluating discriminative motif finders in various biologically motivated contexts. We test DEME using these synthetic problems and on two biological problems: finding yeast transcription factor binding motifs in ChIP-chip data, and finding motifs that discriminate between groups of thermophilic and mesophilic orthologous proteins.

Conclusion: Using artificial data, we show that DEME is more effective than a non-discriminative approach when there are "decoy" motifs or when a variant of the motif is present in the "negative" sequences. With real data, we show that DEME is as good, but not better than non-discriminative algorithms at discovering yeast transcription factor binding motifs. We also show that DEME can find highly informative thermal-stability protein motifs. Binaries for the stand-alone program DEME is free for academic use and is available at http://bioinformatics.org.au/deme/

Show MeSH
Related in: MedlinePlus