Keep the longest chains

[nilamo]

So '7 8 9' is a root fragment of two different chains...

With that in mind, I'd recommend the following steps:
1) sort your list of chain-framents by length. The shortest ones are always the beginning of a chain, so they should be the first ones you process.
2) for each chain fragment, check if the beginning of the fragment matches any other complete fragment.
3) keep track of the chains in a dict, with the keys being the root of the fragment and the values being a dict of branching fragments that continue the chain.

You'll probably need to write a recursive function for step 2 that will find the deepest matching node.

After writing some helper functions, your code will probably look like:

fragments = [
    '1 2 3 4',
    '7 8 9 10 11 12',
    '4 5 2 1 8'
# etc
]

chains = {}
fragments.sort()
for fragment in fragments:
    match = find_root_fragment(fragment, chains)
    if match is None:
        match = chains
    match[fragment] = {}