A ring from its pieces
A phage genome is a ring of the letters A, C, G and T. A sequencer has read it in pieces: for each position of the ring, a piece of k letters starting there (a ring has no end, so the last pieces wrap round through the start). The pieces are shuffled, nobody knows where each stood, and identical pieces may occur several times. Assemble the ring.
If several rings fit the pieces, any will do. The fifth test is the real phage φX174 (NCBI RefSeq NC_001422.1, 5386 letters) with k = 12, the sixth human mitochondria (NC_012920.1, 16,569 letters) with k = 16.
Input
The first line holds n and k (2 ≤ k ≤ n ≤ 200,000, k ≤ 32), the length of the ring and of a piece. Then n lines of k letters, the pieces in arbitrary order. They are guaranteed to come from some ring of length n.
Output
A string of n letters: the ring read from any place. Its pieces of length k, taken round the ring, must coincide exactly with the given ones, repeats included.
Examples
Example 1
7 3 GAT CAG TTA AGA ACA ATT TAC
GATTACA
Example 2
10 3 GAC ATG TGC CAT TTG GCA ACA ATT CAT TGA
GACATGCATT
Limits
- Time · Python
- 6000 ms
- Time · Go
- 3000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Neighbouring pieces of the ring overlap by k − 1 letters. Try making the vertices of the graph not the pieces themselves but their overlaps.
2Hint 2
If you go from piece to piece choosing any fitting continuation, in sample 2 you can return to the start without using all the pieces. What to do with the rest?
3The idea
The de Bruijn graph: the vertices are strings of length k − 1, and each piece is an edge from its first k − 1 letters to its last. The ring is a closed path going along every edge exactly once, that is, an Eulerian circuit. It exists: in a ring every vertex has as many incoming edges as outgoing, and the graph is connected. Conversely, any Eulerian circuit reads as a ring with the same pieces. So it is enough to find any Eulerian circuit, by Hierholzer's algorithm.
4Walkthrough
A dictionary “vertex → list of the ends of its edges” and a pointer to the next unvisited edge for each vertex. A stack: while the vertex on top has an unvisited edge, go along it and push its end; otherwise pop the vertex into the answer. In a directed graph an edge is visible only from its start, so no “walked” marks are needed: the pointer is enough. The answer read backwards is the sequence of the circuit's vertices; the ring is the first vertex and the last letters of all the others, without the repeated tail of k − 1 letters.
Why a simple “go while you can” walk will not do: in the second sample it can go GA → AC → CA → AT → TT → TG and return to GA at once. There are no more edges there, while the pieces ATG, TGC, GCA and the second CAT are left unvisited. Hierholzer at this moment steps back to TG, which still has an edge, and splices in the missed loop TG → GC → CA → AT → TG.
The assembled ring need not coincide with the real genome. In the fifth test ten different strings of 11 letters occur in φX174 more than once, and different Eulerian circuits give different rings with the same pieces, which is why the check accepts any of them. With k = 14 the ring would be unique: the article tells about this.
4+Solution
5Complexity
O(n · k): each edge is walked once, and strings of length k are hashed and copied. Memory is a dictionary of n edges.
6Common mistakes
- A walk without splicing. It gets stuck at the first repeat that closes a loop too early; the ring comes out shorter than n.
- Pieces as vertices. Then the ring is a path through all the vertices, a Hamiltonian one, and searching for it by brute force is hopeless already at a hundred pieces.
- Repeats thrown away. Identical pieces are different edges: if they are stored in a set, there are fewer edges and the ring gets shorter.