Outline

• An Intro to DNA Replication

• Hidden Messages in the Replication Origin
Finding Replication Origins in Bacterial Genomes • Hunting for Frequent Words
Algorithmic Warmup
• A Faster Frequent Words Approach
• Some Hidden Messages are More Surprising than
Others
• An Explosion of Hidden Messages
• Replication Asymmetry Leads Us to the Replication
Origin

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

A Prophetic One-Liner (1953) The “Copying Mechanism”

James
Watson
"It has not escaped our
notice that the specific
Francis pairing we have
Crick postulated
immediately suggests
a possible copying
mechanism for the
genetic material."

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 The “Copying Mechanism” The “Copying Mechanism”

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

The Most Beautiful Experiment in Biology

Three Hypotheses for DNA Replication
(1958)

Meselson and Stahl’s insight: one isotope of nitrogen,

Nitrogen-14 (14N), is lighter and more abundant than
Nitrogen-15 (15N).

STOP: Which hypothesis was Watson & Crick’s?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 The Most Beautiful Experiment in Biology The Most Beautiful Experiment in Biology
(1958) (1958)

Meselson and Stahl’s insight: one isotope of nitrogen, Meselson and Stahl’s insight: one isotope of nitrogen,
Nitrogen-14 (14N), is lighter and more abundant than Nitrogen-14 (14N), is lighter and more abundant than
Nitrogen-15 (15N). Nitrogen-15 (15N).

Meselson and Stahl grew E. coli for many rounds of Meselson and Stahl grew E. coli for many rounds of
replication in a 15N medium, which caused the bacteria to gain replication in a 15N medium, which caused the bacteria to gain
weight as they absorbed the heavier isotope into their DNA. weight as they absorbed the heavier isotope into their DNA.
They then transferred the heavy E. coli cells to a less dense They then transferred the heavy E. coli cells to a less dense
14 14
N medium. N medium.

Key Point: any daughter DNA would be lighter!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

The Most Beautiful Experiment in Biology The Most Beautiful Experiment in Biology
(1958) (1958)

STOP: After one round of replication, Meselson and Stahl STOP: After one round of replication, Meselson and Stahl
spun the DNA in a centrifuge. Why? spun the DNA in a centrifuge. Why?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 The Most Beautiful Experiment in Biology The Most Beautiful Experiment in Biology
(1958) (1958)

STOP: What would we observe in the centrifuge for the Key Point: After two rounds, the DNA divided into two
other two models after two rounds of replication? different densities!
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

The Most Beautiful Experiment in Biology

What a Biologist Sees...
(1958)

STOP: Does this prove that the semiconservative method

must be true?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 What a Bioinformatician Sees... What a Bioinformatician Sees...

String: a contiguous collection of symbols. String: a contiguous collection of symbols.

...ACTGATAACCCAGTATCAGACCAGTATCGAGGACGATACGTA...
DNA String

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

What a Bioinformatician Sees... What a Computer Scientist Sees...

String: a contiguous collection of symbols. String: a contiguous collection of symbols.

...ACTGATAACCCAGTATCAGACCAGTATCGAGGACGATACGTA... ...ACTGATAACCCAGTATCAGACCAGTATCGAGGACGATACGTA...
DNA String DNA String

Complicated Biological Process Complicated Biological Process

Copy 1
...ACTGATAACCCAGTATCAGACCAGTATCGAGGACGATACGTA...
...ACTGATAACCCAGTATCAGACCAGTATCGAGGACGATACGTA...
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
Copy 2
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Origin of Replication The Finding ori Problem

Replication begins in a region called the replication Origin of Replication Problem

origin (denoted ori). • Input: A DNA string genome.
• Output: The location of ori in genome.

STOP: Is the Hidden

Message Problem a
computational problem?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Finding the Origin of Replication

Finding the Origin of Replication
the wet-way
How can we find ori in a genome? How can we find ori in a genome?

Let’s hack out this DNA Let’s hack out this DNA
fragment. Can the fragment. Can the
genome replicate without genome replicate without
it? it?

I need more information

before I can hack this
problem.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Looking for ori Looking for ori

Verified ori of Vibrio cholerae, the bacterium that Verified ori of Vibrio cholerae, the bacterium that
causes cholera (~500 nucleotides): causes cholera (~500 nucleotides):
atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac
ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt
gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc

There must be a hidden message telling the cell to

start replication here.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

The Hidden Message Problem The Hidden Message Problem

Hidden Message Problem Hidden Message Problem

• Input: A string text (representing ori). • Input: A string text (representing ori).
• Output: A hidden message in text. • Output: A hidden message in text.

STOP: Is the Hidden

Message Problem a
computational problem?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 We Have Two Scientific Problems Outline

1. Given a bacterial genome (~3 Mbp), where is ori? • An Intro to DNA Replication
• Hidden Messages in the Replication Origin
• Hunting for Frequent Words
• A Faster Frequent Words Approach
• Some Hidden Messages are More Surprising than
Others
• An Explosion of Hidden Messages
• Replication Asymmetry Leads Us to the Replication
2. Given ori (~500 bp), what is the “hidden message” Origin
saying that replication should start here?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Hidden Message Problem Revisited Hidden Message Problem Revisited

Hidden Message Problem Hidden Message Problem

• Input: A string text (representing ori). • Input: A string text (representing ori).
• Output: A hidden message in text. • Output: A hidden message in text.

