PatMaN

PatMaN searches large nucleotide sequence databases for multiple short patterns, allowing approximate matches via predefined gaps and mismatches.

Key Features:

• Multiple Pattern Search: Performs simultaneous searches of numerous short nucleotide patterns.
• Approximate Matching: Allows users to define a specific number of gaps and mismatches to identify near-matches.
• Efficient Search Algorithm: Implements a non-deterministic automata matching algorithm on a keyword tree to enable fast exact matches with predictable scaling as allowed edits increase.
• Flexibility in Query Types: Supports queries that include ambiguity codes.

Scientific Applications:

• Microarray Probe Design: Identifies candidate probe sequences within large datasets, including near-matches relevant for probe selection.
• Genomic Variant Analysis: Detects sequence variations such as single nucleotide polymorphisms (SNPs) and indels by permitting mismatches and gaps in searches.
• Comparative Genomics: Facilitates sequence comparisons across species or strains by accommodating sequence variability.

Methodology:

Matches are found using a non-deterministic automata matching algorithm applied to a keyword tree of the search strings, with support for predefined gaps, mismatches, and ambiguity codes.