Edges from Prefixes and Suffixes

Build nodes and one labeled edge per k-mer occurrence, preserving parallel edges.

Edges from Prefixes and Suffixes: computed model records
Original synthetic inputs; computed records, not biological motion. The written trace below is the text equivalent.

The problem

A de Bruijn graph turns each observed k-mer into an edge. The source is the first k minus one letters and the target is the last k minus one letters. Nodes are the distinct overlap strings, while edges belong to occurrences. When the same k-mer appears more than once, the graph has parallel edges with different edge identifiers. Nodes are listed in first-occurrence order so a reader can follow the construction without sorting away that order.

Trace the program

For ATGCG with k equal to three, ATG creates AT to TG, TGC creates TG to GC, and GCG creates GC to CG. Four nodes appear in the order AT, TG, GC, CG, and three edge records follow the original windows. The edge identifier is its zero-based position in that list. A repeated window such as AAA in a longer run creates the same source and target twice, but the two occurrences remain two edges.

The live graph

Edit the sequence, k, or source and run the program. The result contains the first-occurrence node list and one edge record for every window. Reset restores the demonstration sequence.

import json
from bio_data import DNA_BASES
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')
nodes, edges = ([], [])
for i in range(len(s) - k + 1):
    x = s[i:i + k]
    a, b = (x[:-1], x[1:])
    if a not in nodes:
        nodes.append(a)
    if b not in nodes:
        nodes.append(b)
    edges.append({'id': len(edges), 'kmer': x, 'source': a, 'target': b})
result = {'nodes': nodes, 'edges': edges}
print(result)

{
  "nodes": [
    "AT",
    "TG",
    "GC",
    "CG"
  ],
  "edges": [
    {
      "id": 0,
      "kmer": "ATG",
      "source": "AT",
      "target": "TG"
    },
    {
      "id": 1,
      "kmer": "TGC",
      "source": "TG",
      "target": "GC"
    },
    {
      "id": 2,
      "kmer": "GCG",
      "source": "GC",
      "target": "CG"
    }
  ]
}
Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'

Your turn

Build the directed multigraph for each supplied read and k. Return nodes in first-occurrence order and one edge record per k-mer, with consecutive integer ids, source prefix, target suffix, and original k-mer. Reject invalid k or letters. Set result to an object with nodes and edges.

import json
data = json.loads(input())
s, k = (data['sequence'], data['k'])
nodes = []
for i in range(len(s) - k + 1):
    x = s[i:i + k]
    for v in (x[:-1], x[1:]):
        if v not in nodes:
            nodes.append(v)
result = {'nodes': nodes, 'edges': []}
print(result)

Build the directed multigraph for each supplied read and k. Return nodes in first-occurrence order and one edge record per k-mer, with consecutive integer ids, source prefix, target suffix, and original k-mer. Reject invalid k or letters. Set result to an object with nodes and edges.

{
  "nodes": [
    "AT",
    "TA"
  ],
  "edges": []
}
Browse the declared helper library
"""Declared input/model data only; algorithms are written in each program."""
DNA_BASES = 'ACGT'

Boundaries and interpretation

The graph is built from one declared read and its ordinary linear windows. It does not add circular wrap-around edges, reverse-complement reads, or paired-read links. A single edge occurrence is not a unique sequence: parallel edges can spell the same k-mer. The graph also says nothing about which path a sequencing instrument actually followed, and it omits coverage, quality, and error models.

Edge ids are positions in the window sequence, so removing a duplicate would renumber every later edge and change the declared output. A self-loop still has one source and one target, and two self-loops remain two edges. The node order is a construction order, not a sorted dictionary; sorting it would change the declared output.

The edge list is ordered by window position, and the node list by first appearance across those windows. Those two orders are independent: a later edge can introduce a node that sorts before an earlier node. The serializer keeps both orders because they record the construction rather than a canonical graph labeling.

Recap

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