Replication initiation is mediated by a protein called

The notion of “hidden message ” is not defined. DnaA .

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Hidden Message Problem Revisited Hidden Message Problem Revisited

Hidden Message Problem Hidden Message Problem

• Input: A string text (representing ori). • Input: A string text (representing ori).
• Output: A hidden message in text. • Output: A hidden message in text.

Replication initiation is mediated by a protein called Replication initiation is mediated by a protein called
DnaA . DnaA .

DnaA binds to a short segment in ori known as a DnaA DnaA binds to a short segment in ori known as a DnaA
box, a hidden message saying: “bind here!” box, a hidden message saying: “bind here!”

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Hidden Message Problem Revisited Hidden Message Problem Revisited

STOP: Would it make sense for an organism to have Answer: Multiple DnaA boxes 🡪 higher chance of
multiple DnaA boxes, or just one? binding 🡪 higher “fitness”

“Nothing in biology makes

Replication initiation is mediated by a protein called sense except in the light of
DnaA . ________.”
Theodosius Dobzhansky
DnaA binds to a short segment in ori known as a DnaA
box, a hidden message saying: “bind here!”

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Hidden Message Problem Revisited Outline

Answer: Multiple DnaA boxes 🡪 higher chance of • An Intro to DNA Replication

binding 🡪 higher “fitness” • Hidden Messages in the Replication Origin
• Hunting for Frequent Words
“Nothing in biology makes • A Faster Frequent Words Approach
sense except in the light of • Some Hidden Messages are More Surprising than
evolution.” Others
Theodosius Dobzhansky
• An Explosion of Hidden Messages
• Replication Asymmetry Leads Us to the Replication
Origin

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Counting Words Counting Words

atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac
ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt
gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc

We are looking for surprisingly frequent substrings We are looking for surprisingly frequent substrings
(contiguous strings appearing within) this ori. (contiguous strings appearing within) this ori.

First: let’s count how often a given substring occurs.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Counting Words Problem Counting Words Problem

Substring Counting Problem Substring Counting Problem

• Input: A string pattern and a longer string text. • Input: A string pattern and a longer string text.
• Output: The number of times pattern occurs in text. • Output: The number of times pattern occurs in text.

STOP: How many times does ATA occur in

CGATATATCCATAG?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Counting Words Problem Substring Indexing

Substring Counting Problem Key Point: We think of a string as just an array of

• Input: A string pattern and a longer string text. symbols. (So it should be 0-indexed.)
• Output: The number of times pattern occurs in text.

STOP: How many times does ATA occur in

CGATATATCCATAG?

Answer: It can be 2 or 3. For this application, we will go

with 3; that is, we count overlaps.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Substring Indexing Substring Indexing

Key Point: We think of a string as just an array of Key Point: We think of a string as just an array of
symbols. (So it should be 0-indexed.) symbols. (So it should be 0-indexed.)

The notation we use for this substring of text is:

text[7, 10]

That’s weird … why not text[7, 9]?!?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Substring Indexing Substring Indexing

Key Point: We think of a string as just an array of Key Point: We think of a string as just an array of
symbols. (So it should be 0-indexed.) symbols. (So it should be 0-indexed.)

STOP: How would we refer to this substring? STOP: How would we refer to this substring?

Answer: text[0, 3]

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Substring Indexing Substring Indexing

Key Point: We think of a string as just an array of Key Point: We think of a string as just an array of
symbols. (So it should be 0-indexed.) symbols. (So it should be 0-indexed.)

STOP: What about this substring? STOP: What about this substring?

Answer: text[3, 6]

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Substring Indexing Substring Indexing

Key Point: We think of a string as just an array of Key Point: We think of a string as just an array of
symbols. (So it should be 0-indexed.) symbols. (So it should be 0-indexed.)

STOP: What do you notice? STOP: What do you notice?

Answer: We can easily get the length of the substring by

subtracting the lower index from the upper index. (Here,
6 - 3 = 3.)
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Substring Indexing Substring Indexing

Key Point: We think of a string as just an array of Key Point: We think of a string as just an array of
symbols. (So it should be 0-indexed.) symbols. (So it should be 0-indexed.)

STOP: How would we refer to the substring of text of STOP: How would we refer to the substring of text of
length k starting at position i? length k starting at position i?

Answer: text[i, i+k]. This will be very useful!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Substring Indexing Our Idea for Counting Patterns

Key Point: We think of a string as just an array of

symbols. (So it should be 0-indexed.)

Note: We use the same notation for “subarrays” if we

want to refer to a contiguous collection of values in an
array.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Our Idea for Counting Patterns Our Idea for Counting Patterns

STOP: How STOP: How

many substrings many substrings
of length k are of length k are
there in a string there in a string
of length n? of length n?

Exercise: Try
writing
pseudocode to
count pattern
occurrences.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Pattern Counting The Frequent Words Problem

PatternCount(pattern, text) k -mer: A string of length k.

count 🡪 0
k 🡪 len(pattern)
n 🡪 len(text)
for every integer i between 0 and n – k
if text[i, i+k] = pattern
count 🡪 count + 1
return count

len(): A (typically built-in) function determining the

length (number of symbols) in a string; also works for
counting elements in an array.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 The Frequent Words Problem The Frequent Words Problem

k -mer: A string of length k. k -mer: A string of length k.

A k-mer pattern is a most frequent k -mer in a string if A k-mer pattern is a most frequent k -mer in a string if
no other k-mer is more frequent than pattern. no other k-mer is more frequent than pattern.

