skip to main content


Search for: All records

Award ID contains: 2046991

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Alkan, Can (Ed.)
    Abstract Motivation

    Pairwise sequence alignment is a heavy computational burden, particularly in the context of third-generation sequencing technologies. This issue is commonly addressed by approximately estimating sequence similarities using a hash-based method such as MinHash. In MinHash, all k-mers in a read are hashed and the minimum hash value, the min-hash, is stored. Pairwise similarities can then be estimated by counting the number of min-hash matches between a pair of reads, across many distinct hash functions. The choice of the parameter k controls an important tradeoff in the task of identifying alignments: larger k-values give greater confidence in the identification of alignments (high precision) but can lead to many missing alignments (low recall), particularly in the presence of significant noise.

    Results

    In this work, we introduce LexicHash, a new similarity estimation method that is effectively independent of the choice of k and attains the high precision of large-k and the high sensitivity of small-k MinHash. LexicHash is a variant of MinHash with a carefully designed hash function. When estimating the similarity between two reads, instead of simply checking whether min-hashes match (as in standard MinHash), one checks how “lexicographically similar” the LexicHash min-hashes are. In our experiments on 40 PacBio datasets, the area under the precision–recall curves obtained by LexicHash had an average improvement of 20.9% over MinHash. Additionally, the LexicHash framework lends itself naturally to an efficient search of the largest alignments, yielding an O(n) time algorithm, and circumventing the seemingly fundamental O(n2) scaling associated with pairwise similarity search.

    Availability and implementation

    LexicHash is available on GitHub at https://github.com/gcgreenberg/LexicHash.

     
    more » « less
    Free, publicly-accessible full text available November 1, 2024
  2. Free, publicly-accessible full text available July 7, 2025
  3. Free, publicly-accessible full text available March 13, 2025
  4. Free, publicly-accessible full text available March 1, 2025
  5. Free, publicly-accessible full text available March 1, 2025
  6. Free, publicly-accessible full text available January 1, 2025
  7. Free, publicly-accessible full text available December 10, 2024
  8. Free, publicly-accessible full text available December 10, 2024