GADEM

GADEM performs unbiased de novo motif discovery in large-scale genome-wide datasets such as Chromatin Immunoprecipitation (ChIP) experiments by combining spaced dyads with genetic algorithms and expectation-maximization probabilistic modeling.

Key Features:

• De novo motif discovery: Performs unbiased motif discovery in large-scale genome-wide datasets, including ChIP experiments.
• Candidate word prioritization: Selects overrepresented candidate words of four to six nucleotides from input sequence data.
• Spaced dyads and PWMs: Constructs spaced dyads from prioritized words and converts them into starting position weight matrices (PWMs).
• Genetic algorithm with EM: Integrates a genetic algorithm (GA) with an expectation-maximization (EM) algorithm to iteratively refine PWMs.
• Entropy-based motif scoring: Evolves a population of spaced dyads toward motifs characterized by statistically significant entropy scores.
• Scalability and runtime: Handles datasets up to ~10,000 binding sites and datasets ranging from 0.5 to over 13 million nucleotides with reported run times of 5 to 96 hours.
• Motif diversity: Identifies approximately 15–30 distinct motifs per dataset spanning motif lengths of 6–40 bp.
• Comparative performance: Demonstrated performance on par with MEME in evaluations using 500 simulated ChIP sequence sets with embedded P53 binding sites.

Scientific Applications:

• Genome-wide ChIP motif discovery: De novo identification of DNA motifs from Chromatin Immunoprecipitation (ChIP) datasets.
• Recovery of known transcription factor motifs: Identification of expected motifs such as P53 without prior motif information.
• Benchmarking and simulation studies: Comparative evaluation of motif-finding performance against algorithms such as MEME using simulated ChIP sequences.

Methodology:

GADEM prioritizes overrepresented 4–6 nucleotide candidate words, constructs spaced dyads from these candidates and converts them into starting position weight matrices (PWMs), then applies a genetic algorithm integrated with an expectation-maximization (EM) algorithm to iteratively refine PWMs toward motifs with statistically significant entropy scores.