Construct the Overlap Graph of a Collection of k-mers

[hamidgasmi]

Construct the overlap graph of a collection of k-mers.

Input: A collection Patterns of k-mers.

Output: The overlap graph Overlap(Patterns), in the form of an adjacency list.

To help determine the order of the k-mers that make up a long string Text, we can attempt to create an Overlap Graph of the k-mers, 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.

Input Format. The input contains a single k-mer on each line.

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” (no quotes), where u and v are both k-mers. The following would be an example of an edge for k = 3: ACG -> CGT. 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

Constraints. k ≤ 100; |Patterns| ≤ 50