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

  1. Jia-Yuan Zhang
  2. Changjiu Miao
  3. Teng Qiu
  4. Junyi He
  5. Wenqi Cao
  6. Wei Lin
  7. Xiaoshuang Xia
  8. Lei He
  9. Chunlei Yang
  10. Yuhui Sun
  11. Tao Zeng
  12. Yuxiang Li
  13. Xun Xu
  14. Yijun Ruan
  15. Yuliang Dong

Reviewed by

Read the full article See related articles

Discuss this preprint

Start a discussion What are Sciety discussions?

Listed in

Log in to save this article

Abstract

Overlap detection is a key step in de novo genome assembly pipelines based on the overlap-layout-consensus paradigm. Existing methods for overlap detection either rely on heuristic seed-and-extension strategies or locality-sensitive hashing (LSH), both of which struggle to handle repetitive genomic regions and the computational burden of large-scale datasets. Here, we present FEDRANN, a novel strategy for overlap graph construction that integrates feature extraction, dimensionality reduction (DR), and approximate nearest neighbor (ANN) search. We find the pipeline combining inverse document frequency (IDF) transformation, sparse random projection (SRP), and NNDescent enables accurate detection of overlaps across diverse datasets. We developed an efficient open-source implementation of this pipeline named Fedrann (https://github.com/jzhang-dev/fedrann). Through systematic benchmarking on real long-read sequencing data, we demonstrate that Fedrann produces overlap graphs comparable to or better than those generated by existing state-of-the-art tools, including MECAT2, minimap2, and wtdbg2, while maintaining competitive runtime. By integrating Fedrann into the Shasta assembler, we successfully reconstructed human whole genomes, achieving high assembly contiguity and quality. Despite being implemented primarily in Python, Fedrann achieves performance parity with tools written in compiled languages by leveraging C-accelerated numerical libraries and optimized batch-based matrix operations. Our results suggest that the combination of DR and ANN techniques offers a robust, scalable framework for accurate overlap detection in long-read assembly and broader sequence similarity search tasks.

Article activity feed

  1. GigaScience

    AbstractOverlap detection is a key step in de novo genome assembly pipelines based on the Overlap-Layout-Consensus (OLC) paradigm. However, existing methods for overlap detection either rely on heuristic seed-and-extension strategies or locality-sensitive hashing (LSH), both of which struggle to handle repetitive genomic regions and the computational burden of large-scale datasets. Here, we present FEDRANN, a novel strategy for overlap graph construction that integrates feature extraction, dimensionality reduction (DR), and approximate nearest neighbor (ANN) search. We find the pipeline combining inverse document frequency (IDF) transformation, sparse random projection (SRP), and NNDescent enables accurate detection of overlaps across diverse datasets. We developed an efficient open-source implementation of this pipeline named Fedrann (https://github.com/jzhang-dev/fedrann). Through systematic benchmarking on real long-read sequencing data, we demonstrate that Fedrann produces overlap graphs comparable to or better than those generated by existing state-of-the-art tools, including MECAT2, minimap2, and wtdbg2, while maintaining competitive runtime. Despite being implemented primarily in Python, Fedrann achieves performance on par with tools written in compiled languages, owing to matrix-based representations and C-accelerated numerical libraries. Our results suggest that DR and ANN techniques offer a promising new direction for scalable and accurate overlap detection in long-read assembly and broader sequence similarity search tasks.

    This work has been peer reviewed in GigaScience (see https://doi.org/10.1093/gigascience/giag048), which carries out open, named peer-review. These reviews are published under a CC-BY 4.0 license and were as follows:

    Reviewer 2：

    The authors present METRIN-KG, a knowledge graph integrating plant metabolomic, trait, and biotic interaction datasets. The work should have substantial value for multiple plant sciences and ecology domains. The overall effort to harmonize disparate resources into an integrated, semantically coherent resource is impressive. The methodology includes a notable pipeline for ontology alignment across multiple sources. However, despite its technical strengths, several issues regarding data accessibility and manuscript structure and clarity should be addressed. The manuscript is highly technical throughout. While this level of precision is exemplary, it may alienate biologically oriented readers, and effort should be made so that the impact and manuscript is clear to a larger audience.

    Major comments

    1. The online deployment currently presents several problems that must be resolved before publication.
    1. Usability represents a significant barrier. Many potential users such as biologists without semantic-web or RDF experience are unlikely to be able to interpret the current figures or formulate SPARQL queries. The manuscript briefly mentions ExpasyGPT, which has strong potential to overcome this barrier by allowing natural language querying. This tool should be emphasized more prominently, potentially with a dedicated subsection and discussion of its role in broadening the resource's accessibility.
    1. To fully demonstrate the relevance of METRIN-KG, the use-case section would benefit from quantitative summaries, visualizations (e.g., distributions, network visualizations), and biological interpretations of query results.
    1. The overall manuscript organisation would benefit from restructuring to improve readability and better expose the impact of the work done.

    • The methodological content currently in "Mapping of TRY data" and "Mapping of GloBI data" should be moved to the Methods section, while the quantitative outputs (e.g., numbers of records) should be moved into a dedicated Results section.

    • The current "Data re-use and case studies" section could be reorganised into Results and Discussion sections,

    • Results include: description of outputs from the methodological steps (e.g. the ontology, the successfulness of the mapping process, the size of the final knowledge graph/number of triples, and other relevant metrics; the user interface, including being able to share and add example questions and write NL questions via ExpasyGPT; examples of SPARQL queries and case studies.

    • Discussion includes: Reuse potential; case-study interpretations or impact; future directions including planned expansion and enhancing of ontological structure, etc.

    1. An overview and evaluation of the KG should be provided, for example the number of plant species, and the distributions of connections. Any gaps or any (potentially) biases due to the input data needs to be acknowledged. For example, it is very likely certain species may be under/overrepresented in either metabolome or interaction datasets, or possibly geographic skews could exist.

    1. The ontology is variously referred to as the "Earth Metabolome Ontology", "EMI ontology", and "EMI". Consistent naming should be adopted throughout the manuscript and associated repositories. It is also unclear whether the ontology is a result of this work. As written, the "Ontology" section under "Methods" reads more like a result/description than a methodological step. Clarifying what components are original contributions and presenting them in Results would strengthen the manuscript. Additionally, the phrases "our proposed framework" and "our approach" are ambiguous, do these refer to the ontology itself, the metadata-mapping pipeline, or the overall integration process? Finally, referring to METRIN-KG as a "tutorial to build a knowledge graph" appears to be a bit out of place, given the topic of the manuscript.

    2. Given its potential relevance beyond this project, the authors are strongly encouraged to publish the code for the metadata-mapping pipeline. In addition, the following details would strengthen the methodological rigor:

    • Were any acceptability criteria implemented in the automated step, e.g. a minimum Cosine similarity threshold?

    • Were the manual corrections systematically documented?

    • In how many cases were manual corrections needed?

    • Was any evaluation done on the embedding/model version or the source of errors?

    Minor comments

    1. The manuscript would benefit from proofreading for consistent use of Oxford commas (and an "&" instead of "and").

    2. Reference 190 contains a typo "GiHub"

    3. References should be checked (e.g. citation for [95] references both METRIN-KG Zenodo and GloBI Zenodo)

    4. The METRIN-KG Zenodo link in the article is not to the latest version (Version 5)

    5. Consider improving the figures, e.g. use of colour to better communicate the content and refining layouts.

    6. The authors should deposit a snapshot of the GitHub repository to Zenodo.

    The following are suggestions to the authors, to be followed by their own judgement:

    1. Table 1, Figure 3, Figure 4 could be moved to supplementary material to make space for figures for the case studies.

    2. The dense in-text list of ontologies in the "Metadata mapping" section could be replaced with a summarized table (e.g. by moving Supplementary Table 2, but including references to the main text).

    3. The full SPARQL queries in "Taxonomy mapping" could be moved to supplementary materials, with a high-level description left in the main text.

  2. GigaScience

    AbstractOverlap detection is a key step in de novo genome assembly pipelines based on the Overlap-Layout-Consensus (OLC) paradigm. However, existing methods for overlap detection either rely on heuristic seed-and-extension strategies or locality-sensitive hashing (LSH), both of which struggle to handle repetitive genomic regions and the computational burden of large-scale datasets. Here, we present FEDRANN, a novel strategy for overlap graph construction that integrates feature extraction, dimensionality reduction (DR), and approximate nearest neighbor (ANN) search. We find the pipeline combining inverse document frequency (IDF) transformation, sparse random projection (SRP), and NNDescent enables accurate detection of overlaps across diverse datasets. We developed an efficient open-source implementation of this pipeline named Fedrann (https://github.com/jzhang-dev/fedrann). Through systematic benchmarking on real long-read sequencing data, we demonstrate that Fedrann produces overlap graphs comparable to or better than those generated by existing state-of-the-art tools, including MECAT2, minimap2, and wtdbg2, while maintaining competitive runtime. Despite being implemented primarily in Python, Fedrann achieves performance on par with tools written in compiled languages, owing to matrix-based representations and C-accelerated numerical libraries. Our results suggest that DR and ANN techniques offer a promising new direction for scalable and accurate overlap detection in long-read assembly and broader sequence similarity search tasks.

    This work has been peer reviewed in GigaScience (see https://doi.org/10.1093/gigascience/giag048), which carries out open, named peer-review. These reviews are published under a CC-BY 4.0 license and were as follows:

    Reviewer 1：

    Summary This paper presents FEDRANN, a novel approach to overlap detection in long-read genome assembly that combines feature extraction, dimensionality reduction (DR), and approximate nearest neighbor (ANN) search. The authors systematically evaluate a range of design choices and implement the best-performing pipeline (IDF-SRP-NNDescent) as an open-source tool, Fedrann. Benchmarking against state-of-the-art tools (minimap2, MECAT2, wtdbg2, BLEND, xRead, MHAP) shows that Fedrann achieves competitive or superior accuracy and overlap graph quality across multiple sequencing platforms (ONT, PacBio HiFi, CycloneSEQ), while maintaining reasonable runtime. The conceptual framing of overlap detection as a k-NN search problem is both innovative and potentially influential. Major Strengths

    1. Novel conceptual framework: Framing overlap detection as a k-NN search problem, drawing analogies from single-cell analysis, is creative and opens new algorithmic possibilities for genome assembly.
    2. Systematic evaluation: The authors carefully assess multiple feature extraction, DR, and ANN methods before converging on the optimal pipeline.
    3. Strong empirical results: Fedrann demonstrates high accuracy and graph quality, often outperforming established tools while remaining runtime-efficient. Major Concerns and Recommendations
    4. Memory consumption is a critical limitation o Fedrann requires >700 GB RAM for human genome datasets, which makes the tool impractical for most research labs and cost-prohibitive for cloud use. o While acknowledged, this limitation is somewhat downplayed. In its current state, Fedrann may be restricted to only very high-resource environments. o Recommendation: Either (a) demonstrate initial results of memory-reduction strategies (e.g., shared memory, memory-mapped structures, GPU acceleration), or (b) more prominently highlight this as a key limitation restricting practical adoption.
    5. Incomplete evaluation at the assembly pipeline level o The paper evaluates overlap graph quality but does not show results on final genome assemblies. Major Concerns and Recommendations
    6. Memory consumption is a critical limitation o Fedrann requires >700 GB RAM for human genome datasets, which makes the tool impractical for most research labs and cost-prohibitive for cloud use. o While acknowledged, this limitation is somewhat downplayed. In its current state, Fedrann may be restricted to only very high-resource environments. o Recommendation: Either (a) demonstrate initial results of memory-reduction strategies (e.g., shared memory, memory-mapped structures, GPU acceleration), or (b) more prominently highlight this as a key limitation restricting practical adoption.
    7. Incomplete evaluation at the assembly pipeline level o The paper evaluates overlap graph quality but does not show results on final genome assemblies. Minor Comments • Figures S4–S6 (embedding dimension analysis) could be better explained in the main text with more intuitive interpretation. • Benchmarking fairness: tools designed for high recall (e.g., minimap2, MECAT2) may be disadvantaged by post-processing into “top k” mode. Clarify this limitation in comparisons. Minor Corrections • Figure 1: Step numbering is currently (1), (3), (4). Step (2) is missing. Overall Recommendation This paper presents a novel and promising framework for overlap detection with strong methodological rigor and empirical results. However, two major gaps — excessive memory usage and lack of assembly-level validation — must be addressed before the work can be considered fully convincing. In addition, clarity on basic parameters such as k-mer size is necessary for robustness.
  3. Version published to 10.1093/gigascience/giag048
  4. Version published to 10.1101/2025.05.30.656979 on bioRxiv