2
$\begingroup$

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();
}
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ May 26 at 1:24
  • $\begingroup$ 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 $\endgroup$ May 26 at 4:32
  • $\begingroup$ @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. $\endgroup$
    – Gonzo
    May 27 at 4:14
  • $\begingroup$ 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. $\endgroup$ May 27 at 18:12
  • $\begingroup$ 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. $\endgroup$ May 27 at 18:27
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.