Computing Phylo-$k$-Mers
| العنوان: | Computing Phylo-$k$-Mers |
|---|---|
| المؤلفون: | Nikolai Romashchenko, Benjamin Linard, Eric Rivals, Fabio Pardi |
| المصدر: | IEEE/ACM Transactions on Computational Biology and Bioinformatics. :1-9 |
| بيانات النشر: | Institute of Electrical and Electronics Engineers (IEEE), 2023. |
| سنة النشر: | 2023 |
| مصطلحات موضوعية: | FOS: Biological sciences, Applied Mathematics, Genetics, Quantitative Biology - Quantitative Methods, Quantitative Methods (q-bio.QM), Biotechnology |
| الوصف: | 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. |
| تدمد: | 2374-0043 1545-5963 |
| الوصول الحر: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f920dc8e8b54b28e4eac2cc260308d6dTest https://doi.org/10.1109/tcbb.2023.3278049Test |
| حقوق: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....f920dc8e8b54b28e4eac2cc260308d6d |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 23740043 15455963 |
|---|