ArticleBioinformatics (Oxford, England)2019
Bit-parallel sequence-to-graph alignment.
Article in Bioinformatics (Oxford, England), 2019. The graph could read no effect estimate from its abstract, so it casts no vote on the map. Cited by 33 papers.
What it found
Each row is one number read from the abstract, on the scale the paper reported it, with its interval. Left of the dashed line favours the treatment, right favours the comparator. Under each row is the sentence it came from. New to these charts? A ten-minute tutorial.
The abstract states no effect estimate the extractor could read, or names no intervention and outcome on the map, so this paper lights no cell and moves no belief. It is still indexed, cited and linked below.
The trial behind it
Trials whose registry record cites this paper, or whose number appears in the abstract. A trial that started after this paper was published is citing it as background, not reporting it.
Neither the registry nor the abstract names a trial number. If this is a trial report, that itself is worth knowing.
Who cites it
33 citing papers in PubMed.
- Theseus: fast and optimal affine-gap sequence-to-graph alignment.Bioinformatics (Oxford, England) · 2026Article
- De Bruijn graphs for pangenomics: in-depth performance benchmarking of de Bruijn graph-based tools for read mapping.Briefings in bioinformatics · 2026Article
- Building and applying pangenome references to capture genetic diversity.Nature reviews. Genetics · 2026Review
- Article
- Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe.Research square · 2025Article
- Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe.bioRxiv : the preprint server for biology · 2025Article
- Panaln: indexing pangenome for read alignment.Bioinformatics (Oxford, England) · 2025Article
- A survey of sequence-to-graph mapping algorithms in the pangenome era.Genome biology · 2025Review
- Haplotype-aware sequence alignment to pangenome graphs.Genome research · 2024Article
- NIPT-PG: empowering non-invasive prenatal testing to learn from population genomics through an incremental pan-genomic approach.Briefings in bioinformatics · 2024Article
- RecGraph: recombination-aware alignment of sequences to variation graphs.Bioinformatics (Oxford, England) · 2024Article
- Pangenome comparison via ED strings.Frontiers in bioinformatics · 2024Article
- Chaining for accurate alignment of erroneous long reads to acyclic variation graphs.Bioinformatics (Oxford, England) · 2023Article
- Computational graph pangenomics: a tutorial on data structures and their applications.Natural computing · 2022Article
- VariantStore: an index for large-scale genomic variant search.Genome biology · 2021Article
- STRONG: metagenomics strain resolution on assembly graphs.Genome biology · 2021Article
- Profiling variable-number tandem repeat variation across populations using repeat-pangenome graphs.Nature communications · 2021Article
- An international virtual hackathon to build tools for the analysis of structural variants within species ranging from coronaviruses to vertebrates.F1000Research · 2021Article
- The design and construction of reference pangenome graphs with minigraph.Genome biology · 2020Article
- GraphAligner: rapid and versatile sequence-to-graph alignment.Genome biology · 2020Article
Corrections and comments
PubMed lists nothing against this paper. Absence here is not a guarantee, only a check that was made.
Authors and funding
3 authors.
Funding
No grant is acknowledged in the PubMed record.
Abstract
motivationGraphs 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.
resultsWe 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.
Indexed as
Identifiers
What OpenQuestion holds
Registered trials
Read under generation 80e0d062 · epoch 390. Bibliography from PubMed, PubMed Central and OpenAlex; grants from NIH RePORTER; trial links from ClinicalTrials.gov; estimates, votes and beliefs from the OpenQuestion graph.