Algos Problem 1: Replikationsstart

Question 1

Which is the slowest / fastest run time?

• |n|^2∙k
• 4^k+|n|∙k
• |n|∙k∙log(|n|)
• |n|

Answer 1

naive and slow:
|n|^2∙k

fast:
|n|

Question 2

What is a clump?

Answer 2

Formal: A k-mer forms an (L, t)-clump inside Genome if there
is a short (length L) interval of Genome in which it appears
many (at least t) times.

Question 3

DNA Strands Directions?

Answer 3

The two strands run in opposite directions
(from 5’ to 3’)

Question 4

Different Lifestyles of Reverse and Forward Half-Strands ?

Answer 4

The reverse half-strand lives a double-stranded life most of the time.

The forward half-strand spends a large portion of its life singlestranded, waiting to be replicated.

Question 5

How does Asymmetry of Replication Affect
Nucleotide Frequencies?

Answer 5

Single-stranded DNA has a much higher mutation rate than double-stranded DNA.

Thus, if one nucleotide has a greater mutation rate, then we should observe its shortage on the forward half-strand that lives single-stranded life!

Question 6

Which nucleotide (A/C/G/T) has the highest mutation rate? Why?

Answer 6

The Peculiar Statistics of #G - #C

Cytosine (C) rapidly mutates into thymine (T) through deamination;
deamination rates rise 100-fold when DNA is single stranded!

• Forward half-strand (single-stranded life): shortage of C, normal G
• Reverse half-strand (double-stranded life): shortage of G, normal C

Question 7

You walk along the genome and pass OriC. You notice that #G - #C has been ____ and then suddenly starts ______.

Answer 7

has been decreasing and then suddenly starts increasing

Question 8

Skew Diagram ?

Answer 8

Skew(k): #G - #C for the first k nucleotides of Genome.

Skew diagram: Plot Skew(k) against k