Rosalind — Bioinformatics Textbook Track — Assembly

BA3B — Reconstruct a String from its Genome Path

The path is already ordered, so the string is the first k-mer plus one symbol from each after it. Finding the order is what BA3C and BA3H are for.

BA3C — Construct the Overlap Graph of a Collection of k-mers

solved Problem statement

An edge where one k-mer's suffix is another's prefix. Written with `source` and `target` because `from` and `to` are reserved words.

BA3D — Construct the De Bruijn Graph of a String

solved Problem statement

Nodes are (k-1)-mers and edges are the k-mers, which is the inversion that turns assembly into an Eulerian path problem rather than a Hamiltonian one.

BA3E — Construct the De Bruijn Graph of a Collection of k-mers

solved Problem statement

The same construction from a bag of reads rather than a string. A duplicate k-mer stays duplicated: it is evidence of a repeat, not noise.

BA3H — Reconstruct a String from its k-mer Composition

solved Problem statement

Reads become edges, not nodes — which makes assembly an Eulerian path, solvable in linear time. Reads as nodes would give a Hamiltonian path instead: the same data, a different graph, and the difference between tractable and NP-hard.

BA3I — Find a k-Universal Circular String

solved Problem statement

Every (k-1)-mer has two edges in and two out, so the graph is balanced and the walk closes. Returns a different valid string from the published one; the assertion reads around the circle and checks all 2^k k-mers appear exactly once.

BA3J — Reconstruct a String from its Paired Composition

solved Problem statement

Paired reads pin down a repeat that either read alone would be ambiguous inside. The two halves must agree wherever they overlap, and checking that agreement is what makes a wrong assembly detectable.

BA3K — Generate Contigs from a Collection of Reads

solved Problem statement

What assembly actually produces. BA3H asked for the genome, which needs an Eulerian path to exist and be unique — real data gives neither. Where the graph branches the reads genuinely do not say which way the genome went, so the honest output is the unambiguous stretches and no more.

BA3L — Construct a String Spelled by a Gapped Genome Path

solved Problem statement

BA3J had to find the path; here it is given, so what remains is the overlap check — a path whose two halves disagree spells nothing at all, however valid it looked in the graph.