ALFRED: A Practical Method for Alignment-Free Distance Computation.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Alignment-free methods are crucial for analyzing large biological sequence datasets.
• Average Common Substring (ACS) and its k-mismatch generalization are key alignment-free techniques.
• Existing exact computation methods for generalized ACS are complex and inefficient.

Purpose of the Study:

• To introduce ALFRED, a novel alignment-free distance computation method.
• To address the generalized common substring search problem using efficient exact computation.
• To provide a practical and performant alternative to existing theoretical approaches.

Main Methods:

• ALFRED employs an exact computation strategy for generalized common substring search.
• The algorithm is implemented in C++ for practical application.
• Expected runtime complexity is competitive, offering practical efficiency.

Main Results:

• ALFRED demonstrates ease of implementation and practical usability.
• The method achieves highly competitive theoretical performance.
• In a phylogenetic inference case study, ALFRED accurately reconstructed a primate mitochondrial genome phylogenetic tree.

Conclusions:

• ALFRED offers an efficient and practical solution for alignment-free sequence analysis.
• The method successfully applies to complex tasks like phylogenetic tree reconstruction.
• Source code is freely available, promoting wider adoption and research.