Construct the Overlap Graph of a Collection of k-mers

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];
for (const auto& kmer_u : patterns) {
// Add kmer as key if it doesn't exist in the map and find its neighbours.
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)) &&
}
}
} // 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::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();
}

• 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. May 26 '21 at 1:24
• 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 May 26 '21 at 4:32
• @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. May 27 '21 at 4:14
• 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. May 27 '21 at 18:12
• 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. May 27 '21 at 18:27

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