Résumé
Phylogenetically informed k-mers, or phylo-k-mers for short, are k-mers that
are predicted to appear within a given genomic region at predefined locations
of a fixed phylogeny. Given a reference alignment for this genomic region and
assuming a phylogenetic model of sequence evolution, we can compute a
probability score for any given k-mer at any given tree node. The k-mers with
sufficiently high probabilities can later be used to perform alignment-free
phylogenetic classification of new sequences-a procedure recently proposed for
the phylogenetic placement of metabarcoding reads and the detection of novel
virus recombinants. While computing phylo-k-mers, we need to consider large
numbers of k-mers at each tree node, which warrants the development of
efficient enumeration algorithms. We consider a formal definition of the
problem of phylo-k-mer computation: How to efficiently find all k-mers whose
probability lies above a user-defined threshold for a given tree node? We
describe and analyze algorithms for this problem, relying on branch-and-bound
and divideand-conquer techniques. We exploit the redundancy of adjacent windows
of the alignment and the structure of the probability matrix to save on
computation. Besides computational complexity analyses, we provide an empirical
evaluation of the relative performance of their implementations on real-world
and simulated data. The divide-and-conquer algorithms, which to the best of our
knowledge are novel, are found to be clear improvements over the
branch-and-bound approach, especially when a large number of phylo-k-mers are
found.