OMH

OMH implements an order-sensitive locality-sensitive hashing method to estimate edit distance between biological sequences for improved sequence comparison and alignment filtering.

Key Features:

• Edit Distance Sensitivity: Sensitive to both k-mer content and the relative order of k-mers within sequences, enabling more accurate estimation of edit distance than unordered k-mer approaches.
• MinHash Foundation: Builds on the minHash LSH framework and contrasts with traditional LSH methods that approximate Jaccard or Hamming similarity by treating sequences as unordered collections of k-mers.
• Reduction in Computational Load: Distinguishes sequence pairs unlikely to produce high-quality alignments from those that may, reducing downstream alignment computation while limiting false negatives.
• Theoretical Guarantees: Operates as a gapped LSH method and provides formal theoretical guarantees for similarity detection under the edit distance model.

Scientific Applications:

• Sequence alignment filtering: Pre-filters candidate sequence pairs to reduce alignment workload while preserving true alignments.
• Phylogenetic analysis: Supports comparative sequence analyses where accurate estimates of sequence similarity and order-aware distance are required.
• Genomic research: Applies to large-scale genomic sequence comparison tasks that require efficient, order-sensitive similarity estimation.

Methodology:

OMH extends the minHash locality-sensitive hashing framework used to approximate Jaccard similarity by incorporating order sensitivity into the hashing process and implementing a gapped LSH approach with formal theoretical guarantees.