GRISOTTO: A greedy approach to improve combinatorial algorithms for motif discovery with prior knowledge

Area of Science:

• Computational biology
• Bioinformatics
• Genomics

Background:

• Position-specific priors (PSP) enhance motif discovery algorithms like EM and Gibbs samplers.
• Existing methods utilize PSP from single sources (e.g., conservation, DNA stability, nucleosome positioning).
• Prior information has not been integrated with combinatorial motif discovery algorithms, nor have combined priors been studied.

Purpose of the Study:

• To extend the RISOTTO combinatorial algorithm for motif discovery by incorporating prior information.
• To develop a method (GRISOTTO) that combines PSP from multiple sources to guide a greedy search procedure.
• To evaluate the effectiveness of combined priors in improving motif discovery accuracy.

Main Methods:

• Post-processing the output of the RISOTTO combinatorial algorithm using a greedy procedure guided by prior information.
• Combining position-specific priors from diverse sources into a unified scoring criterion.
• Evaluating the GRISOTTO method on 156 yeast TF ChIP-chip sequence-sets and mouse ChIP-seq data.

Main Results:

• GRISOTTO demonstrates accuracy comparable to twelve state-of-the-art methods even without combined priors.
• Incorporating combined priors significantly enhances GRISOTTO's accuracy beyond current state-of-the-art approaches.
• PSP improve GRISOTTO's motif retrieval from mouse ChIP-seq data, showing cross-technology and cross-species applicability.

Conclusions:

• Integrating prior information via post-processing of combinatorial algorithms yields highly effective motif discovery.
• Combining multiple sources of prior information offers greater benefits than using individual priors separately.
• The GRISOTTO method provides a robust framework for enhanced motif discovery across different biological contexts.