A fast and efficient algorithm for DNA sequence similarity identification

Area of Science:

• Genomics and Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• DNA sequence similarity analysis is crucial for genome analysis, biological information extraction, and understanding species' evolutionary relationships.
• Alignment-based (AB) methods are NP-hard for long sequences, while alignment-free (AF) methods face limitations in time complexity, memory, precision, and performance.
• Existing AF algorithms often exhibit high computational demands and reduced accuracy on benchmark datasets.

Purpose of the Study:

• To develop a novel, efficient, and accurate alignment-free (AF) algorithm for DNA sequence similarity analysis.
• To overcome the limitations of existing AF methods, specifically high time complexity and memory consumption.
• To enhance the precision and performance of DNA sequence similarity measurement.

Main Methods:

• Developed an AF algorithm utilizing a 2D count matrix, inspired by the Chaos Game Representation (CGR) approach.
• Implemented matrix shrinking by analyzing neighbors and measured similarities using pairwise distance (PD) and phylogenetic tree methods.
• Dynamically selected the value of 'k' and developed an efficient system for locating 'k-mers' within the count matrix.

Main Results:

• Achieved top ranks on two benchmark datasets from AFproject.
• Demonstrated 100% accuracy on the 16S Ribosomal and 18 Eutherian datasets.
• Established a milestone in time complexity and memory consumption compared to existing studies (HEV, HIV-1).

Conclusions:

• The developed AF method is highly effective, efficient, and accurate for DNA sequence similarity measurement.
• The algorithm significantly reduces time complexity and memory usage compared to current approaches.
• This novel method offers a high level of authenticity for DNA sequence similarity analysis.