Approximate nearest neighbor graph provides fast and efficient embedding with applications for large-scale biological...

Area of Science:

• Computational Biology
• Data Science
• Bioinformatics

Background:

• Dimension reduction (DR) algorithms like t-SNE and UMAP are crucial for big data visualization but struggle with large datasets.
• Existing methods face computational bottlenecks, particularly in constructing K-nearest neighbor graphs (K-NNG).
• There is a need for scalable DR techniques applicable to diverse biological data, including genomic sequences.

Purpose of the Study:

• To develop an improved and efficient dimension reduction algorithm for large-scale biological data visualization.
• To enhance the speed and scalability of DR methods by optimizing the K-NNG construction.
• To extend DR capabilities to DNA/RNA sequence data analysis.

Main Methods:

• Developed a novel DR algorithm combining aspects of t-SNE and UMAP.
• Replaced the K-NNG bottleneck with a Hierarchical Navigable Small World (HNSW) graph.
• Integrated HNSW with locality-sensitive hashing (e.g., MinHash) for efficient DNA/RNA sequence distance estimation.

Main Results:

• The annembed library, implemented in Rust, offers competitive accuracy compared to UMAP-like algorithms.
• Demonstrated scalability and effectiveness on large-scale microbial genomics, single-cell RNA sequencing, and metagenomic binning datasets.
• Introduced features for computing local intrinsic dimension and hubness to assess embedding quality.

Conclusions:

• Annembed provides a fast and accurate solution for dimension reduction in big biological data.
• The library facilitates analysis tasks where distance computation is intensive or datasets are massive.
• Annembed is a valuable tool for advancing biological data analysis, particularly in genomics and single-cell studies.