An alignment-free heuristic for fast sequence comparisons with applications to phylogeny reconstruction.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Alignment-free sequence comparison is crucial for phylogenetic tree construction.
• The average common substring measure (ACS) and its k-mismatch variant (ACS_k) are effective similarity measures.
• Exact ACS_k computation is time-prohibitive for large datasets, necessitating heuristic approximations.

Purpose of the Study:

• To develop a novel, linear-time heuristic for approximating ACS_k.
• To improve upon existing linear-time greedy heuristics for ACS_k approximation.
• To evaluate the heuristic's accuracy, runtime, and applicability in phylogeny reconstruction.

Main Methods:

• Developed a novel linear-time algorithm to approximate ACS_k.
• Evaluated the algorithm's performance on four real-world DNA and protein sequence datasets.
• Compared the heuristic's accuracy and runtime against previously published methods.

Main Results:

• The proposed heuristic achieves a faster runtime than exact ACS_k computation.
• The algorithm provides a closer approximation to exact ACS_k values compared to prior linear-time heuristics.
• Demonstrated comparable or superior accuracy for phylogeny reconstruction on real datasets.

Conclusions:

• The novel method offers a superior approximation of ACS_k for alignment-free biological sequence comparison.
• The algorithm achieves highly competitive speeds, making it practical for large-scale analyses.
• The implementation in Rust is publicly available for use.