EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

k -nonical space: sketching with reverse complements

Guillaume Marçais iD, C S Elder, Carl Kingsford

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsComputational BiologyGenomicsSequence Analysis, DNADNAHumans

Substanzen

DNA

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}
}
Kostenlos starten →