Frequent Words Problem

• Input: A string text and an integer k.
• Output: All most frequent k- mers in text.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

The Frequent Words Problem Solving the Frequent Words Problem

k -mer: A string of length k. Frequent Words Problem

• Input: A string text and an integer k.
A k-mer pattern is a most frequent k -mer in a string if • Output: All most frequent k-mers in text.
no other k-mer is more frequent than pattern.

Frequent Words Problem atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaac

• Input: A string text and an integer k. ctgagtggatgacatcaagataggtcgttgtatctccttcctctcgtactctcatgacca
cggaaagatgatcaagagaggatgatttcttggccatatcgcaatgaatacttgtgactt
• Output: All most frequent k-mers in text. gtgcttccaattgacatcttcagcgccatattgcgctggccaaggtgacggagcgggatt
acgaaagcatgatcatggctgttgttctgtttatcttgttttgactgagacttgttagga
tagacggtttttcatcactgactagccaaagccttactctgcctgacatcgaccgtaaat
tgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccgattgaag
STOP: Now is this problem clearly stated? atcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtt
tccttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Solving the Frequent Words Problem Solving the Frequent Words Problem

Frequent Words Problem Frequent Words Problem

• Input: A string text and an integer k. • Input: A string text and an integer k.
• Output: All most frequent k-mers in text. • Output: All most frequent k-mers in text.

Example: If text = ACGTTTCACGTTTTACGG and k = 3, Exercise: How might we solve this problem with an
then the most frequent words are ACG and TTT (both array? What subroutines would you find useful?
occur three times).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 count 3 2

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 count 3 2 2 3

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 count 3 2 2 3 1 1

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 1 1 count 3 2 2 3 1 1 1 3

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 1 1 3 2 count 3 2 2 3 1 1 1 3 2 2

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 1 1 3 2 2 3 count 3 2 2 3 1 1 1 3 2 2 3 3

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 1 1 3 2 2 3 3 1 count 3 2 2 3 1 1 1 3 2 2 3 3 1 1

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

One Frequent Words Solution One Frequent Words Solution

1. Create an array count of length len(text) - k + 1. 1. Create an array count of length len(text) - k + 1.
2. For each i, set count[i] equal to the number of times 2. For each i, set count[i] equal to the number of times
text[i, i+k] appears in text. text[i, i+k] appears in text.
3. Take k-mers having the maximum values of count[i]. 3. Take k-mers having the maximum values of count[i].

Example: text = ACGTTTCACGTTTTACGG and k = 3. Example: text = ACGTTTCACGTTTTACGG and k = 3.

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
count 3 2 2 3 1 1 1 3 2 2 3 3 1 1 3 1 count 3 2 2 3 1 1 1 3 2 2 3 3 1 1 3 1

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Solving the Frequent Words Problem Solving the Frequent Words Problem
FrequentWords(text, k) FrequentWords(text, k)
freqPatterns 🡪 an array of strings of length 0 freqPatterns 🡪 an array of strings of length 0
n 🡪 Len(text) n 🡪 Len(text)
count 🡪 array of integers of length n - k + 1 count 🡪 array of integers of length n - k + 1
for every integer i between 0 and n – k for every integer i between 0 and n – k
pattern 🡪 text[i, i+k] pattern 🡪 text[i, i+k]
count[i] 🡪 PatternCount(pattern, text) count[i] 🡪 PatternCount(pattern, text)
max 🡪 MaxArray(count) max 🡪 MaxArray(count)
for every integer i between 0 and n - k for every integer i between 0 and n - k
if count[i] = max if count[i] = max
pattern 🡪 text[i, i+k] pattern 🡪 text[i, i+k]
freqPatterns 🡪 Append(freqPatterns, pattern) freqPatterns 🡪 freqPatterns 🡪 Append(freqPatterns, pattern) freqPatterns 🡪
RemoveDuplicates(freqPatterns) RemoveDuplicates(freqPatterns)
return freqPatterns return freqPatterns

PatternCount: our pattern counting function from before STOP: This algorithm is inefficient; why? How could we
MaxArray: take maximum value in an array a make it better?
RemoveDuplicates: remove duplicates from list patterns
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Outline Arrays/Slices Store Lists of Variables

• An Intro to DNA Replication

H i T h e r e !
• Hidden Messages in the Replication Origin
0 1 2 3 4 5 6 7 8
• Hunting for Frequent Words
• A Faster Frequent Words Approach
• Some Hidden Messages are More Surprising than 1 1 2 3 5 8 13 21 34 55 89
Others 0 1 2 3 4 5 6 7 8 9 10
• An Explosion of Hidden Messages
• Replication Asymmetry Leads Us to the Replication
Origin “ACG” “TTA” “GAG” “CCT” “TAA” “GGG” “CAT”
0 1 2 3 4 5 6
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
Pevzner.
 What if the Indices Aren’t Integers? What if the Indices Aren’t Integers?

Pattern count Map/Dictionary: An Pattern count

“AA” 17 association of keys “AA” 17
Would make things
“AC” 4 with values . “AC” 4
easier when finding
“CG” 15 “CG” 15
frequent words …
“GA” 23 “GA” 23
“GG” 3 “GG” 3
“GT” 30 “GT” 30
“TA” 18 “TA” 18
“TG” 2 “TG” 2
“TT” 24 “TT” 24

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
Pevzner. Pevzner.

