CPSSM

CPSSM identifies consecutive-position scoring matrices induced from protein sequences and uses a dynamic programming pattern-matching algorithm to detect these coding-region patterns in genomic DNA, accommodating intronic gaps and large sequences to improve open reading frame detection and gene finding.

Key Features:

• Pattern Structure Definition: Defines a genomic pattern structure representing patterns induced from protein sequences and serving as a replacement for traditional protein patterns and profiles in genome analysis.
• Dynamic Programming Algorithm: Employs a dynamic programming–based pattern matching algorithm for identification, discovery, and searching of CPSSMs in genomic sequences.
• Intronic Gaps and Large Sequence Support: Algorithm modified to accommodate intronic gaps and large genomic sequences for comprehensive pattern detection.
• Empirical Validation: Tested on the Saccharomyces cerevisiae genome and the human genome, reporting a 132% increase in true positives in yeast, a tenfold increase in humans, and zero false negatives.

Scientific Applications:

• Open Reading Frame Detection: Improves detection of open reading frames by identifying coding-region patterns correlated with protein motifs.
• Gene Finding: Assists gene finding by detecting genomic patterns induced from proteins within genomic sequences.

Methodology:

Represents protein-induced genomic patterns as consecutive-position scoring matrices and applies a dynamic programming pattern-matching algorithm modified to accommodate intronic gaps and large genomic sequences, with empirical evaluation on Saccharomyces cerevisiae and human genomes.