Answers.Body: <p>There are several tools beyond the one that you link that  you're referring to. There are &quot;pseudoalignment&quot; techniques like <a href="https://www.nature.com/articles/nbt.3519" rel="nofollow noreferrer">kallisto</a> or <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5600148/" rel="nofollow noreferrer">salmon</a>, which are formally not alignments in part because they do not use techniques like dynamic programming to generate exact base alignments, but provide functionally similar information in the sense that each read is assigned to a possible transcript.</p>
  <p>There are additionally techniques like <a href="https://academic.oup.com/bioinformatics/article/34/18/3094/4994778?login=false" rel="nofollow noreferrer">minimap2</a> or <a href="https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2336-6" rel="nofollow noreferrer">k-mer alignment</a> (KMA) that simply use k-mers to seed alignments but go on to perform exact base-by-base alignments as the final output, and these are used for scoring alignments. This is a common feature that is also leveraged in some BLAST tools.</p>
  <p>These are all still what one might call <strong>read mapping methods</strong>.</p>
  <hr />
  <p>Your paper that you link is somewhat different, in that it is not really doing <em>read mapping</em> or alignment.</p>
  <p>It is most similar to kallisto, in that it is essentially sketching k-mers for each possible read target in their database, and sketching k-mers for each read, and then finding the best pairwise match between each read k-mer sketch and the set of possible database sketches. It does this by using matrix factorization approaches to infer these relationships, as opposed to alignment approaches to assign direct one-to-one associations between DNA sequence positions. It looks like it also tries to be clever about higher-level relationships and classifications, but that's outside the scope of your question. (I have not read the paper in depth, maybe there is probably to it than that.)</p>
  <p>I believe that the answer to your second question varies from tool to tool. In some cases queries only might be hashed to reference indices (minimap2), in others both might be hashed (kallisto/salmon and I believe the first step of KMA?).</p>
  <p>I look forward with interest to whether someone with a deeper knowledge of alignment algorithms will come in and correct me!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-31T21:44:06.630Z
Answers.LastActivityDate: 2024-07-31T21:44:06.630Z
Answers.UserDisplayName: Maximilian Press
Answers.Body: <p>The statement from the paper relates to the particular method they've used as an alignment-free method, not kmer methods in general. There are plenty of kmer-dependent alignment algorithms (e.g. <a href="https://github.com/lh3/minimap2" rel="nofollow noreferrer">minimap2</a>, <a href="https://gitlab.com/mcfrith/last" rel="nofollow noreferrer">LAST</a>) - usually referred to as <em>seeded</em> alignment. There are also a few kmer-<em>only</em> aligners (e.g. <a href="https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2336-6" rel="nofollow noreferrer">KMA</a>), but such approaches are rare.</p>
  <p>I think it's important to distinguish between a <em>mapper</em> and an <em>aligner</em>:</p>
  <ul>
  <li><strong>mapper</strong> - identifies the likely origin of a sequence</li>
  <li><strong>aligner</strong> - determines base-level matching of a sequence and a reference</li>
  </ul>
  <p>Because aligners require base-level matching, all aligners are mappers, but not all mappers are aligners. For what it's worth, there's also a class of <em>light-weight</em> or <em>quasi</em> mappers (e.g. <a href="https://www.biorxiv.org/content/10.1101/138800v2.abstract" rel="nofollow noreferrer">Salmon</a>) which attempt to find approximate match locations, but don't put effort into exact base-level alignment.</p>
  <p>So when this paper talks about an &quot;alignment-free approach&quot;, they're referring to using kmers for mapping only, and not doing any subsequent alignment.</p>
  <p>A common approach for kmer-based mapping is to pregenerate a reference index by storing the component kmers of the reference sequences in a database as a <a href="https://en.wikipedia.org/wiki/Hash_table" rel="nofollow noreferrer">hash map</a> which links each kmer to a set of reference sequences. This corresponds with the second approach that you mentioned.</p>
  <p>When the mapping is carried out, the query sequences are broken up into kmers and those kmers are queried against the hash map, quickly identifying matches.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-31T22:12:16.017Z
Answers.LastActivityDate: 2024-07-31T22:12:16.017Z
Answers.UserDisplayName: gringer
Body: <p>I'm currently exploring the concept of k-mer alignment in bioinformatics and came across <a href="https://academic.oup.com/gigascience/article/doi/10.1093/gigascience/giac029/6588116" rel="nofollow noreferrer">some information</a> suggesting that the k-mer approach is considered a non-alignment method. Could someone clarify how k-mer alignment actually functions? Specifically, I'm trying to understand the mechanism behind it.</p>
  <p>Additionally, I'm confused about the process of hashing in relation to k-mers. Is it the query sequences that are converted into k-mers for alignment against a database, or are the database sequences hashed into k-mers that then align with multiple query sequences? This question came up during a discussion about adjusting the -k parameter, which controls the k-mer length.</p>
  <p>I am not sure if I understand it correctly, I just want to understand how k-mers approach works, since I have never heard about it before. If you know something about it, I'd really appreciate your help. Thanks in advance.</p>
  