What if the Indices Aren’t Integers? What if the Indices Aren’t Integers?

Map/Dictionary: An Pattern count Map/Dictionary: An Pattern count

association of keys “AA” 17 association of keys “AA” 17
with values . “AC” 4 with values . “AC” 4
“CG” 15 “CG” 15
We use a variable “GA” 23 We use a variable “GA” 23
(say, freq) to refer to “GG” 3 (say, freq) to refer to “GG” 3
the map. “GT” 30 the map. “GT” 30
“TA” 18 “TA” 18
“TG” 2
Value access is like “TG” 2
“TT” 24
arrays: freq[“GT”] “TT” 24

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
Pevzner. Pevzner.
 Note that not every 2-mer is a key... Rewriting Frequent Words Pseudocode
BetterFrequentWords(text, k)
Pattern count freqPatterns 🡪 an empty array
Map/Dictionary: An freqMap 🡪 empty map
association of keys “AA” 17 n 🡪 Len(text)
for every integer i between 0 and n - k
with values . “AC” 4
pattern 🡪 text[i, i+k]
“CG” 15 if freqMap[pattern] doesn’t exist
freqMap[pattern] = 1
We use a variable “GA” 23 else
(say, freq) to refer to “GG” 3 freqMap[pattern] 🡪 freqMap[pattern] + 1
maxCount 🡪 MaxMap(freqMap)
the map. “GT” 30 for all strings pattern in freqMap
if freqMap[pattern] = maxCount
“TA” 18
freqPatterns 🡪 Append(freqPatterns, pattern)
Value access is like “TG” 2 return freqPatterns
arrays: freq[“GT”] “TT” 24
Note: We don’t need RemoveDuplicates() or Count() !
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
And this is much faster!
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
Pevzner. Pevzner.

Shortening BetterFrequentWords() Shortening BetterFrequentWords()

BetterFrequentWords(text, k) BetterFrequentWords(text, k)
freqPatterns 🡪 an array of strings of length 0 freqPatterns 🡪 an empty array of strings
freqMap 🡪 an empty map freqMap 🡪 FrequencyMap(text, k)
n 🡪 Len(text) maxCount 🡪 MaxValue(freqMap)
for every integer i between 0 and n - k for all strings pattern in freqMap
pattern 🡪 text[i, i+k] if freqMap[pattern] = maxCount
if freqMap[pattern] doesn’t exist append pattern to freqPatterns
freqMap[pattern] = 1 return freqPatterns
else
freqMap[pattern] 🡪 freqMap[pattern] + 1 FrequencyMap(text, k)
max 🡪 MaxMap(freqMap) freqMap 🡪 an empty map
for all strings pattern in freqMap n 🡪 Len(text)
if freqMap[pattern] = max for every integer i between 0 and n - k
freqPatterns 🡪 Append(freqPatterns, pattern) pattern 🡪 text[i, i+k]
return freqPatterns if freqMap[pattern] doesn’t exist
freqMap[pattern] = 1
else
Subroutine time! We can shorten the code in red. freqMap[pattern] 🡪 freqMap[pattern] + 1
return freqMap
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and
Pevzner. Pevzner.
 Outline Returning to ori of Vibrio cholerae

• An Intro to DNA Replication atcaatgatcaacgtaagcttctaagcatgatcaaggtgctcacacagtttatccacaacctgagtgga

tgacatcaagataggtcgttgtatctccttcctctcgtactctcatgaccacggaaagatgatcaagag
• Hidden Messages in the Replication Origin aggatgatttcttggccatatcgcaatgaatacttgtgacttgtgcttccaattgacatcttcagcgcc

• Hunting for Frequent Words

atattgcgctggccaaggtgacggagcgggattacgaaagcatgatcatggctgttgttctgtttatct
tgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactctgcctg
acatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacctcttgatcatcgatccga
• A Faster Frequent Words Approach ttgaagatcttcaattgttaattctcttgcctcgactcatagccatgatgagctcttgatcatgtttcc
ttaaccctctattttttacggaagaatgatcaagctgctgctcttgatcatcgtttc
• Some Hidden Messages are More Surprising than
Others
• An Explosion of Hidden Messages
• Replication Asymmetry Leads Us to the Replication
Origin

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Returning to ori of Vibrio cholerae Returning to ori of Vibrio cholerae

atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaacctgagtgga atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaacctgagtgga
tgacatcaagataggtcgttgtatctccttcctctcgtactctcatgaccacggaaagATGATCAAGag tgacatcaagataggtcgttgtatctccttcctctcgtactctcatgaccacggaaagATGATCAAGag
aggatgatttcttggccatatcgcaatgaatacttgtgacttgtgcttccaattgacatcttcagcgcc aggatgatttcttggccatatcgcaatgaatacttgtgacttgtgcttccaattgacatcttcagcgcc
atattgcgctggccaaggtgacggagcgggattacgaaagcatgatcatggctgttgttctgtttatct atattgcgctggccaaggtgacggagcgggattacgaaagcatgatcatggctgttgttctgtttatct
tgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactctgcctg tgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactctgcctg
acatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacCTCTTGATCATcgatccga acatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacCTCTTGATCATcgatccga
ttgaagatcttcaattgttaattctcttgcctcgactcatagccatgatgagCTCTTGATCATgtttcc ttgaagatcttcaattgttaattctcttgcctcgactcatagccatgatgagCTCTTGATCATgtttcc
ttaaccctctattttttacggaagaATGATCAAGctgctgCTCTTGATCATcgtttc ttaaccctctattttttacggaagaATGATCAAGctgctgCTCTTGATCATcgtttc

