An Algorithm That Builds a Set of Strings Given Its Overlap Graph

The k-overlap graph for a set of strings is a graph such that each vertex corresponds to a string and there is a directed edge between two vertices if there is an overlap of at least k characters between their corresponding strings. Given a directed graph G, an integer k ? 1, and a finite alphabet ? of at least two symbols, we propose an algorithm to obtain a set of strings C, written over ?, such that G is its k-overlap graph. The algorithm runs in exponential time on the maximum degree of G, due to the size of the returned strings, but in polynomial time on k, |?|, and the size of the graph. A practical application of this algorithm is its use to prove the NP-hardness of Minimum Contig Problems family (MCP) and its variation MCPr, which are based on the DNA Fragment Assembly problem.