MOODS

MOODS matches position weight matrices (PWMs) to DNA sequences to detect motif occurrences and assess how sequence variants affect motif sites.

Key Features:

• Advanced Matrix Matching Algorithms: MOODS implements online matching algorithms in C++ that outperform brute-force approaches and can handle scanning hundreds of PWMs against chromosome-sized sequences (e.g., 123 JASPAR matrices across the human genome in ~18 minutes on a standard PC).
• High-Order PWM Support: The software supports first-order Markov and other high-order motif models that capture dependencies between adjacent positions, including dinucleotide and general q-mer dependencies.
• Sequence Variant Integration: MOODS integrates single nucleotide polymorphisms (SNPs), insertions, and deletions into PWM matching workflows to evaluate variant effects on motif sites.
• Multiple-Matrix Filtration: MOODS performs simultaneous searches for multiple matrices using a multiple-matrix filtration algorithm that demonstrates superior performance compared to basic sliding-window algorithms.
• Implementation and Bindings: The package is implemented in C++ and provides bindings for BioPerl and Biopython, and can be used as a standalone C++ library for integration into analysis pipelines.
• Algorithmic Optimizations: The software generalizes classical multipattern matching and applies filtering and superalphabet methods adapted for high-order PWMs to reduce computational complexity.

Scientific Applications:

• Genome-scale motif scanning: Rapid identification of motif occurrences across entire genomes and chromosome-sized sequences.
• Motif discovery and analysis: Prediction of putative sites for learned motifs and analysis of motif models.
• Variant impact analysis: Assessment of how SNPs, insertions, and deletions affect PWM matches and potential regulatory sites.
• Modeling position dependencies: Exploration of dinucleotide, q-mer, and other high-order dependencies within biological sequence motifs.

Methodology:

MOODS generalizes classical multipattern matching to weight matrix matching using online matching algorithms, a multiple-matrix filtration approach, and filtering and superalphabet methods adapted for high-order PWMs; the implementation is in C++.