Most frequent 9-mers in this ori (all appear 3 times): Most frequent 9-mers in this ori (all appear 3 times):
ATGATCAAG, CTTGATCAT, TCTTGGATCA, ATGATCAAG, CTTGATCAT, TCTTGGATCA,
CTCTTGATC CTCTTGATC

STOP: Now what do you see?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Complementarity of DNA Complementarity of DNA
DNA is double-stranded, and the two strands are The reverse complement of AGTCGCATAGT is
reverse complements of each other. ACTATGCGACT.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Reverse Complement Problem Reverse Complement Problem

Reverse Complement Problem Reverse Complement Problem

• Input: A DNA string text. • Input: A DNA string text.
• Output: The reverse complement of text. • Output: The reverse complement of text.

STOP: Try to write the shortest possible pseudocode

function solving this problem.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Reverse Complement Problem Or in One Line …

Reverse Complement Problem Reverse Complement Problem

• Input: A DNA string text. • Input: A DNA string text.
• Output: The reverse complement of text. • Output: The reverse complement of text.

STOP: Try to write the shortest possible pseudocode STOP: Try to write the shortest possible pseudocode
function solving this problem. function solving this problem.

ReverseComplement(text) ReverseComplement(text)
x 🡪 Reverse(text) return Reverse(Complement(text))
y 🡪 Complement(x)
return y
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Or in One Line … Hidden Message Found!

atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaacctgagtgga
Reverse Complement Problem tgacatcaagataggtcgttgtatctccttcctctcgtactctcatgaccacggaaagATGATCAAGag
• Input: A DNA string text. aggatgatttcttggccatatcgcaatgaatacttgtgacttgtgcttccaattgacatcttcagcgcc
atattgcgctggccaaggtgacggagcgggattacgaaagcatgatcatggctgttgttctgtttatct
• Output: The reverse complement of text. tgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactctgcctg
acatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacctCTTGATCATcgatccga
ttgaagatcttcaattgttaattctcttgcctcgactcatagccatgatgagctCTTGATCATgtttcc
ttaaccctctattttttacggaagaATGATCAAGctgctgctCTTGATCATcgtttc
STOP: Try to write the shortest possible pseudocode
function solving this problem. ATGATCAAG are reverse complements and likely DnaA
||||||||| boxes (DnaA does not know which strand
ReverseComplement(text) TACTAGTTC it binds to).
return Reverse(Complement(text))

We split our work into two easy pieces! More later...

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Hidden Message Found! Homework problems
atcaatgatcaacgtaagcttctaagcATGATCAAGgtgctcacacagtttatccacaacctgagtgga
tgacatcaagataggtcgttgtatctccttcctctcgtactctcatgaccacggaaagATGATCAAGag
aggatgatttcttggccatatcgcaatgaatacttgtgacttgtgcttccaattgacatcttcagcgcc
1. What is the probability of finding a specific
atattgcgctggccaaggtgacggagcgggattacgaaagcatgatcatggctgttgttctgtttatct
tgttttgactgagacttgttaggatagacggtttttcatcactgactagccaaagccttactctgcctg
9-mer 6-times in a random 500 nucleotide
acatcgaccgtaaattgataatgaatttacatgcttccgcgacgatttacctCTTGATCATcgatccga
ttgaagatcttcaattgttaattctcttgcctcgactcatagccatgatgagctCTTGATCATgtttcc
sequence?
ttaaccctctattttttacggaagaATGATCAAGctgctgctCTTGATCATcgtttc

2. What is the probability of finding a specific

ATGATCAAG are reverse complements and likely DnaA
||||||||| boxes (DnaA does not know which strand
k-mer m-times in an n-mer nucleotide
TACTAGTTC it binds to). sequence?

It is VERY SURPRISING to find a 9-mer appearing 6 or more

times (with reverse complements) within ≈ 500 nucleotides.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Looking for other Hidden Messages? Hidden Messages in T. petrophila?

aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactgaaactaaa
atggtaggtttggtggtaggttttgtgtacattttgtagtatctgatttttaattacataccgtata
STOP: Now that we know the “hidden message” in Vibrio ttgtattaaattgacgaacaattgcatggaattgaatatatgcaaaacaaacctaccaccaaactct
gtattgaccattttaggacaacttcagggtggtaggtttctgaagctctcatcaatagactatttta
cholerae, how would we look for a hidden message starting gtctttacaaacaatattaccgttcagattcaagattctacaacgctgttttaatgggcgttgcaga
replication in other bacteria? aaacttaccacctaaaatccagtatccaagccgatttcagagaaacctaccacttacctaccactta
cctaccacccgggtggtaagttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttc
aatactcgaaacctaccacctgcgtcccctattatttactactactaataatagcagtataattgat
ctgaaaagaggtggtaaaaaa

