Circuits and Starting Points

Enumerate every distinct linear reconstruction of a circular Euler graph.

Circuits and Starting Points: computed model records
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.

The problem

A linear read whose k-mer graph is an Euler circuit closes back on itself. The graph has no degree imbalance, so every node is a possible starting point for the same set of edges. Different starts rotate the reconstructed string, and branches can produce more than one order. A complete answer therefore needs the number of distinct node starts and every distinct reconstruction, not one traversal chosen by a hidden tie-break.

Trace the program

For ATGGAT with k equal to three, the windows are ATG, TGG, GGA and GAT. The four nodes form a ring AT to TG to GG to GA to AT. Starting at AT gives ATGGAT; starting at TG gives TGGATG; starting at GG gives GGATGG; starting at GA gives GATGGA. All four strings are rotations of the same ring. The program uses ordinary linear windows only, so it does not add a wrap-around window that was never observed.

The live graph

Edit the read or k and run the program. The result reports whether the graph is a circuit, how many node starts produce complete trails, and every distinct reconstruction in sorted order. Reset restores the demonstration read.

import json
from bio_data import DNA_BASES

def nodes_of(edges):
    nodes = []
    for a, b in edges:
        for v in (a, b):
            if v not in nodes:
                nodes.append(v)
    return nodes

def degrees(nodes, edges):
    out = {v: 0 for v in nodes}
    inc = {v: 0 for v in nodes}
    for a, b in edges:
        out[a] += 1
        inc[b] += 1
    return (out, inc)

def weakly_connected(nodes, edges):
    adj = {v: set() for v in nodes}
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    seen = {nodes[0]}
    stack = [nodes[0]]
    while stack:
        v = stack.pop()
        for w in adj[v]:
            if w not in seen:
                seen.add(w)
                stack.append(w)
    return len(seen) == len(nodes)
data = json.loads(input())
s, k = (data['sequence'], data['k'])
if k < 2 or k > len(s) or any((b not in DNA_BASES for b in s)):
    raise ValueError('invalid input')
edges = [(s[i:i + k][:-1], s[i:i + k][1:]) for i in range(len(s) - k + 1)]
nodes = nodes_of(edges)
out, inc = degrees(nodes, edges)
is_cycle = weakly_connected(nodes, edges) and all((out[v] == inc[v] for v in nodes))
strings, starts = (set(), 0)
if is_cycle:
    for start in nodes:
        found = []

        def walk(v, used, path):
            if len(used) == len(edges):
                found.append(path)
                return
            for i, (a, b) in enumerate(edges):
                if i not in used and a == v:
                    walk(b, used | {i}, path + [b])
        walk(start, frozenset(), [start])
        if found:
            starts += 1
        for p in found:
            strings.add(p[0] + ''.join((v[-1] for v in p[1:])))
result = {'cycle': is_cycle, 'starts': starts, 'reconstructions': sorted(strings)}
print(result)

{
  "cycle": true,
  "starts": 4,
  "reconstructions": [
    "ATGGAT",
    "GATGGA",
    "GGATGG",
    "TGGATG"
  ]
}
Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'

Your turn

For each read whose linear k-mer graph is a connected Euler circuit, return cycle, the number of distinct node start choices, and every distinct reconstruction in sorted order. Use only the read's ordinary overlapping k-mers; do not add wrap-around windows. Set result to an object with cycle, starts and reconstructions.

import json
result = {'cycle': False, 'starts': 0, 'reconstructions': []}
print(result)

For each read whose linear k-mer graph is a connected Euler circuit, return cycle, the number of distinct node start choices, and every distinct reconstruction in sorted order. Use only the read's ordinary overlapping k-mers; do not add wrap-around windows. Set result to an object with cycle, starts and reconstructions.

{
  "cycle": false,
  "starts": 0,
  "reconstructions": []
}
Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'

Boundaries and interpretation

Rotating a circuit is a presentation choice inside this model; it does not recover the biological origin of the read. The page counts node starts, not every edge rotation when parallel edges exist, and it deduplicates only reconstructed strings. A circular graph built from a linear read is still a graph of observed windows, not proof that the original molecule was circular.

The starts count is the number of nodes that produce a complete trail, not the number of rotations of one fixed path. Two different starts can produce the same string when the graph has repeated labels, which is why the strings are deduplicated after enumeration.

The starts count is determined from the first-occurrence node order, not from the sorted string order. A node that produces no complete trail is not counted, and repeated strings are collapsed only after all starts have been tried. The output therefore keeps the distinction between a start choice and a distinct reconstruction.

Recap

Synthetic data: CC0-1.0. No personal data are sent anywhere.