Module algorithms_edu::problems::graph::reconstruct_string_from_lmers

Problem

Reconstruct the original string from all substrings of length l of the string. For example, reconstruct "ATGCAGGT" from ["ATG", "TGC", "GCA", "CAG", "AGG", "GGT"]. (note that the collection of l-mers is disordered)

Strategy

This problem can be solved by finding a Eulerian path through the graph where vertices represent l-mers and edges represent l-1 overlaps among the l-mers. For example, between two vertices ATG and TGC, there is a directed edge pointing from ATG to TGC, because they have an l-1-meroverlap, i.e."ATG"[1..] == "TGC"[.."TGC".len() - 1]`

Functions

reconstruct_string