Not one occurrence of ATGATCAAG or CTTGATCAT!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Hidden Messages in T. petrophila? Hidden Messages in T. petrophila?
aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactgaaactaaa aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactgaaactaaa
atggtaggtttggtggtaggttttgtgtacattttgtagtatctgatttttaattacataccgtata atggtaggtttggtggtaggttttgtgtacattttgtagtatctgatttttaattacataccgtata
ttgtattaaattgacgaacaattgcatggaattgaatatatgcaaaacaaacctaccaccaaactct ttgtattaaattgacgaacaattgcatggaattgaatatatgcaaaacaaacctaccaccaaactct
gtattgaccattttaggacaacttcagggtggtaggtttctgaagctctcatcaatagactatttta gtattgaccattttaggacaacttcagggtggtaggtttctgaagctctcatcaatagactatttta
gtctttacaaacaatattaccgttcagattcaagattctacaacgctgttttaatgggcgttgcaga gtctttacaaacaatattaccgttcagattcaagattctacaacgctgttttaatgggcgttgcaga
aaacttaccacctaaaatccagtatccaagccgatttcagagaaacctaccacttacctaccactta aaacttaccacctaaaatccagtatccaagccgatttcagagaaacctaccacttacctaccactta
cctaccacccgggtggtaagttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttc cctaccacccgggtggtaagttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttc
aatactcgaaacctaccacctgcgtcccctattatttactactactaataatagcagtataattgat aatactcgaaacctaccacctgcgtcccctattatttactactactaataatagcagtataattgat
ctgaaaagaggtggtaaaaaa ctgaaaagaggtggtaaaaaa

Not one occurrence of ATGATCAAG or CTTGATCAT! Different genomes 🡪 different hidden messages
Applying Frequent Words Problem to this ori: Applying Frequent Words Problem to this ori:
AACCTACCA, ACCTACCAC, GGTAGGTTT AACCTACCA, ACCTACCAC, GGTAGGTTT
TGGTAGGTT, AAACCTACC, CCTACCACC TGGTAGGTT, AAACCTACC, CCTACCACC

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Hidden Messages in Thermotoga petrophila Outline

aactctatacctcctttttgtcgaatttgtgtgatttatagagaaaatcttattaactgaaactaaa
atggtaggtttGGTGGTAGGttttgtgtacattttgtagtatctgatttttaattacataccgtata • An Intro to DNA Replication
ttgtattaaattgacgaacaattgcatggaattgaatatatgcaaaacaaaCCTACCACCaaactct
gtattgaccattttaggacaacttcagGGTGGTAGGtttctgaagctctcatcaatagactatttta • Hidden Messages in the Replication Origin
gtctttacaaacaatattaccgttcagattcaagattctacaacgctgttttaatgggcgttgcaga
aaacttaccacctaaaatccagtatccaagccgatttcagagaaacctaccacttacctaccactta • Hunting for Frequent Words
CCTACCACCcgggtggtaagttgcagacattattaaaaacctcatcagaagcttgttcaaaaatttc
aatactcgaaaCCTACCACCtgcgtcccctattatttactactactaataatagcagtataattgat
ctgaaaagaggtggtaaaaaa
• A Faster Frequent Words Approach
• Some Hidden Messages are More Surprising than
CCTACCACC
Others
||||||||| are candidate hidden messages.
• An Explosion of Hidden Messages
GGATGGTGG
• Replication Asymmetry Leads Us to the Replication
Origin

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Returning to “Problem 1” Bacteria with Unknown ori

We have found hidden messages if ori is given. But we STOP: Now that we know that “hidden messages” may
still don’t know how to find ori in a (long) genome. differ, how could we look for ori in a newly sequenced
bacterial genome?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Finding ori Computationally Finding ori Computationally

OLD strategy: given a previously known ori (500 nucleotide OLD strategy: given a previously known ori (500 nucleotide
window), find frequent words (clumps) in ori as candidate DnaA window), find frequent words (clumps) in ori as candidate DnaA
boxes. boxes.
replication origin → frequent words replication origin → frequent words

NEW strategy: find frequent words in ALL windows within a (3

million nucleotide) genome. Windows with clumps of frequent
words are candidate replication origins.
frequent words → replication origin
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Finding ori Computationally Defining and Hunting for “Clumps”
k-mer forms
A Intuitive: A k-mer (L, t )-clump
an forms Genome
insideGenome
a clump inside if there
if there is a is
Exercise: Define a computational problem modeling our short interval
a short (lengthofL )Genome
intervalinof
which it appears
Genome many times.
in which it
new strategy. appears many (at least t ) times.

NEW strategy: find frequent words in ALL windows within a (3

million nucleotide) genome. Windows with clumps of frequent
words are candidate replication origins.
frequent words → replication origin
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Defining and Hunting for “Clumps” Defining and Hunting for “Clumps”
A k-mer forms an (L, t )-clump inside Genome if there is FindClumps(text, k, L, t,H)
patterns 🡪 an array of strings of length 0
a short (length L ) interval of Genome in which it n 🡪 Len(text)
appears many (at least t ) times. for every integer i between 0 and n – L
window 🡪 text[i, i + L]
freqMap 🡪 FrequencyMap(window, k)
Clump Finding Problem for every string pattern in freqMap
if freqMap[pattern] >= t
• Input: A string Genome and integers k (length of a patterns 🡪 Append(patterns, pattern)
patterns 🡪 RemoveDuplicates(patterns)
pattern), L (window length), and t (number of return patterns
patterns in a clump).
• Output: All k-mers forming (L, t )-clumps in Genome. Note: A complicated function can be made easier by
using subroutines as building blocks.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Defining and Hunting for “Clumps” What’s the Issue?
FindClumps(text, k, L, t)
patterns 🡪 an array of strings of length 0
n 🡪 Len(text) Genomes have many repeats , some more useful than
for every integer i between 0 and n – L
window 🡪 text[i, i + L] others. Alu in humans is ~300 bp long and occurs (with
freqMap 🡪 FrequencyMap(window, k) some changes) 1 million times.
for every string pattern in freqMap
if freqMap[pattern] >= t
patterns 🡪 Append(patterns, pattern)
patterns 🡪 RemoveDuplicates(patterns)
return patterns

