Optimization and Performance Analysis of CAT Method for DNA Sequence Similarity Searching and Alignment.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Exponential growth in biological databases necessitates efficient data processing methods.
• Accurate DNA sequence comparison is crucial for understanding gene function and evolutionary relationships.

Purpose of the Study:

• To present a novel pairwise DNA sequence alignment algorithm based on an improved CAT (Context-Aware Transformation) method.
• To enhance the speed and accuracy of DNA sequence matching in large biological datasets.

Main Methods:

• Developed a new version of the CAT method incorporating prior match dependencies and closest neighbor considerations to increase profile uniqueness.
• Implemented a two-stage algorithm: CAT profile calculation and sequence comparison using these profiles.
• Generated CAT profiles as sequence metadata prior to database upload for efficient retrieval.

Main Results:

• The enhanced CAT method demonstrates increased profile uniqueness, reducing collisions.
• Experimental results show significant improvements in speed and efficiency for large-scale DNA sequence alignment compared to traditional methods.
• Performance analysis indicates the CAT algorithm's execution time is stable and unaffected by sequence length, outperforming Knuth-Morris-Pratt in certain aspects.

Conclusions:

• The proposed CAT method-based algorithm provides a highly efficient solution for rapid DNA sequence alignment in large datasets.
• The algorithm achieves enhanced performance with minimal, often negligible, deviation, making it suitable for practical bioinformatics applications.