EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Jia-Yuan Zhang iD, Changjiu Miao iD, Teng Qiu, Junyi He, Wenqi Cao, Wei Lin, Xiaoshuang Xia, Lei He, Chunlei Yang, Yuhui Sun, Tao Zeng, Yuxiang Li iD und 3 weitere

GigaScience · 21.01.2026 · 15

DOI: 10.1093/gigascience/giag048 ↗

Kurz gefasst

Fachartikel in der Zeitschrift GigaScience, online erschienen am 08.05.2026. Verfasst von Jia-Yuan Zhang und 14 weiteren Autor:innen. Beteiligte Einrichtung: Life Sciences Institute, Zhejiang University, 866 Yuhangtang Road, Xihu District, Hangzhou 310058, China. Hauptthemen laut MEDLINE: Software, Genomics, Sequence Analysis, DNA, Computational Biology. Die Arbeit nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Key Research and Development Program of China.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

SoftwareGenomicsSequence Analysis, DNAComputational BiologyAlgorithmsHumansDimensionality ReductionHigh-Throughput Nucleotide Sequencing

Stichwörter der Autor:innen

de novo assemblydimensionality reductionk-nearest neighborslocality-sensitive hashingoverlap-layout-consensus

Autor:innen und Institutionen

  • Life Sciences Institute, Zhejiang University, 866 Yuhangtang Road, Xihu District, Hangzhou 310058, China.
  • State Key Laboratory of Genome and Multi-omics Technologies, BGI Research, 202 Zhenzhong Road, Xihu District, Hangzhou 310030, China.
  • BGI Research, 202 Zhenzhong Road, Xihu District, Hangzhou 310030, China.
  • BGI Hangzhou CycloneSEQ Technology Co. Ltd., 203 Zhenzhong Road, Xihu District, Hangzhou 310030, China.
  • College of Life Sciences, Zhejiang University, 866 Yuhangtang Road, Xihu District, Hangzhou 310058, China.
  • BGI Research, 59 Keji 3rd Road, Donghu New Technology Development Zone, Wuhan 430074, China.

ORCID-Profile: Jia-Yuan Zhang, Changjiu Miao, Yuxiang Li, Xun Xu, Yuliang Dong

Förderung

  • National Key Research and Development Program of China

Zitieren

APA

Zhang, J. Y., Miao, C., Qiu, T., He, J., Cao, W., Lin, W., Xia, X., He, L., Yang, C., Sun, Y., Zeng, T., Li, Y., Xu, X., Ruan, Y., & Dong, Y. (2026). FEDRANN: effective long-read overlap detection based on dimensionality reduction and approximate nearest neighbors. GigaScience, 15. https://doi.org/10.1093/gigascience/giag048

Vancouver

Zhang JY, Miao C, Qiu T, He J, Cao W, Lin W, et al. FEDRANN: effective long-read overlap detection based on dimensionality reduction and approximate nearest neighbors. GigaScience. 2026;15. doi:10.1093/gigascience/giag048

BibTeX
@article{Zhang2026,
  author = {Zhang, Jia-Yuan and Miao, Changjiu and Qiu, Teng and He, Junyi and Cao, Wenqi and Lin, Wei and Xia, Xiaoshuang and He, Lei and Yang, Chunlei and Sun, Yuhui and Zeng, Tao and Li, Yuxiang and Xu, Xun and Ruan, Yijun and Dong, Yuliang},
  title = {FEDRANN: effective long-read overlap detection based on dimensionality reduction and approximate nearest neighbors},
  journal = {GigaScience},
  year = {2026},
  volume = {15},
  doi = {10.1093/gigascience/giag048}
}
Kostenlos starten →