Minimum GC Skew

Intermediate Bioinformatics GC Skew Cumulative Sums Replication Origin Genomics
Significance:

In most bacterial genomes the leading and lagging strands accumulate mutations at
different rates, leaving an asymmetry in G versus C content. Plotting the running difference along the
genome produces a characteristic V shape whose minimum marks the replication origin (oriC) — the
place where DNA replication begins. This is one of the cleanest examples in all of bioinformatics of a
simple statistic revealing a deep biological structure.

Statement

Define Skew(i) as the number of G minus the number of C in the first i characters
of a genome, with Skew(0) = 0.

Given a genome, find every position i (from 0 to n) at which Skew(i) attains its minimum value.

Print all such positions in increasing order, separated by single spaces, on one line.

Input — read from standard input
Variable Type Description
genome
line 1
 str The genome sequence
1 <= len(genome) <= 5000, uppercase A, C, G, T only

These variables are already read for you in the starter code on the right.

Output

str space-separated positions of minimum skew, in increasing order, on one line

Sample Cases
Sample 1
Input
CCTATCGGTGGATTAGCATGTCCCTGTACGTTTCGCCGCGAACTAGTTCACACGGCTTGATGGCAAATGGTTTTTCCGGCGACCGTAATCGTCCACCGAG
Expected Output
53 97
The running skew bottoms out at a single position, marking the candidate replication origin.
Sample 2
Input
GAGCCACCGCGATA
Expected Output
8 10
A short genome where the minimum is reached early.

Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 1 <= length(genome) <= 5000
  • Positions are 0-based prefix lengths: position i means the prefix of length i
  • Skew(0) = 0 is always a candidate and must be considered
  • If several positions tie for the minimum, print all of them
Further Reading
  • Build the skew array in one pass: +1 for G, -1 for C, 0 otherwise.
  • Track the running minimum and the positions achieving it, or compute the array then scan it.
  • Position 0 (the empty prefix, skew 0) counts — a genome starting with many Cs will not include it,
    but one starting with G might.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: genome (str)
Next Problem
Six-Frame ORF Finder