A novel optimal multi-pattern matching method with wildcards for DNA sequence.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• DNA sequence alignment is crucial for identifying gene families and has broad applications in biomedical engineering, biotechnology, and health informatics.
• Pattern matching for DNA sequences presents a fundamental challenge in these scientific domains.

Purpose of the Study:

• To develop an optimal multi-pattern matching algorithm specifically designed for DNA sequences, incorporating wildcard characters.
• To enhance the efficiency and accuracy of DNA sequence analysis through advanced pattern matching techniques.

Main Methods:

• The proposed method involves packing patterns and utilizing a sliding window approach over packed text.
• The algorithm efficiently matches packed patterns against a sliding window as it traverses the DNA sequence.

Main Results:

• Performance evaluation using three distinct datasets demonstrated the algorithm's superior efficiency compared to existing methods.
• The algorithm's operational proximity to machine language contributes to its enhanced performance.

Conclusions:

• Both theoretical analysis and experimental results confirm that the proposed method surpasses current state-of-the-art techniques.
• The developed algorithm is particularly effective for DNA sequence analysis and pattern matching applications.