Scholarlink

Motivation <p>Short DNA sequences of length&#xa0;<i>k</i> that appear in a single location (e.g., at a single genomic position, in a single species from a larger set of species, etc.) are called <i>unique k-mers</i>. They are useful for placing sequenced DNA fragments at the correct location without computing alignments and without ambiguity. However, they are not necessarily robust: A single basepair change may turn a unique <i>k</i>-mer into a different one that may in fact be present at one or more different locations, which may give confusing or contradictory information when attempting to place a read by its <i>k</i>-mer content. A more robust concept are <i>strongly unique</i> <i>k</i>-mers, i.e., unique <i>k</i>-mers for which no Hamming-distance-1 neighbor with conflicting information exists in all of the considered sequences. Given a set of <i>k</i>-mers, it is therefore of interest to have an efficient method that can distinguish <i>k</i>-mers with a Hamming-distance-1 neighbor in the collection from those that do not.</p> Results <p>We present engineered algorithms to identify and mark within a set <i>K</i> of (canonical) <i>k</i>-mers all elements that have a Hamming-distance-1 neighbor in the same set. One algorithm is based on recursively running a 4-way comparison on sub-intervals of the sorted set. The other algorithm is based on bucketing and running a pairwise bit-parallel Hamming distance test on small buckets of the sorted set. Both methods consider canonical <i>k</i>-mers (i.e., taking reverse complements into account) and allow for efficient parallelization. The methods have been implemented and applied in practice to sets consisting of several billions of <i>k</i>-mers. An optimized combined approach running with 16 threads on a 16-core workstation yields wall times below 20 seconds on the 2.5 billion distinct 31-mers of the human telomere-to-telomere reference genome.</p> Availability <p>An implementation can be found at <a href="https://gitlab.com/rahmannlab/strong-k-mers">https://gitlab.com/rahmannlab/strong-k-mers</a>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Swiftly identifying strongly unique k-mers

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月13日

查看全文
  • Jens Zentgraf,
  • Sven Rahmann

摘要

Motivation

Short DNA sequences of length k that appear in a single location (e.g., at a single genomic position, in a single species from a larger set of species, etc.) are called unique k-mers. They are useful for placing sequenced DNA fragments at the correct location without computing alignments and without ambiguity. However, they are not necessarily robust: A single basepair change may turn a unique k-mer into a different one that may in fact be present at one or more different locations, which may give confusing or contradictory information when attempting to place a read by its k-mer content. A more robust concept are strongly unique k-mers, i.e., unique k-mers for which no Hamming-distance-1 neighbor with conflicting information exists in all of the considered sequences. Given a set of k-mers, it is therefore of interest to have an efficient method that can distinguish k-mers with a Hamming-distance-1 neighbor in the collection from those that do not.

Results

We present engineered algorithms to identify and mark within a set K of (canonical) k-mers all elements that have a Hamming-distance-1 neighbor in the same set. One algorithm is based on recursively running a 4-way comparison on sub-intervals of the sorted set. The other algorithm is based on bucketing and running a pairwise bit-parallel Hamming distance test on small buckets of the sorted set. Both methods consider canonical k-mers (i.e., taking reverse complements into account) and allow for efficient parallelization. The methods have been implemented and applied in practice to sets consisting of several billions of k-mers. An optimized combined approach running with 16 threads on a 16-core workstation yields wall times below 20 seconds on the 2.5 billion distinct 31-mers of the human telomere-to-telomere reference genome.

Availability

An implementation can be found at https://gitlab.com/rahmannlab/strong-k-mers.