Label-guided seed-chain-extend alignment on annotated De Bruijn graphs
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.
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)
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}
}
EUVIMED