FEDRANN: effective long-read overlap detection based on dimensionality reduction and approximate nearest neighbors.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Overlap detection is crucial for de novo genome assembly using the Overlap-Layout-Consensus (OLC) paradigm.
• Current methods struggle with repetitive genomic regions and large datasets.
• Heuristic seed-and-extension and locality-sensitive hashing (LSH) are common but limited strategies.

Purpose of the Study:

• To develop a novel and efficient strategy for overlap graph construction in genome assembly.
• To address limitations of existing overlap detection methods in handling repetitive regions and large datasets.
• To present Fedrann, an open-source implementation for robust overlap detection.

Main Methods:

• Integration of feature extraction, dimensionality reduction (DR), and approximate nearest neighbor (ANN) search.
• Utilized inverse document frequency (IDF) transformation, sparse random projection (SRP), and NNDescent algorithm.
• Developed an efficient Python-based implementation leveraging C-accelerated libraries for performance.

Main Results:

• Fedrann achieves accurate overlap detection across diverse datasets, comparable or superior to state-of-the-art tools (MECAT2, minimap2, wtdbg2).
• Maintains competitive runtime performance despite being Python-based.
• Enabled successful reconstruction of human whole genomes with high contiguity and quality when integrated into the Shasta assembler.

Conclusions:

• The combination of DR and ANN techniques provides a scalable and accurate framework for overlap detection in long-read assembly.
• Fedrann offers a robust solution for constructing overlap graphs, improving genome assembly quality.
• The approach is applicable to broader sequence similarity search tasks beyond genome assembly.