A greedy alignment-free distance estimator for phylogenetic inference.

Area of Science:

• Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• Alignment-free sequence comparison is crucial for large-scale phylogenetic inference.
• K-mer based methods dominate, but the average common substring (ACS) approach is gaining prominence.
• Generalized ACS methods allow mismatches in common substrings for enhanced accuracy.

Purpose of the Study:

• Introduce ALFRED-G, a greedy alignment-free distance estimator for phylogenetic tree reconstruction.
• Develop and apply a novel heuristic for efficiently computing common string lengths with mismatches.
• Evaluate ALFRED-G's performance against existing algorithms.

Main Methods:

• Developed ALFRED-G, a greedy algorithm based on the generalized ACS approach.
• Implemented a new heuristic for calculating common string lengths with allowed mismatches.
• Applied the heuristic to phylogenetic tree reconstruction.

Main Results:

• ALFRED-G reconstructs phylogenetic tree topologies with accuracy comparable or superior to the kmacs heuristic.
• The algorithm achieves highly competitive speeds in performance evaluations.
• Demonstrated effectiveness on real biological sequence datasets.

Conclusions:

• ALFRED-G is an effective alignment-free heuristic for evolutionary distance estimation.
• The algorithm is implemented in C++ and available in the open-source ALFRED software package.
• ALFRED-G provides a valuable tool for phylogenetic analysis.