Rxivist logo

Bit-parallel sequence-to-graph alignment

By Mikko Rautiainen, Veli Mäkinen, Tobias Marschall

Posted 15 May 2018
bioRxiv DOI: 10.1101/323063 (published DOI: 10.1093/bioinformatics/btz162)

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. Here, 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 w over naive algorithms. Our bitvector-based graph alignment algorithm reaches a worst case runtime of O(V + m/w E log(w)) for acyclic graphs and O(V + mE log(w)) for arbitrary cyclic graphs. We apply it to four different types of graphs and observe a speedup between 3.1-fold and 10.1-fold compared to previous algorithms.

Download data

  • Downloaded 945 times
  • Download rankings, all-time:
    • Site-wide: 15,185 out of 103,802
    • In bioinformatics: 2,300 out of 9,474
  • Year to date:
    • Site-wide: 71,047 out of 103,802
  • Since beginning of last month:
    • Site-wide: 39,689 out of 103,802

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)