Tags: <phylogenetics><k-mer>
Title: What is the the principle and mechanism of k-mer alignment?
ThreadText: # What is the the principle and mechanism of k-mer alignment?
  
  (Asked by: username_0 on 2024-07-30)
  
  I'm currently exploring the concept of k-mer alignment in bioinformatics and came across [some information](https://academic.oup.com/gigascience/article/doi/10.1093/gigascience/giac029/6588116) suggesting that the k-mer approach is considered a non-alignment method. Could someone clarify how k-mer alignment actually functions? Specifically, I'm trying to understand the mechanism behind it.
  
  Additionally, I'm confused about the process of hashing in relation to k-mers. Is it the query sequences that are converted into k-mers for alignment against a database, or are the database sequences hashed into k-mers that then align with multiple query sequences? This question came up during a discussion about adjusting the -k parameter, which controls the k-mer length.
  
  I am not sure if I understand it correctly, I just want to understand how k-mers approach works, since I have never heard about it before. If you know something about it, I'd really appreciate your help. Thanks in advance.
  
  **Tags:** phylogenetics, k-mer
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-07-31. Score: 2
  
  There are several tools beyond the one that you link that you're referring to. There are "pseudoalignment" techniques like [kallisto](https://www.nature.com/articles/nbt.3519) or [salmon](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5600148/), which are formally not alignments in part because they do not use techniques like dynamic programming to generate exact base alignments, but provide functionally similar information in the sense that each read is assigned to a possible transcript.
  
  There are additionally techniques like [minimap2](https://academic.oup.com/bioinformatics/article/34/18/3094/4994778?login=false) or [k-mer alignment](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2336-6) (KMA) that simply use k-mers to seed alignments but go on to perform exact base-by-base alignments as the final output, and these are used for scoring alignments. This is a common feature that is also leveraged in some BLAST tools.
  
  These are all still what one might call **read mapping methods**.
  
  ---
  
  Your paper that you link is somewhat different, in that it is not really doing *read mapping* or alignment.
  
  It is most similar to kallisto, in that it is essentially sketching k-mers for each possible read target in their database, and sketching k-mers for each read, and then finding the best pairwise match between each read k-mer sketch and the set of possible database sketches. It does this by using matrix factorization approaches to infer these relationships, as opposed to alignment approaches to assign direct one-to-one associations between DNA sequence positions. It looks like it also tries to be clever about higher-level relationships and classifications, but that's outside the scope of your question. (I have not read the paper in depth, maybe there is probably to it than that.)
  
  I believe that the answer to your second question varies from tool to tool. In some cases queries only might be hashed to reference indices (minimap2), in others both might be hashed (kallisto/salmon and I believe the first step of KMA?).
  
  I look forward with interest to whether someone with a deeper knowledge of alignment algorithms will come in and correct me!
  
  
  ---
  
  ### Answer by username_2 on 2024-07-31. Score: 1
  
  The statement from the paper relates to the particular method they've used as an alignment-free method, not kmer methods in general. There are plenty of kmer-dependent alignment algorithms (e.g. [minimap2](https://github.com/lh3/minimap2), [LAST](https://gitlab.com/mcfrith/last)) - usually referred to as *seeded* alignment. There are also a few kmer-*only* aligners (e.g. [KMA](https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-018-2336-6)), but such approaches are rare.
  
  I think it's important to distinguish between a *mapper* and an *aligner*:
  
  * **mapper** - identifies the likely origin of a sequence
  * **aligner** - determines base-level matching of a sequence and a reference
  
  Because aligners require base-level matching, all aligners are mappers, but not all mappers are aligners. For what it's worth, there's also a class of *light-weight* or *quasi* mappers (e.g. [Salmon](https://www.biorxiv.org/content/10.1101/138800v2.abstract)) which attempt to find approximate match locations, but don't put effort into exact base-level alignment.
  
  So when this paper talks about an "alignment-free approach", they're referring to using kmers for mapping only, and not doing any subsequent alignment.
  
  A common approach for kmer-based mapping is to pregenerate a reference index by storing the component kmers of the reference sequences in a database as a [hash map](https://en.wikipedia.org/wiki/Hash_table) which links each kmer to a set of reference sequences. This corresponds with the second approach that you mentioned.
  
  When the mapping is carried out, the query sequences are broken up into kmers and those kmers are queried against the hash map, quickly identifying matches.
  
  
  ---
  
  