Construction of edit-distance graphs for large sets of short reads through minimizer-bucketing.

ABSTRACT:

Motivation

Pairs of short reads with small edit distances, along with their unique molecular identifier tags, have been exploited to correct sequencing errors in both reads and tags. However, brute-force identification of these pairs is impractical for large datasets containing ten million or more reads due to its quadratic complexity. Minimizer-bucketing and locality-sensitive hashing have been used to partition read sets into buckets of similar reads, allowing edit-distance calculations only within each bucket. However, challenges like minimizing missing pairs, optimizing bucketing parameters, and exploring combination bucketing to improve pair detection remain.

Results

We define an edit-distance graph for a set of short reads, where nodes represent reads, and edges connec

SUBMITTER: Ping P 

PROVIDER: S-EPMC12040381 | biostudies-literature | 2025

REPOSITORIES: biostudies-literature