PatMaN: rapid alignment of short sequences to large databases

Area of Science:

• Bioinformatics
• Computational Biology
• Genomic Data Analysis

Background:

• Large-scale nucleotide sequence databases require efficient search tools.
• Existing methods may not adequately handle sequence variations like gaps and mismatches.
• The need for specialized algorithms to accelerate sequence alignment and retrieval.

Purpose of the Study:

• To introduce PatMaN, a novel command-line program for searching multiple short nucleotide sequences.
• To enable searches with a specified number of gaps and mismatches.
• To provide a tool capable of handling queries with or without ambiguity codes.

Main Methods:

• Implementation of a non-deterministic automata matching algorithm.
• Utilizing a keyword tree structure for search strings.
• Development as a command-line driven program for broad accessibility.

Main Results:

• PatMaN demonstrates short search times for exact nucleotide sequence matches.
• Retrieval time increases exponentially with the number of allowed edits (gaps/mismatches).
• The tool efficiently handles numerous short nucleotide sequences in large databases.

Conclusions:

• PatMaN offers an effective solution for searching nucleotide sequences with variations.
• The program's performance is optimized for exact matches, with predictable performance scaling for inexact matches.
• Availability of C++ source code under GNU GPL facilitates further development and application.