k -nonical space: sketching with reverse complements
Bioinformatics · 2024
DOI: 10.1093/bioinformatics/btae629 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2024. Verfasst von Guillaume Marçais und 2 weiteren Autor:innen. Beteiligte Einrichtung: Ray and Stephanie Lane Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA 15213, United States. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NHGRI NIH HHS, US National Science Foundation.
Abstract (Originalsprache)
Motivation Sequences equivalent to their reverse complements (i.e. double-stranded DNA) have no analogue in text analysis and non-biological string algorithms. Despite this striking difference, algorithms designed for computational biology (e.g. sketching algorithms) are designed and tested in the same way as classical string algorithms. Then, as a post-processing step, these algorithms are adapted to work with genomic sequences by folding a k-mer and its reverse complement into a single sequence: The canonical representation (k-nonical space). Results The effect of using the canonical representation with sketching methods is understudied and not understood. As a first step, we use context-free sketching methods to illustrate the potentially detrimental effects of using canonical k-mers with string algorithms not designed to accommodate for them. In particular, we show that large stretches of the genome (“sketching deserts”) are undersampled or entirely skipped by context-free sketching methods, effectively making these genomic regions invisible to subsequent algorithms using these sketches. We provide empirical data showing these effects and develop a theoretical framework explaining the appearance of sketching deserts. Finally, we propose two schemes to accommodate for these effects: (i) a new procedure that adapts existing sketching methods to k-nonical space and (ii) an optimization procedure to directly design new sketching methods for k-nonical space. Availability and implementation The code used in this analysis is available under a permissive license at https://github.com/Kingsford-Group/mdsscope.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Autor:innen und Institutionen
- Ray and Stephanie Lane Computational Biology Department, Carnegie Mellon University, Pittsburgh, PA 15213, United States.
ORCID-Profile: Guillaume Marçais
Förderung
- NHGRI NIH HHS
- US National Science Foundation
Zitieren
APA
Marçais, G., Elder, C. S., & Kingsford, C. (2024). k -nonical space: sketching with reverse complements. Bioinformatics. https://doi.org/10.1093/bioinformatics/btae629
Vancouver
Marçais G, Elder CS, Kingsford C. k -nonical space: sketching with reverse complements. Bioinformatics. 2024. doi:10.1093/bioinformatics/btae629
BibTeX
@article{Marais2024,
author = {Marçais, Guillaume and Elder, C S and Kingsford, Carl},
title = {k -nonical space: sketching with reverse complements},
journal = {Bioinformatics},
year = {2024},
doi = {10.1093/bioinformatics/btae629}
}
EUVIMED