<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>

CC BY-SA 4.0
2021-05-26T01:22:23.790Z
2021-05-26T01:22:23.790Z
Throckmorton
<p>The usual way to avoid loops in linked lists is to keep a record of the things that have already been used / visited, and stop when an already visited thing has been seen again (or when there is nothing more to visit).</p>

CC BY-SA 4.0
2021-05-25T03:12:08.787Z
2021-05-25T03:12:08.787Z
gringer
<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>

CC BY-SA 4.0
2021-05-26T01:24:08.237Z
I think this is actually a de-bruijn as opposed to an overlap graph. I believe an overlap graph has an edge whenever **any positive length** suffix of a node overlaps with the prefix of another node.
Throckmorton
CC BY-SA 4.0
2021-05-26T04:32:56.563Z
Also, since you are only concerned with length $k-1$ overlaps, you can find all of the edges in $O(n)$ time, since each node can only have 4 possible outgoing edges. I can extend my answer to include details on this if interested
Throckmorton
CC BY-SA 4.0
2021-05-27T04:14:00.277Z
@Throckmorton Thank you for the feedback - I really appreciate it. However, in the de Bruijn graph, the nodes are the $|k-1|$  unique k-mers whereas in the overlap graph the nodes are the unique $|k|$ k-mers. For instance, the $k=3$ de Bruijn graph for genome AGT will be AG->GT and the overlap graph is AGT->AGT (I am actually having troubles with this part - why did we need to add the self-loop here?). I agree with you that the de Bruijn graph can be solved in $O(n)$  as we don't need to check for duplicates, ie. for TTTT and $k=3$ the graph is TT->TT, TT.
Gonzo
CC BY-SA 4.0
2021-05-27T18:12:05.480Z
You can define $k$ to be whatever you want. The definition of a de-Bruin graph is a graph just all $k$-mers as nodes and an edge whenever there is a $k-1$ overlap between two nodes. This is exactly what the docstring in your question states.
Throckmorton
CC BY-SA 4.0
2021-05-27T18:27:27.270Z
Also, I don’t think there should be a self edge for AGT, in fact inter example the node “ACT” doesn’t have a self edge either.
Throckmorton
CC BY-SA 4.0
2021-05-27T18:29:19.653Z
And the O(n) time isn’t due to duplicates, it’s because for a single node you can find all out edges in constant time.
Throckmorton
<ngs><k-mer><homework><c++><graphs>
Construct the Overlap Graph of a Collection of k-mers
# Construct the Overlap Graph of a Collection of k-mers

(Asked by: username_0 on 2021-05-24)

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 
#include 
#include 
#include 
#include 
#include 


std::string overlap_graph(const std::vector& 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 > 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 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 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 patterns;

    std::string pattern;
    while (std::cin >> pattern) {
        patterns.push_back(pattern);
    }
    std::cout << overlap_graph(patterns) << std::endl;
}


int main() {
    //tests();
    solution();
}

**Tags:** ngs, k-mer, homework, c++, graphs
> **Comments:**
> **username_1**: I think this is actually a de-bruijn as opposed to an overlap graph. I believe an overlap graph has an edge whenever **any positive length** suffix of a node overlaps with the prefix of another node.  
> **username_1**: Also, since you are only concerned with length $k-1$ overlaps, you can find all of the edges in $O(n)$ time, since each node can only have 4 possible outgoing edges. I can extend my answer to include details on this if interested  
> **username_0**: @Throckmorton Thank you for the feedback - I really appreciate it. However, in the de Bruijn graph, the nodes are the $|k-1|$  unique k-mers whereas in the overlap graph the nodes are the unique $|k|$ k-mers. For instance, the $k=3$ de Bruijn graph for genome AGT will be AG->GT and the overlap graph is AGT->AGT (I am actually having troubles with this part - why did we need to add the self-loop here?). I agree with you that the de Bruijn graph can be solved in $O(n)$  as we don't need to check for duplicates, ie. for TTTT and $k=3$ the graph is TT->TT, TT.  
> **username_1**: You can define $k$ to be whatever you want. The definition of a de-Bruin graph is a graph just all $k$-mers as nodes and an edge whenever there is a $k-1$ overlap between two nodes. This is exactly what the docstring in your question states.  
> **username_1**: Also, I don’t think there should be a self edge for AGT, in fact inter example the node “ACT” doesn’t have a self edge either.  
> **username_1**: And the O(n) time isn’t due to duplicates, it’s because for a single node you can find all out edges in constant time.  

---

## 2 answers

### Answer by username_1 on 2021-05-26. Score: 1

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$.


---

### Answer by username_2 on 2021-05-25. Score: 0

The usual way to avoid loops in linked lists is to keep a record of the things that have already been used / visited, and stop when an already visited thing has been seen again (or when there is nothing more to visit).


---