STOP : Why is looking for clumps in bacterial

genomes as a source of hidden messages destined to
fail?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

What’s the Issue? We Are Back Where We Started...

Genomes have many repeats , some more useful than Let’s hack out this DNA
others. Alu in humans is ~300 bp long and occurs (with fragment. Can the
some changes) 1 million times. genome replicate without
it?

In E. coli, 1900+ different 9-mers form (500,3)-clumps.

It is unclear which ones point to ori... I need more information
before I can hack this
problem.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

 Outline A Surprising Pattern in Nucleotide Counts

• An Intro to DNA Replication

• Hidden Messages in the Replication Origin Let’s run a very simple
computational analysis:
• Hunting for Frequent Words take frequency of each
• A Faster Frequent Words Approach nucleotide in 100,000
• Some Hidden Messages are More Surprising than nucleotide windows of E.
coli (verified ori).
Others
• An Explosion of Hidden Messages Why would there be more
• Replication Asymmetry Leads Us to the Replication C on half the genome?
Origin ori ter

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

A Surprising Pattern in Nucleotide Counts Taking Difference in G – C

Let’s run a very simple The pattern is even more

computational analysis: stark if we take the
take frequency of each difference between the
nucleotide in 100,000 frequency of G and the
nucleotide windows of E. frequency of C ...
coli (verified ori).

And why would the story

be opposite when we
count G’s?
ori ter ori ter

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Taking Difference in G – C Taking Difference in G – C

And the pattern is still And the pattern is still

there even if we didn’t there even if we didn’t
know where ori was and know where ori was and
start counting at some start counting at some
arbitrary spot. arbitrary spot.

Let’s learn more about

replication in the hope
of finding an answer...

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

DNA Strands Have Directions Four DNA Polymerases Can Do the Job
ori

5’ ori 3’
5’ 3’

3’ ori 5’ 3’ 5’

ori

The two strands run in opposite directions

(from 5’ to 3’).
Blue Strand: Clockwise ,
Green Strand: Counter-Clockwise

terC
terC

terC terC
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 If you Were a UNIDIRECTIONAL DNA
Continue as Replication Fork Enlarges
Polymerase, how Would you Replicate a Genome?

5’ 3’
5’ 3’
3’ 5’
3’ 5’

Simple, but wrong: DNA polymerases are

unidirectional : they can only traverse a Leading Lagging Leading Lagging
half-strand half-strand half-strand half-strand
parent strand in the 3’ 🡪 5’ direction.

No problem replicating leading

Big lagging half-strands
half-strands (thick lines).
(thin lines) .
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

If you Were a UNIDIRECTIONAL DNA

Polymerase, how Would you Replicate a Genome? Wait until the Fork Opens and ...

5’ 3’ 5’ 3’

3’ 5’ 3’ 5’

Leading Lagging Leading Lagging

half-strand half-strand half-strand half-strand

Note: Leading/lagging
No problem replicatinghalf-strands
reverse half-strands are complementary
(thick lines).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
Wait until the Fork Opens and Replicate Iterate this Process

5’ 3’

3’ 5’

Okazaki
fragments

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Iterate this Process Okazaki Fragments Must Be Ligated

Okazaki
fragments

Okazaki
fragments
The genome has been
replicated!
Many Okazaki
fragments are
replicated.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Different Lifestyles of Half-strands Different Lifestyles of Half-strands
waiting waiting
The leading half-strand lives The leading half-strand lives
a double-stranded life most a double-stranded life most
of the time. of the time.
waiting waiting
The lagging half-strand The lagging half-strand
spends a large portion of its spends a large portion of its
life single-stranded , waiting life single-stranded , waiting
to be replicated. to be replicated.

But why would a

computer scientist care?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Asymmetry of Replication Affects Asymmetry of Replication Affects

Nucleotide Frequencies Nucleotide Frequencies
waiting waiting

Single-stranded DNA has a waiting Single-stranded DNA has a waiting

much higher mutation rate much higher mutation rate
than double-stranded than double-stranded
DNA. DNA.

Thus, if one nucleotide has a greater mutation rate, then

we should observe its shortage on the lagging
half-strand, since it is more often single-stranded!
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Deamination is the Answer Deamination is the Answer

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

lagging
...C...
...G...
leading

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Deamination is the Answer Deamination is the Answer

Cytosine (C) rapidly mutates into thymine (T) through Cytosine (C) rapidly mutates into thymine (T) through
deamination ; deamination rates rise 100-fold when DNA deamination ; deamination rates rise 100-fold when DNA
is single-stranded! is single-stranded!
lagging lagging lagging
...C... ...C... ...T...
lagging lagging
...C... ...C...
...G... ...G...
leading
...C... leading
...C... ...C...
...G... ...G... ...G...
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Take a Walk Along the Genome
Deamination is the Answer #G - #C is DECREASING #G - #C is INCREASING
5’ 3’

