GRISOTTO: A greedy approach to improve combinatorial algorithms for motif discovery with prior knowledge
See where this sits in the topic map →Summary AI-generated
- TL;DR
- We introduce GRISOTTO, a new method that combines combinatorial motif discovery algorithms with position-specific prior information to significantly improve accuracy.
- Problem
- While position-specific priors (PSPs) derived from sources like orthologous conservation and DNA stability have successfully boosted probabilistic motif discovery algorithms like expectation-maximization and Gibbs samplers, they had not yet been applied to combinatorial algorithms. Furthermore, previous methods only used these priors independently without studying the benefits of combining them.
- Method
- We extend the combinatorial motif discovery algorithm RISOTTO by adding a post-processing greedy search procedure. This procedure is guided by a scoring criterion that can integrate position-specific priors from multiple sources.
- Results
- Evaluated on 156 yeast transcription factor ChIP-chip datasets, GRISOTTO matched the accuracy of twelve state-of-the-art approaches without combined priors, and considerably outperformed them when using combined priors. Additional tests on mouse ChIP-seq data showed that PSPs also improve motif retrieval in higher eukaryotes and different technologies.
- Contributions
- We developed GRISOTTO, successfully integrated position-specific priors into combinatorial motif discovery, and demonstrated the effectiveness of combining priors from multiple sources.
- Limitations
- Not specified in the abstract.
- Takeaways
- Post-processing combinatorial algorithm outputs with prior information creates an efficient and effective motif discovery method, and combining priors from multiple sources yields even greater benefits.
- Applications
- The algorithm can be applied to biological sequence data for motif discovery across different technologies, such as ChIP-chip and ChIP-seq, and in higher eukaryotes like mice.
- Topics
- Algorithms for Molecular Biology
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
BACKGROUND: Position-specific priors (PSP) have been used with success to boost EM and Gibbs sampler-based motif discovery algorithms. PSP information has been computed from different sources, including orthologous conservation, DNA duplex stability, and nucleosome positioning. The use of prior information has not yet been used in the context of combinatorial algorithms. Moreover, priors have been used only independently, and the gain of combining priors from different sources has not yet been studied. RESULTS: We extend RISOTTO, a combinatorial algorithm for motif discovery, by post-processing its output with a greedy procedure that uses prior information. PSP's from different sources are combined into a scoring criterion that guides the greedy search procedure. The resulting method, called GRISOTTO, was evaluated over 156 yeast TF ChIP-chip sequence-sets commonly used to benchmark prior-based motif discovery algorithms. Results show that GRISOTTO is at least as accurate as other twelve state-of-the-art approaches for the same task, even without combining priors. Furthermore, by considering combined priors, GRISOTTO is considerably more accurate than the state-of-the-art approaches for the same task. We also show that PSP's improve GRISOTTO ability to retrieve motifs from mouse ChiP-seq data, indicating that the proposed algorithm can be applied to data from a different technology and for a higher eukaryote. CONCLUSIONS: The conclusions of this work are twofold. First, post-processing the output of combinatorial algorithms by incorporating prior information leads to a very efficient and effective motif discovery method. Second, combining priors from different sources is even more beneficial than considering them separately.