Alignment-free algorithms can be used to estimate the similarity of biological 
sequences and hence are often applied to the phylogenetic reconstruction of 
genomes. Most of these algorithms rely on comparing the frequency of all the 
distinct substrings of fixed length (k-mers) that occur in the analyzed 
sequences. In this paper, we present Logic Alignment Free (LAF), a method that 
combines alignment-free techniques and rule-based classification algorithms in 
order to assign biological samples to their taxa. This method searches for a 
minimal subset of k-mers whose relative frequencies are used to build 
classification models as disjunctive-normal-form logic formulas (if-then rules). 
We apply LAF successfully to the classification of bacterial genomes to their 
corresponding taxonomy. In particular, we succeed in obtaining reliable 
classification at different taxonomic levels by extracting a handful of rules, 
each one based on the frequency of just few k-mers. State of the art methods to 
adjust the frequency of k-mers to the character distribution of the underlying 
genomes have negligible impact on classification performance, suggesting that 
the signal of each class is strong and that LAF is effective in identifying it.