3’ ori 5’
Cytosine (C) rapidly mutates into thymine (T) through
deamination ; deamination rates rise 100-fold when DNA
C low
is single-stranded! C high
G low
You walk along the genome and see that #G - #C has G high
been decreasing and then suddenly starts increasing.
lagging lagging lagging
...C... ...T... ...T... Where are you in the genome?
lagging
...C... ...A...
leading terC

...G...
leading
...C... ...C... ...C...
C high/G low → #G - #C is DECREASING as C low/G high → #G - #C is INCREASING
...G... ...G... ...G... we walk along the LEADING half-strand as we walk along the LAGGING half-strand
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Take a Walk Along the Genome

#G - #C is DECREASING #G - #C is INCREASING
Skew Array/Diagram
5’ 3’

3’ ori 5’ Skew array : Skew[k] = #G - #C for the first k

nucleotides of Genome.
C high C low
G low Exercise: What is the computational G high Skew diagram : Plot Skew[k] against k.
problem we are trying to solve here?

terC

C high/G low → #G - #C is DECREASING as C low/G high → #G - #C is INCREASING

we walk along the LEADING half-strand as we walk along the LAGGING half-strand CATGGGCATCGGCCATACGCC
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Skew Array/Diagram Skew Diagram of E. Coli
#G - #C is DECREASING #G - #C is INCREASING
5’ 3’

3’ ori 5’

C high C low
G low
STOP: What will the skew array of a G high
ori
bacterial genome look like?

terC

You walk along the genome and see that #G - #C have been decreasing and then
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
suddenly starts Bioinformatics
increasing . Where are you in the genome?
Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

We Have Now “Solved” Question 1! We Have Now “Solved” Question 1!

Given a bacterial genome (~3 Mbp), where is ori? Given a bacterial genome (~3 Mbp), where is ori?

Minimum Skew Problem

• Input: A DNA string genome.
• Output: The min value of Skew[k] for genome.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
We Found the Replication Origin in E. Coli BUT… We Found the Replication Origin in E. Coli BUT…

aatgatgatgacgtcaaaaggatccggataaaacatggtgattgcctcgcataacgcggta aatgatgatgacgtcaaaaggatccggataaaacatggtgattgcctcgcataacgcggta
tgaaaatggattgaagcccgggccgtggattctactcaactttgtcggcttgagaaagacc tgaaaatggattgaagcccgggccgtggattctactcaactttgtcggcttgagaaagacc
tgggatcctgggtattaaaaagaagatctatttatttagagatctgttctattgtgatctc tgggatcctgggtattaaaaagaagatctatttatttagagatctgttctattgtgatctc
ttattaggatcgcactgccctgtggataacaaggatccggcttttaagatcaacaacctgg ttattaggatcgcactgccctgtggataacaaggatccggcttttaagatcaacaacctgg
aaaggatcattaactgtgaatgatcggtgatcctggaccgtataagctgggatcagaatga aaaggatcattaactgtgaatgatcggtgatcctggaccgtataagctgggatcagaatga
ggggttatacacaactcaaaaactgaacaacagttgttctttggataactaccggttgatc ggggttatacacaactcaaaaactgaacaacagttgttctttggataactaccggttgatc
caagcttcctgacagagttatccacagtagatcgcacgatctgtatacttatttgagtaaa caagcttcctgacagagttatccacagtagatcgcacgatctgtatacttatttgagtaaa
ttaacccacgatcccagccattcttctgccggatcttccggaatgtcgtgatcaagaatgt ttaacccacgatcccagccattcttctgccggatcttccggaatgtcgtgatcaagaatgt
tgatcttcagtg tgatcttcagtg

But there are no frequent 9-mers (that appear three But there are no frequent 9-mers (that appear three
or more times) in this region of E. coli! or more times) in this region of E. coli!

STOP: Any ideas? Should we give up?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Accounting for Point Mutations Complications

• Some bacteria have fewer DnaA boxes.
aatgatgatgacgtcaaaaggatccggataaaacatggtgattgcctcgcataacgcggta • Terminus of replication is often not located
tgaaaatggattgaagcccgggccgtggattctactcaactttgtcggcttgagaaagacc
tgggatcctgggtattaaaaagaagatctatttatttagagatctgttctattgtgatctc directly opposite to ori.
ttattaggatcgcactgcccTGTGGATAAcaaggatccggcttttaagatcaacaacctgg
aaaggatcattaactgtgaatgatcggtgatcctggaccgtataagctgggatcagaatga
ggggTTATACACAactcaaaaactgaacaacagttgttcTTTGGATAACtaccggttgatc
• The skew diagram is often more complex than in
caagcttcctgacagagTTATCCACAgtagatcgcacgatctgtatacttatttgagtaaa
ttaacccacgatcccagccattcttctgccggatcttccggaatgtcgtgatcaagaatgt
the case of E. coli.
tgatcttcagtg

Frequent 9-mers (with 1 Mismatch and Reverse

Complements) in putative ori of E. coli Skew diagram
of T. petrophila

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner. Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.
 Moral? Homework problem

Take a random sequence with equal number of A,

This division is not an appropriate view of how T,G,C and then make then undergo replications
biology (or science in general) can and should
operate in the 21st Century.
and then assume that 50% of all C in the lagging
strand are getting mutated.
Ori

Ex. ATGCATGCATGCATGCATGCATGCATGC

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau and Pevzner.

Lab: Psuedocode for an OriFinder

[Link]