PalCheck

Palindrome Pattern Matching in Biological Sequences

PalCheck performs palindrome pattern matching in DNA, RNA, and protein sequences by identifying indices where a pattern P is pal-equivalent to substrings within a text T.

Key Features:

• Palindrome Pattern Matching: Detects substrings pal-equivalent to pattern P, where two equal-length strings share identical maximal palindrome lengths at each center.
• Online Processing: Supports real-time analysis without requiring complete dataset preloading, enabling processing of large genomic sequences.
• Single and Multiple Pattern Matching: Single-pattern matching requires O(m^2) preprocessing time, O(mn) query time, and O(m^2) space; multiple-pattern matching addresses the online multiple palindrome pattern matching problem with complexity dependent on total pattern length (M), longest pattern length (m_k), and number of occurrences (c).

Scientific Applications:

• Genomic and Proteomic Analysis: Identifies palindromic structures associated with genetic regulation, replication origins, structural motifs, comparative genomics, and evolutionary biology.

Methodology:

Implements algorithmic palindrome detection based on pal-equivalence by comparing maximal palindrome lengths at each possible center to precisely identify palindromic regions in biological sequences.