Bit-parallel sequence-to-graph alignment
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
Motivation: Graphs are commonly used to represent sets of sequences. Either edges or nodes can be labeled by sequences, so that each path in the graph spells a concatenated sequence. Examples include graphs to represent genome assemblies, such as string graphs and de Bruijn graphs, and graphs to represent a pan-genome and hence the genetic variation present in a population. Being able to align sequencing reads to such graphs is a key step for many analyses and its applications include genome assembly, read error correction and variant calling with respect to a variation graph. Results: We generalize two linear sequence-to-sequence algorithms to graphs: the Shift-And algorithm for exact matching and Myers’ bitvector algorithm for semi-global alignment. These linear algorithms are both based on processing w sequence characters with a constant number of operations, where w is the word size of the machine (commonly 64), and achieve a speedup of up to w over naive algorithms. For a graph with |V| nodes and |E| edges and a sequence of length m, our bitvector-based graph alignment algorithm reaches a worst case runtime of O(|V|+⌈mw⌉|E| log w) for acyclic graphs and O(|V|+m|E| log w) for arbitrary cyclic graphs. We apply it to five different types of graphs and observe a speedup between 3-fold and 20-fold compared with a previous (asymptotically optimal) alignment algorithm. Availability and implementation: https://github.com/maickrau/GraphAligner Supplementary information: Supplementary data are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Minimap2: Pairwise alignment for nucleotide sequences
Li, H. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty191 · Cited by 14,807
Multi-platform discovery of haplotype-resolved structural variation in human genomes
Chaisson, M. J. P., Sanders, A. D., Zhao, X., Malhotra, A., Porubsky, D., Rausch, T., Gardner, E. J., Rodriguez, O. L., Guo, L., Collins, R. L., et al. (2019) · Nature Communications · doi:10.1038/s41467-018-08148-z · Cited by 891
Self-citationVariation graph toolkit improves read mapping by representing genetic variation in the reference
Garrison, E., Sirén, J., Novak, A. M., Hickey, G., Eizenga, J. M., Dawson, E. T., Jones, W., Garg, S., Markello, C., Lin, M. F., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4227 · Cited by 821
How to apply de Bruijn graphs to genome assembly
Compeau, P. E. C., Pevzner, P. A., & Tesler, G. (2011) · Nature Biotechnology · doi:10.1038/nbt.2023 · Cited by 673
Cited by
The design and construction of reference pangenome graphs with minigraph
Li, H., Feng, X., & Chu, C. (2020) · Genome Biology · doi:10.1186/s13059-020-02168-z · Cited by 455
Eizenga, J. M., Novak, A. M., Sibbesen, J. A., Heumos, S., Ghaffaari, A., Hickey, G., Chang, X., Seaman, J. D., Rounthwaite, R., Ebler, J., et al. (2020) · Annual Review of Genomics and Human Genetics · doi:10.1146/annurev-genom-120219-080406 · Cited by 320
Self-citationPan-genomics in the human genome era
Sherman, R. M., & Salzberg, S. L. (2020) · Nature Reviews Genetics · doi:10.1038/s41576-020-0210-7 · Cited by 359
GraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Self-citationTechnology dictates algorithms: recent developments in read alignment
Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., et al. (2021) · Genome Biology · doi:10.1186/s13059-021-02443-7 · Cited by 144
Metadata
- Authors
- Rautiainen, M., Mäkinen, V., & Marschall, T.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2019-03-09
- Volume
- 35
- Issue
- 19
- Pages
- 3599-3607
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2952746707
- Cited by
- 72
- References
- 4
- FWCI
- 5.18
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.