LexicHash: sequence similarity estimation via lexicographic comparison of hashes

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pairwise sequence alignment is computationally intensive, especially for third-generation sequencing data.
• MinHash is a common approximation method using k-mers and min-hashes to estimate sequence similarity.
• The parameter k in MinHash presents a precision-recall tradeoff, impacting alignment identification.

Purpose of the Study:

• Introduce LexicHash, a novel similarity estimation method.
• Achieve high precision and sensitivity independent of the k-mer size parameter.
• Develop an efficient algorithm for searching large alignments.

Main Methods:

• LexicHash is a variant of MinHash utilizing a specialized hash function.
• Similarity is estimated by assessing the lexicographical similarity of min-hashes, not just matches.
• The method was evaluated on 40 PacBio datasets.

Main Results:

• LexicHash demonstrated an average 20.9% improvement in the area under the precision-recall curve compared to MinHash.
• The LexicHash framework enables an O(n) time algorithm for efficient alignment searching.
• This circumvents the typical O(n^2) complexity of pairwise similarity searches.

Conclusions:

• LexicHash offers a significant advancement in sequence similarity estimation for large-scale genomic data.
• The method overcomes the limitations of traditional MinHash, providing better precision and recall.
• LexicHash is available for use and further development.