Unknown

Dataset Information

0

Locality-sensitive hashing for the edit distance.


ABSTRACT: 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 high-quality alignment from those that may. Therefore, an LSH reduces 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. In addition, due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming similarity 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 sensitive not only 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. AVAILABILITY AND IMPLEMENTATION:The code to generate the results is available at http://github.com/Kingsford-Group/omhismb2019. SUPPLEMENTARY INFORMATION:Supplementary data are available at Bioinformatics online.

SUBMITTER: Marcais G 

PROVIDER: S-EPMC6612865 | biostudies-other | 2019 Jul

REPOSITORIES: biostudies-other

altmetric image

Publications

Locality-sensitive hashing for the edit distance.

Marçais Guillaume G   DeBlasio Dan D   Pandey Prashant P   Kingsford Carl C  

Bioinformatics (Oxford, England) 20190701 14


<h4>Motivation</h4>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 high-quality alignment from those that may. Therefore, an LSH reduces the  ...[more]

Similar Datasets

| S-EPMC8340999 | biostudies-literature
| S-EPMC10538361 | biostudies-literature
| S-EPMC10985673 | biostudies-literature
| S-EPMC7669687 | biostudies-literature
| S-EPMC4393915 | biostudies-other
| S-EPMC5773183 | biostudies-literature
| S-EPMC9301846 | biostudies-literature
| S-EPMC2844998 | biostudies-literature
| S-EPMC9695784 | biostudies-literature
| S-EPMC8322085 | biostudies-literature