Chaining for accurate alignment of erroneous long reads to acyclic variation graphs
Bioinformatics · 2023
DOI: 10.1093/bioinformatics/btad460 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2023. Verfasst von Jun Ma und 4 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, University of Helsinki, 00014 Helsinki, Finland. Hauptthemen laut MEDLINE: High-Throughput Nucleotide Sequencing, Algorithms. Die Arbeit wurde bisher 20-mal zitiert (Crossref) und nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council, European Union’s Horizon 2020 research and innovation program.
Abstract (Originalsprache)
Motivation Aligning reads to a variation graph is a standard task in pangenomics, with downstream applications such as improving variant calling. While the vg toolkit [Garrison et al. (Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat Biotechnol 2018;36:875–9)] is a popular aligner of short reads, GraphAligner [Rautiainen and Marschall (GraphAligner: rapid and versatile sequence-to-graph alignment. Genome Biol 2020;21:253–28)] is the state-of-the-art aligner of erroneous long reads. GraphAligner works by finding candidate read occurrences based on individually extending the best seeds of the read in the variation graph. However, a more principled approach recognized in the community is to co-linearly chain multiple seeds. Results We present a new algorithm to co-linearly chain a set of seeds in a string labeled acyclic graph, together with the first efficient implementation of such a co-linear chaining algorithm into a new aligner of erroneous long reads to acyclic variation graphs, GraphChainer. We run experiments aligning real and simulated PacBio CLR reads with average error rates 15% and 5%. Compared to GraphAligner, GraphChainer aligns 12–17% more reads, and 21–28% more total read length, on real PacBio CLR reads from human chromosomes 1, 22, and the whole human pangenome. On both simulated and real data, GraphChainer aligns between 95% and 99% of all reads, and of total read length. We also show that minigraph [Li et al. (The design and construction of reference pangenome graphs with minigraph. Genome Biol 2020;21:265–19.)] and minichain [Chandra and Jain (Sequence to graph alignment using gap-sensitive co-linear chaining. In: Proceedings of the 27th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2023). Springer, 2023, 58–73.)] obtain an accuracy of <60% on this setting. Availability and implementation GraphChainer is freely available at https://github.com/algbio/GraphChainer. The datasets and evaluation pipeline can be reached from the previous address.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Department of Computer Science, University of Helsinki, 00014 Helsinki, Finland.
ORCID-Profile: Manuel Cáceres, Veli Mäkinen, Alexandru I Tomescu
Förderung
- European Research Council
- European Union’s Horizon 2020 research and innovation program
Zitieren
APA
Ma, J., Cáceres, M., Salmela, L., Mäkinen, V., & Tomescu, A. I. (2023). Chaining for accurate alignment of erroneous long reads to acyclic variation graphs. Bioinformatics. https://doi.org/10.1093/bioinformatics/btad460
Vancouver
Ma J, Cáceres M, Salmela L, Mäkinen V, Tomescu AI. Chaining for accurate alignment of erroneous long reads to acyclic variation graphs. Bioinformatics. 2023. doi:10.1093/bioinformatics/btad460
BibTeX
@article{Ma2023,
author = {Ma, Jun and Cáceres, Manuel and Salmela, Leena and Mäkinen, Veli and Tomescu, Alexandru I},
title = {Chaining for accurate alignment of erroneous long reads to acyclic variation graphs},
journal = {Bioinformatics},
year = {2023},
doi = {10.1093/bioinformatics/btad460}
}
EUVIMED