MELO-ED: learning locality-sensitive multi-embeddings for edit distance

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Edit distance is crucial for biological sequence similarity but computationally expensive.
• Previous methods like learned locality-sensitive bucketing (LSB) had accuracy limitations due to one-dimensional hash values.
• Scalable and accurate sequence comparison is vital for large-scale genomic analysis.

Purpose of the Study:

• Introduce MELO-ED, a novel framework to efficiently approximate edit distance for biological sequences.
• Improve accuracy and scalability of sequence similarity searches beyond existing methods.
• Enable fast classification of similar and dissimilar sequences in massive datasets.

Main Methods:

• Developed MELO-ED, a multi-embedding locality-sensitive framework.
• Employed a Siamese convolutional neural architecture for learning complementary embeddings.
• Integrated locality-sensitive bucketing with higher-dimensional embeddings.
• Utilized mature indexing methods in the embedding space for similarity searches.

Main Results:

• MELO-ED achieves near-perfect accuracy in approximating edit distance.
• The framework demonstrates superior performance and efficiency compared to traditional and machine learning methods.
• Evaluations on simulated DNA and real barcode data confirm MELO-ED's effectiveness.
• MELO-ED significantly speeds up edit distance computations for large databases.

Conclusions:

• MELO-ED offers a state-of-the-art solution for fast and accurate biological sequence classification.
• The multi-embedding approach overcomes limitations of previous LSB functions.
• MELO-ED enables scalable similarity searches in massive genomic databases.