text: user12302: I am doing a course on graph algorithms in genome sequencing and the current assignment involves building an overlap graph from a bunch of k-mers. Formally the problem is as follows:
  Input: A collection of Patterns of k-mers.
  Output: The overlap graph in the form of an adjacency list.
  I have a working algorithm that handles most cases except for self-loops. The problem is that I don't know when/why I should be adding self-loops. Any help on this would be greatly appreciated. Below are some examples illustrating my question and my current solution. Thank you!
  Example 1:
  Input:
  ACT 
  CTT 
  TTT 
  Output:
  TTT->TTT 
  ACT->CTT 
  CTT->TTT 
  Example 2:
  Input:
  CCCC 
  Output:
  CCCC->CCCC 
  Example 3: 
  Input:
  CT 
  TG 
  TG 
  TC 
  TT 
  TC 
  Output:
  TC->CT 
  CT->TC,TG,TT 
  TT->TC,TG,TT 
  The goal here is to represent a collection of kmers as an overlap graph where unique kmer will be represented as a node in the graph. Directed edges will connect nodes whose last $k-1$ characters overlap with the other node's first $k-1$ characters. Therefore, repeated kmers that overlap with a other kmer should be reflected as self loops. That's what I understood, however I am looking for a more general rule/solution.
  Here is another example to illustrate this.
  Input:
  CT
  TT
  TT
  TT
  TT
  TT
  
  Output:
  CT->TT
  TT->TT
  
  Current code:
  /*
   * Creates an overlap graph from a list of k-mers
   *
   * \param patterns      a vector of string k-mers
   *
   * \return a string containing an adjacency list representation of the
   * overlap graph as described in the problem specification
   * 
   * Output Format. The overlap graph Overlap(Patterns), in the form of an
   * adjacency list. Specifically, each line of the output represents all
   * edges (u,v) leaving a given node u in the format “u -> v”, where u and v
   * are both k-mers. If a given node u has multiple edges leaving it (e.g. v and w),
   * the destination nodes are comma-separated in any order. For example, if
   * there exist nodes ACG, CGT, and CGG, the resulting line of the adjacency
   * list would be: ACG -> CGT,CGG
   */
  
  
  #include <algorithm>
  #include <iostream>
  #include <map>
  #include <vector>
  #include <set>
  #include <string>
  
  
  std::string overlap_graph(const std::vector<std::string>& patterns) {
      // Overlap Graph of the k-mers collection patterns, in which a vertex exists for
      // each unique k-mer, and an edge (u,v) exists if the last k-1 characters of u are
      // equal to the first k-1 characters of v.
  
      if (patterns.size() == 1) return patterns[0] + "->" + patterns[0];
      // Build adjancency list O(n^2)
      std::map <std::string, std::vector<std::string>> adj;
      for (const auto& kmer_u : patterns) {
          // Add kmer as key if it doesn't exist in the map and find its neighbours.
          if (adj.find(kmer_u) == adj.end()) {
              adj[kmer_u] = {};
              for (const auto& kmer_v : patterns) {
                  if ((kmer_u != kmer_v) &&
                      (kmer_u.substr(1, kmer_u.length() - 1) == kmer_v.substr(0, kmer_v.length() - 1)) && 
                      (std::find(adj[kmer_u].begin(), adj[kmer_u].end(), kmer_v) == adj[kmer_u].end())) {
                      adj[kmer_u].push_back(kmer_v);
                  }
              }
          } // Otherwise continue.
      }
  
      // Convert to string O(n).
      std::string ans;
      for (auto const& key_value : adj) {
          std::string kmer_u{ key_value.first };
          std::vector<std::string> kmers_v{ key_value.second };
          if (!kmers_v.empty()) {
              ans.append(kmer_u + "->" + kmers_v[0]);
              for (std::size_t kmer_v{ 1 }; kmer_v < kmers_v.size(); kmer_v++) {
                  ans.append(',' + kmers_v[kmer_v]);
              }
              ans.push_back('\n');
          }
      }
      return ans;
  }
  
  
  void tests() {
      /* Sample Dataset */
      std::vector<std::string> patterns{ {"AAG"}, {"AGA"}, {"ATT"}, {"CTA"}, {"CTC"}, {"GAT"},
                                         {"TAC"}, {"TCT"}, {"TCT"}, {"TTC"} };
      std::string answer{ "TTC->TCT\nCTA->TAC\nAAG->AGA\nCTC->TCT\nTCT->CTA,CTC\nAGA->GAT\nGAT->ATT\nATT->TTC\n" };
      std::cout << answer << std::endl;
      // std::cout << (overlap_graph(patterns) == answer) << std::endl;
      std::cout << overlap_graph(patterns) << std::endl;
  }
  
  
  void solution() {
      std::vector<std::string> patterns;
  
      std::string pattern;
      while (std::cin >> pattern) {
          patterns.push_back(pattern);
      }
      std::cout << overlap_graph(patterns) << std::endl;
  }
  
  
  int main() {
      //tests();
      solution();
  }
  
  
  user6628: You will want to create a self loop for a $k$-mer $s$ whenever $s_1,...,s_{k-1} = s_2,...,s_k$. This will only happen when all of the characters of the $k$-mer are identical, as $s_1=s_2, s_2=s_3,...,s_{k-1}=s_k$.
  
