kmacs

kmacs computes alignment-free sequence distances by measuring longest common substrings allowing up to k mismatches to support sequence comparison and phylogenetic reconstruction.

Key Features:

• Alignment-free approach: Uses a generalized average common substring approach that accommodates inexact substring matches rather than relying on exact word matches.
• k-mismatch substrings: Considers longest common substrings with up to k mismatches to capture inexact similarities between sequences.
• Greedy heuristic: Approximates the length of k-mismatch substrings using a greedy heuristic.
• Data structures: Leverages generalized enhanced suffix arrays for rapid computation on large datasets.
• Phylogenetic performance: Evaluated for phylogeny reconstruction and reported to outperform alignment-free methods based on exact word matches, with strong performance on protein sequences and competitive results versus multiple alignment combined with maximum likelihood.
• Implementation: Implemented in C++.

Scientific Applications:

• Phylogenetic reconstruction: Reconstruction of phylogenies from nucleotide or protein sequence data using alignment-free distances.
• Protein sequence comparison: Comparative analysis of protein sequences where inexact matches improve detection of homology.
• Large-scale genomic analyses: Analysis of large genomic datasets when alignment-based methods are computationally constrained.
• Evolutionary biology: Studies of genetic diversity and evolutionary relationships using alignment-free similarity measures.

Methodology:

Computes a generalized average common substring metric based on longest common substrings with up to k mismatches, approximates substring lengths with a greedy heuristic, and implements computation via generalized enhanced suffix arrays.