Learning locality-sensitive bucketing functions.

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Sequence analysis tasks often require identifying biologically related sequences within large datasets.
• Edit distance is a common measure for sequence similarity, but its computation is computationally expensive for massive datasets.
• Existing methods like locality-sensitive hashing (LSH) have limitations in efficiently handling large-scale sequence comparisons.

Purpose of the Study:

• To develop and train effective locality-sensitive bucketing (LSB) functions using machine learning techniques.
• To address the computational challenges of identifying sequences with small edit distances in large biological datasets.
• To improve upon existing methods for sequence similarity searching.

Main Methods:

• Utilized machine learning, specifically novel neural network structures and a custom loss function, to train LSB functions.
• Developed generalized (d1,d2)-LSB functions capable of partitioning sequences into buckets based on edit distance.
• Compared the performance of trained LSB functions against the state-of-the-art LSH method, Order Min Hash.

Main Results:

• Achieved nearly perfect accuracy for specific (d1,d2) pairs, validating theoretical predictions.
• Demonstrated high accuracy for a broader range of (d1,d2) parameters.
• Trained LSB functions showed a 2- to 5-fold improvement in sensitivity for recognizing similar sequences compared to Order Min Hash.
• Successfully applied the trained LSB functions to analyze erroneous cell barcode data.

Conclusions:

• Machine learning provides a powerful approach for training effective LSB functions for sequence analysis.
• The developed LSB functions offer significant improvements in efficiency and accuracy for identifying related sequences.
• These findings have practical implications for large-scale biological sequence analysis and error correction.