original_text: 12302: <p>I am doing a course on graph algorithms in genome sequencing and the current assignment involves building an overlap graph from a bunch of k-mers. Formally the problem is as follows:<br><br>
  <strong>Input:</strong> A collection of Patterns of k-mers.<br>
  <strong>Output:</strong> The overlap graph in the form of an adjacency list.<br><br>
  I have a working algorithm that handles most cases except for self-loops. The problem is that I don't know when/why I should be adding self-loops. Any help on this would be greatly appreciated. Below are some examples illustrating my question and my current solution. Thank you!</p>
  <p><em>Example 1</em>:<br>
  Input:</p>
  <p>ACT <br>
  CTT <br>
  TTT <br></p>
  <p>Output:</p>
  <p>TTT-&gt;TTT <br>
  ACT-&gt;CTT <br>
  CTT-&gt;TTT <br></p>
  <p><em>Example 2</em>:<br>
  Input:</p>
  <p>CCCC <br>
  Output:</p>
  <p>CCCC-&gt;CCCC <br></p>
  <p><em>Example 3</em>: <br>
  Input:</p>
  <p>CT <br>
  TG <br>
  TG <br>
  TC <br>
  TT <br>
  TC <br>
  Output:</p>
  <p>TC-&gt;CT <br>
  CT-&gt;TC,TG,TT <br>
  TT-&gt;TC,TG,TT <br></p>
  <p>The goal here is to represent a collection of kmers as an overlap graph where unique kmer will be represented as a node in the graph. Directed edges will connect nodes whose last <span class="math-container">$k-1$</span> characters overlap with the other node's first <span class="math-container">$k-1$</span> characters. Therefore, repeated kmers that overlap with a other kmer should be reflected as self loops. That's what I understood, however I am looking for a more general rule/solution.</p>
  <p>Here is another example to illustrate this.</p>
  <p>Input:</p>
  <pre><code>CT
  TT
  TT
  TT
  TT
  TT
  </code></pre>
  <p>Output:</p>
  <pre><code>CT-&gt;TT
  TT-&gt;TT
  </code></pre>
  <p>Current code:</p>
  <pre><code>/*
   * Creates an overlap graph from a list of k-mers
   *
   * \param patterns      a vector of string k-mers
   *
   * \return a string containing an adjacency list representation of the
   * overlap graph as described in the problem specification
   * 
   * Output Format. The overlap graph Overlap(Patterns), in the form of an
   * adjacency list. Specifically, each line of the output represents all
   * edges (u,v) leaving a given node u in the format “u -&gt; v”, where u and v
   * are both k-mers. If a given node u has multiple edges leaving it (e.g. v and w),
   * the destination nodes are comma-separated in any order. For example, if
   * there exist nodes ACG, CGT, and CGG, the resulting line of the adjacency
   * list would be: ACG -&gt; CGT,CGG
   */
  
  
  #include &lt;algorithm&gt;
  #include &lt;iostream&gt;
  #include &lt;map&gt;
  #include &lt;vector&gt;
  #include &lt;set&gt;
  #include &lt;string&gt;
  
  
  std::string overlap_graph(const std::vector&lt;std::string&gt;&amp; patterns) {
      // Overlap Graph of the k-mers collection patterns, in which a vertex exists for
      // each unique k-mer, and an edge (u,v) exists if the last k-1 characters of u are
      // equal to the first k-1 characters of v.
  
      if (patterns.size() == 1) return patterns[0] + &quot;-&gt;&quot; + patterns[0];
      // Build adjancency list O(n^2)
      std::map &lt;std::string, std::vector&lt;std::string&gt;&gt; adj;
      for (const auto&amp; kmer_u : patterns) {
          // Add kmer as key if it doesn't exist in the map and find its neighbours.
          if (adj.find(kmer_u) == adj.end()) {
              adj[kmer_u] = {};
              for (const auto&amp; kmer_v : patterns) {
                  if ((kmer_u != kmer_v) &amp;&amp;
                      (kmer_u.substr(1, kmer_u.length() - 1) == kmer_v.substr(0, kmer_v.length() - 1)) &amp;&amp; 
                      (std::find(adj[kmer_u].begin(), adj[kmer_u].end(), kmer_v) == adj[kmer_u].end())) {
                      adj[kmer_u].push_back(kmer_v);
                  }
              }
          } // Otherwise continue.
      }
  
      // Convert to string O(n).
      std::string ans;
      for (auto const&amp; key_value : adj) {
          std::string kmer_u{ key_value.first };
          std::vector&lt;std::string&gt; kmers_v{ key_value.second };
          if (!kmers_v.empty()) {
              ans.append(kmer_u + &quot;-&gt;&quot; + kmers_v[0]);
              for (std::size_t kmer_v{ 1 }; kmer_v &lt; kmers_v.size(); kmer_v++) {
                  ans.append(',' + kmers_v[kmer_v]);
              }
              ans.push_back('\n');
          }
      }
      return ans;
  }
  
  
  void tests() {
      /* Sample Dataset */
      std::vector&lt;std::string&gt; patterns{ {&quot;AAG&quot;}, {&quot;AGA&quot;}, {&quot;ATT&quot;}, {&quot;CTA&quot;}, {&quot;CTC&quot;}, {&quot;GAT&quot;},
                                         {&quot;TAC&quot;}, {&quot;TCT&quot;}, {&quot;TCT&quot;}, {&quot;TTC&quot;} };
      std::string answer{ &quot;TTC-&gt;TCT\nCTA-&gt;TAC\nAAG-&gt;AGA\nCTC-&gt;TCT\nTCT-&gt;CTA,CTC\nAGA-&gt;GAT\nGAT-&gt;ATT\nATT-&gt;TTC\n&quot; };
      std::cout &lt;&lt; answer &lt;&lt; std::endl;
      // std::cout &lt;&lt; (overlap_graph(patterns) == answer) &lt;&lt; std::endl;
      std::cout &lt;&lt; overlap_graph(patterns) &lt;&lt; std::endl;
  }
  
  
  void solution() {
      std::vector&lt;std::string&gt; patterns;
  
      std::string pattern;
      while (std::cin &gt;&gt; pattern) {
          patterns.push_back(pattern);
      }
      std::cout &lt;&lt; overlap_graph(patterns) &lt;&lt; std::endl;
  }
  
  
  int main() {
      //tests();
      solution();
  }
  </code></pre>
   6628: <p>You will want to create a self loop for a <span class="math-container">$k$</span>-mer <span class="math-container">$s$</span> whenever <span class="math-container">$s_1,...,s_{k-1} = s_2,...,s_k$</span>. This will only happen when all of the characters of the <span class="math-container">$k$</span>-mer are identical, as <span class="math-container">$s_1=s_2, s_2=s_3,...,s_{k-1}=s_k$</span>.</p>
  