Rosalind — Bioinformatics Stronghold — Assembly

ASMQ — Assessing Assembly Quality with N50 and N75

N50 is the contig length at which half the assembly sits in contigs that long or longer. It is the standard summary and a gameable one: joining contigs wrongly raises it, so a high N50 is evidence of a long assembly rather than a correct one.

LONG — Genome Assembly as Shortest Superstring

solved Problem statement

Shortest superstring is NP-hard in general. This is solvable only because the problem guarantees every pair overlaps by more than half their length, which makes the correct overlap unique and a greedy merge safe. GREP shows what happens when that guarantee is dropped.

PCOV — Genome Assembly with Perfect Coverage

solved Problem statement

Perfect coverage makes the De Bruijn graph a single cycle, so it is walked directly rather than searched. The assertion checks every read appears in the doubled string, which is what cyclic containment means.

GASM — Genome Assembly Using Reads

solved Problem statement

A read gives no clue which strand it came from, so the graph holds every read and its reverse complement and falls into two mirror cycles. Returns AATCTGT — a rotation of the reverse complement of GATTACA, which the assertion checks up to both rotation and strand.

GREP — Genome Assembly with Perfect Coverage and Repeats

solved Problem statement

PCOV returns one answer; this is the honest version. Repeats make the Eulerian cycle non-unique and all six cycles are genomes consistent with the reads — so the reads do not determine the chromosome, and reporting one would be picking arbitrarily.