de_bruijn_asm.py

def eulerian_walk(nodes, start):
    tour = []

    def visit(n):
        if n in nodes:
            while nodes[n]:
                visit(nodes[n].pop())
        tour.append(n)
    
    visit(start)
    
    return list(reversed(tour))

def spell_out(tour):
    string = tour[0]
    for n in tour[1:]:
        string += n[-1]
    return string

read_length = 3
sequence = 'loong_loong_long_loong_long_time_ago'
reads = [sequence[i:i+read_length] for i in range(len(sequence) - read_length + 1)]

nodes = {}
for read in reads:
    a = read[:-1]
    b = read[1:]
    if not a in nodes:
        nodes[a] = []
    nodes[a].append(b)

print('ground truth:')
print(sequence)
print('reads:')
print(reads)
print('nodes:')
print(nodes)

start = next(iter(nodes.keys()))
tour = eulerian_walk(nodes, start)

print('tour:')
print(tour)
print('reconstructed:')
print(spell_out(tour))