Rxivist logo

Rxivist combines preprints from bioRxiv with data from Twitter to help you find the papers being discussed in your field. Currently indexing 65,094 bioRxiv papers from 288,491 authors.

Locality sensitive hashing for the edit distance

By Guillaume Marçais, Dan DeBlasio, Prashant Pandey, Carleton Kingsford

Posted 29 Jan 2019
bioRxiv DOI: 10.1101/534446 (published DOI: 10.1093/bioinformatics/btz354)

Motivation: Sequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality Sensitive Hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have an alignment from those that may have an alignment. Therefore, an LSH reduces in the overall computational requirement while not introducing many false negatives (i.e., omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of k-mers and do not take into account the relative ordering of k-mers in sequences. And due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming distance are used as a proxy. Results: We present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is not only sensitive to the k-mer contents of the sequences but also to the relative order of the k-mers in the sequences. We present theoretical guarantees of the OMH as a gapped LSH.

Download data

  • Downloaded 1,053 times
  • Download rankings, all-time:
    • Site-wide: 6,866 out of 65,094
    • In bioinformatics: 1,257 out of 6,446
  • Year to date:
    • Site-wide: 1,576 out of 65,094
  • Since beginning of last month:
    • Site-wide: 10,361 out of 65,094

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide

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