EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Label-guided seed-chain-extend alignment on annotated De Bruijn graphs

Harun Mustafa iD, Mikhail Karasikov iD, Nika Mansouri Ghiasi iD, Gunnar Rätsch, André Kahles iD

Bioinformatics · 2024

DOI: 10.1093/bioinformatics/btae226 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2024. Verfasst von Harun Mustafa und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, ETH Zurich, Zurich, 8092, Switzerland. Hauptthemen laut MEDLINE: Algorithms, Sequence Alignment. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Swiss National Research Programme, SNSF, Monique Dornonville de la Cour Foundation.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation Exponential growth in sequencing databases has motivated scalable De Bruijn graph-based (DBG) indexing for searching these data, using annotations to label nodes with sample IDs. Low-depth sequencing samples correspond to fragmented subgraphs, complicating finding the long contiguous walks required for alignment queries. Aligners that target single-labelled subgraphs reduce alignment lengths due to fragmentation, leading to low recall for long reads. While some (e.g. label-free) aligners partially overcome fragmentation by combining information from multiple samples, biologically irrelevant combinations in such approaches can inflate the search space or reduce accuracy. Results We introduce a new scoring model, ‘multi-label alignment’ (MLA), for annotated DBGs. MLA leverages two new operations: To promote biologically relevant sample combinations, ‘Label Change’ incorporates more informative global sample similarity into local scores. To improve connectivity, ‘Node Length Change’ dynamically adjusts the DBG node length during traversal. Our fast, approximate, yet accurate MLA implementation has two key steps: a single-label seed-chain-extend aligner (SCA) and a multi-label chainer (MLC). SCA uses a traditional scoring model adapting recent chaining improvements to assembly graphs and provides a curated pool of alignments. MLC extracts seed anchors from SCAs alignments, produces multi-label chains using MLA scoring, then finally forms multi-label alignments. We show via substantial improvements in taxonomic classification accuracy that MLA produces biologically relevant alignments, decreasing average weighted UniFrac errors by 63.1%–66.8% and covering 45.5%–47.4% (median) more long-read query characters than state-of-the-art aligners. MLAs runtimes are competitive with label-combining alignment and substantially faster than single-label alignment. Availability and implementation The data, scripts, and instructions for generating our results are available at https://github.com/ratschlab/mla.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsSequence AlignmentSoftwareComputational BiologySequence Analysis, DNADatabases, Genetic

Autor:innen und Institutionen

  • Department of Computer Science, ETH Zurich, Zurich, 8092, Switzerland.
  • Biomedical Informatics Group, University Hospital Zurich, Zurich, 8091, Switzerland.
  • Biomedical Informatics, Swiss Institute of Bioinformatics, Zurich, 8092, Switzerland.
  • Department of Information Technology and Electrical Engineering, ETH Zurich, Zurich, 8092, Switzerland.
  • ETH AI Center, Zurich, 8092, Switzerland.
  • Department of Biology, ETH Zurich, Zurich, 8093, Switzerland.

ORCID-Profile: Harun Mustafa, Mikhail Karasikov, Nika Mansouri Ghiasi, André Kahles

Förderung

  • Swiss National Research Programme
  • SNSF
  • Monique Dornonville de la Cour Foundation
  • Personalized Health and Related Technologies
  • Transition Postdoc Fellowship

Zitieren

APA

Mustafa, H., Karasikov, M., Mansouri Ghiasi, N., Rätsch, G., & Kahles, A. (2024). Label-guided seed-chain-extend alignment on annotated De Bruijn graphs. Bioinformatics. https://doi.org/10.1093/bioinformatics/btae226

Vancouver

Mustafa H, Karasikov M, Mansouri Ghiasi N, Rätsch G, Kahles A. Label-guided seed-chain-extend alignment on annotated De Bruijn graphs. Bioinformatics. 2024. doi:10.1093/bioinformatics/btae226

BibTeX
@article{Mustafa2024,
  author = {Mustafa, Harun and Karasikov, Mikhail and Mansouri Ghiasi, Nika and Rätsch, Gunnar and Kahles, André},
  title = {Label-guided seed-chain-extend alignment on annotated De Bruijn graphs},
  journal = {Bioinformatics},
  year = {2024},
  doi = {10.1093/bioinformatics/btae226}
}
Kostenlos starten →