A survey and evaluations of histogram-based statistics in alignment-free sequence comparison

Area of Science:

• Bioinformatics and Computational Biology
• Genomics and Sequence Analysis

Background:

• Sequence alignment scores are the traditional method for comparing biological sequences.
• Alignment algorithms have quadratic complexity, leading to long execution times.
• Alignment-free statistics have emerged as faster alternatives for sequence comparison.

Purpose of the Study:

• To survey and evaluate various alignment-free k-mer statistics for sequence similarity measurement.
• To identify efficient alternatives to computationally expensive sequence alignment algorithms.
• To assess the performance of different statistics and their combinations in finding similar sequences.

Main Methods:

• Surveyed tens of alignment-free k-mer statistics.
• Evaluated 33 statistics and their multiplicative combinations using k-mer histograms.
• Assessed performance against global alignment scores and identity scores, considering sequence length differences and Earth Mover's distance.

Main Results:

• Most alignment-free statistics effectively identify similar sequences, enabling rapid filtering of dissimilar ones.
• Multiplicative combinations of statistics, especially those including sequence length difference or Earth Mover's distance, correlate highly with identity scores.
• Using shorter k-mer histograms significantly reduces memory and increases speed with comparable performance.
• Simple single statistics are sufficient for next-generation sequencing reads and local alignment applications.

Conclusions:

• Alignment-free statistics provide efficient and rapid alternatives to traditional sequence alignment.
• Specific combinations of statistics enhance accuracy in measuring sequence identity.
• Optimized k-mer usage and simpler statistics offer substantial computational savings for large-scale sequence analysis.