qPMS9

qPMS9 implements a parallel exact quorum Planted Motif Search (qPMS) algorithm to identify length-ℓ motifs with up to d mismatches across DNA and protein sequences, requiring motif occurrences in at least a quorum of input strings.

Key Features:

• Motif Identification: Detects short recurring motifs in DNA—including open reading frames, gene promoter elements, intron/exon splicing sites, small RNAs (sRNAs), RNA degradation signals, and alternative splicing sites—and in proteins for domain identification, protease cleavage sites, signal peptide recognition, protein interaction motifs, protein degradation elements, protein trafficking elements, and short functional motifs.
• Algorithmic Approach: Solves the (ℓ, d) Planted Motif Search (PMS) problem by receiving a set of n strings and integers ℓ and d and finding all length-ℓ sequences M whose occurrences in the input strings differ from M by at most d positions.
• Quorum PMS: Extends PMS with a quorum formulation that requires motifs to appear in at least q% of the input strings rather than in every string.
• Parallel Processing: Leverages parallel computation to accelerate the exact search and improve runtime on large DNA and protein datasets.
• Challenging Instances: Capable of solving difficult DNA instances characterized by parameters such as (ℓ, d) = (28, 12) and (30, 13).

Scientific Applications:

• Genomics: Discovery of regulatory elements and structural features in DNA sequences, including promoters, splicing signals, sRNAs, and RNA degradation signals.
• Proteomics: Identification of protein domains, protease cleavage sites, signal peptides, and short motifs involved in protein interactions, degradation, and trafficking to elucidate protein function and interaction networks.

Methodology:

Performs a parallel exact qPMS search across multiple biological sequences incorporating quorum-based criteria to require motif presence in a specified proportion of input strings.