Rxivist logo

Distance Indexing and Seed Clustering in Sequence Graphs

By Xian Chang, Jordan Eizenga, Adam M. Novak, Jouni Sirén, Benedict Paten

Posted 23 Dec 2019
bioRxiv DOI: 10.1101/2019.12.20.884924 (published DOI: 10.1093/bioinformatics/btaa446)

Graph representations of genomes are capable of expressing more genetic variation and can therefore better represent a population than standard linear genomes. However, due to the greater complexity of genome graphs relative to linear genomes, some functions that are trivial on linear genomes become more difficult in genome graphs. Calculating distance is one such function that is simple in a linear genome but much more complicated in a graph context. In read mapping algorithms, distance calculations are commonly used in a clustering step to determine if seed alignments could belong to the same mapping. Clustering algorithms are a bottleneck for some mapping algorithms due to the cost of repeated distance calculations. We have developed an algorithm for quickly calculating the minimum distance between positions on a sequence graph using a minimum distance index. We have also developed an algorithm that uses the distance index to cluster seeds on a graph. We demonstrate that our implementations of these algorithms are efficient and practical to use for mapping algorithms.

Download data

  • Downloaded 373 times
  • Download rankings, all-time:
    • Site-wide: 52,193 out of 106,159
    • In bioinformatics: 5,937 out of 9,474
  • Year to date:
    • Site-wide: 22,529 out of 106,159
  • Since beginning of last month:
    • Site-wide: 76,539 out of 106,159

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


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