How Do Biologists Assemble Genomic

Puzzles from Millions of Pieces?

Graph Algorithms

Phillip Compeau

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Eternity II: The Highest-
Stakes Puzzle in History

Bioinformatics Algorithms: An Active Learning Approach. © 2020Courtesy:

Compeau Matej Bat’ha
 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Newspaper Problem

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Newspaper Problem

The Newspaper Problem is an overlap

puzzle.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 The Newspaper Problem

But what does this have to do with

biology?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 DNA is a Double Helix of
Nucleotide Strands

DNA’s Double Helix (1953) DNA’s Molecular Structure

Courtesy: Madprime, Wikimedia Commons

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Order of Nucleotides
Determines Genetics

Nucleotide: Half of
one “rung” of DNA.

Four choices for the nucleic

acid of a nucleotide:
1. Adenine (A)
2. Cytosine (C)
3. Guanine (G)—bonds
to C
DNA’s Molecular Structure
4. Thymine (T)—bonds Courtesy: Madprime, Wikimedia Commons

to A
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 The Order of Nucleotides
Determines Genetics

Nucleotide: Half of
one “rung” of DNA.

Key point: if we know

one strand of DNA, we
get the other strand for
free because of this
“complementarity”.
DNA’s Molecular Structure

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Genome “Sequencing” Means
“Reading” the Genome

Genome: The nucleotide sequence read

down one side of an organism’s
chromosomal DNA. A human genome has
about 3 billion letters.
…CCGTAGTCGCATGGAACAGTATACGAGACAGTACAGATACGATACGATACGATCATTAACCGAGAGTACCAGATTCCAGATCATACG
TTACGCTTAGCTACGGACGTACGATACCCAGATTACGATCCATATAGATATAACCGGTGTGTCTTGCTAATACGTAACGGGGTGCCT
TCGATAGGTCAGAATACCAGATCTCTCGATCTTCTTACAGATACTACGATCCCCAGATACTACCCCTACTGACCCATCGTACGGGTA
CTACTACGGATATGATACCGATGTAGAGGGATCCATATATCCCGAGACGTCTCGCGCATAAGATCATCGTCTAGATACACGTACGTA
CTAGACTAGCGTATGCCTCTTATGATCGTCCCGATCGAGTCGCGTGCTCAGAAAAGCTACGATACGATACCCGATACTAGACCATAG…

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Genome “Sequencing” Means
“Reading” the Genome

Genome: The nucleotide sequence read

down one side of an organism’s
chromosomal DNA. A human genome has
about 3 billion letters.
…CCGTAGTCGCATGGAACAGTATACGAGACAGTACAGATACGATACGATACGATCATTAACCGAGAGTACCAGATTCCAGATCATACG
TTACGCTTAGCTACGGACGTACGATACCCAGATTACGATCCATATAGATATAACCGGTGTGTCTTGCTAATACGTAACGGGGTGCCT
TCGATAGGTCAGAATACCAGATCTCTCGATCTTCTTACAGATACTACGATCCCCAGATACTACCCCTACTGACCCATCGTACGGGTA
CTACTACGGATATGATACCGATGTAGAGGGATCCATATATCCCGAGACGTCTCGCGCATAAGATCATCGTCTAGATACACGTACGTA
CTAGACTAGCGTATGCCTCTTATGATCGTCCCGATCGAGTCGCGTGCTCAGAAAAGCTACGATACGATACCCGATACTAGACCATAG…

Polychaos dubium (an amoeba) has one of

the longest known genomes: 670 billion
nucleotides.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Genome “Sequencing” Means
“Reading” the Genome

Genome: The nucleotide sequence read

down one side of an organism’s
chromosomal DNA. A human genome has
about 3 billion letters.
…CCGTAGTCGCATGGAACAGTATACGAGACAGTACAGATACGATACGATACGATCATTAACCGAGAGTACCAGATTCCAGATCATACG
TTACGCTTAGCTACGGACGTACGATACCCAGATTACGATCCATATAGATATAACCGGTGTGTCTTGCTAATACGTAACGGGGTGCCT
TCGATAGGTCAGAATACCAGATCTCTCGATCTTCTTACAGATACTACGATCCCCAGATACTACCCCTACTGACCCATCGTACGGGTA
CTACTACGGATATGATACCGATGTAGAGGGATCCATATATCCCGAGACGTCTCGCGCATAAGATCATCGTCTAGATACACGTACGTA
CTAGACTAGCGTATGCCTCTTATGATCGTCCCGATCGAGTCGCGTGCTCAGAAAAGCTACGATACGATACCCGATACTAGACCATAG…

Key Point: DNA is submicroscopic! How do

we read something that we cannot see?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Sequence a Species’s Genome
to Unlock its Genetic Identity

Darwin’s notebook c. 1837 Hug et al., 2016

Nature Biotechnology, Discovery Magazine

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Sequence an Individual’s Genome
to Find What Makes them Unique
Nicholas
Volker: First
human whose
life was saved
because of
genome
sequencing
(2011).

One in a Billion
Foundation

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 History of Genome Sequencing
Late 1970s: Walter Gilbert and
Frederick Sanger develop
independent sequencing methods.
GAGTTTTATCGCTTCCATGACGCAGAAGTTAACACTTTCGGATATTTCTGATGAGTCGAAAAATTATCTTGATAAAGCAGGAATTACTACTGCTTGTTTACGAATTAAATCGAAGTGGACTGCTGGCGGAAAATGAGAAAATTCGACCTATCCTTGCGCAGCT
CGAGAAGCTCTTACTTTGCGACCTTTCGCCATCAACTAACGATTCTGTCAAAAACTGACGCGTTGGATGAGGAGAAGTGGCTTAATATGCTTGGCACGTTCGTCAAGGACTGGTTTAGATATGAGTCACATTTTGTTCATGGTAGAGATTCTCTTGTTGACAT

Walter Gilbert
TTTAAAAGAGCGTGGATTACTATCTGAGTCCGATGCTGTTCAACCACTAATAGGTAAGAAATCATGAGTCAAGTTACTGAACAATCCGTACGTTCCAGACCGCTTTGGCCTCTATTAAGCTCATTCAGGCTTCTGCCGTTTTGGATTTAACCGAAGATGATTT
CGATTTTCTGACGAGTAACAAAGTTTGGATTGCTACTGACCGCTCTCGTGCTCGTCGCTGCGTTGAGGCTTGCGTTTATGGTACGCTGGACTTTGTGGGATACCCTCGCTTTCCTGCTCCTGTTGAGTTTATTGCTGCCGTCATTGCTTATTATGTTCATCCC
GTCAACATTCAAACGGCCTGTCTCATCATGGAAGGCGCTGAATTTACGGAAAACATTATTAATGGCGTCGAGCGTCCGGTTAAAGCCGCTGAATTGTTCGCGTTTACCTTGCGTGTACGCGCAGGAAACACTGACGTTCTTACTGACGCAGAAGAAAACGTGC
GTCAAAAATTACGTGCGGAAGGAGTGATGTAATGTCTAAAGGTAAAAAACGTTCTGGCGCTCGCCCTGGTCGTCCGCAGCCGTTGCGAGGTACTAAAGGCAAGCGTAAAGGCGCTCGTCTTTGGTATGTAGGTGGTCAACAATTTTAATTGCAGGGGCTTCGG
CCCCTTACTTGAGGATAAATTATGTCTAATATTCAAACTGGCGCCGAGCGTATGCCGCATGACCTTTCCCATCTTGGCTTCCTTGCTGGTCAGATTGGTCGTCTTATTACCATTTCAACTACTCCGGTTATCGCTGGCGACTCCTTCGAGATGGACGCCGTTG
GCGCTCTCCGTCTTTCTCCATTGCGTCGTGGCCTTGCTATTGACTCTACTGTAGACATTTTTACTTTTTATGTCCCTCATCGTCACGTTTATGGTGAACAGTGGATTAAGTTCATGAAGGATGGTGTTAATGCCACTCCTCTCCCGACTGTTAACACTACTGG
TTATATTGACCATGCCGCTTTTCTTGGCACGATTAACCCTGATACCAATAAAATCCCTAAGCATTTGTTTCAGGGTTATTTGAATATCTATAACAACTATTTTAAAGCGCCGTGGATGCCTGACCGTACCGAGGCTAACCCTAATGAGCTTAATCAAGATGAT
GCTCGTTATGGTTTCCGTTGCTGCCATCTCAAAAACATTTGGACTGCTCCGCTTCCTCCTGAGACTGAGCTTTCTCGCCAAATGACGACTTCTACCACATCTATTGACATTATGGGTCTGCAAGCTGCTTATGCTAATTTGCATACTGACCAAGAACGTGATT
ACTTCATGCAGCGTTACCATGATGTTATTTCTTCATTTGGAGGTAAAACCTCTTATGACGCTGACAACCGTCCTTTACTTGTCATGCGCTCTAATCTCTGGGCATCTGGCTATGATGTTGATGGAACTGACCAAACGTCGTTAGGCCAGTTTTCTGGTCGTGT
TCAACAGACCTATAAACATTCTGTGCCGCGTTTCTTTGTTCCTGAGCATGGCACTATGTTTACTCTTGCGCTTGTTCGTTTTCCGCCTACTGCGACTAAAGAGATTCAGTACCTTAACGCTAAAGGTGCTTTGACTTATACCGATATTGCTGGCGACCCTGTT
TTGTATGGCAACTTGCCGCCGCGTGAAATTTCTATGAAGGATGTTTTCCGTTCTGGTGATTCGTCTAAGAAGTTTAAGATTGCTGAGGGTCAGTGGTATCGTTATGCGCCTTCGTATGTTTCTCCTGCTTATCACCTTCTTGAAGGCTTCCCATTCATTCAGG
AACCGCCTTCTGGTGATTTGCAAGAACGCGTACTTATTCGCCACCATGATTATGACCAGTGTTTCCAGTCCGTTCAGTTGTTGCAGTGGAATAGTCAGGTTAAATTTAATGTGACCGTTTATCGCAATCTGCCGACCACTCGCGATTCAATCATGACTTCGTG
ATAAAAGATTGAGTGTGAGGTTATAACGCCGAAGCGGTAAAAATTTTAATTTTTGCCGCTGAGGGGTTGACCAAGCGAAGCGCGGTAGGTTTTCTGCTTAGGAGTTTAATCATGTTTCAGACTTTTATTTCTCGCCATAATTCAAACTTTTTTTCTGATAAGC
TGGTTCTCACTTCTGTTACTCCAGCTTCTTCGGCACCTGTTTTACAGACACCTAAAGCTACATCGTCAACGTTATATTTTGATAGTTTGACGGTTAATGCTGGTAATGGTGGTTTTCTTCATTGCATTCAGATGGATACATCTGTCAACGCCGCTAATCAGGT
TGTTTCTGTTGGTGCTGATATTGCTTTTGATGCCGACCCTAAATTTTTTGCCTGTTTGGTTCGCTTTGAGTCTTCTTCGGTTCCGACTACCCTCCCGACTGCCTATGATGTTTATCCTTTGAATGGTCGCCATGATGGTGGTTATTATACCGTCAAGGACTGT
GTGACTATTGACGTCCTTCCCCGTACGCCGGGCAATAACGTTTATGTTGGTTTCATGGTTTGGTCTAACTTTACCGCTACTAAATGCCGCGGATTGGTTTCGCTGAATCAGGTTATTAAAGAGATTATTTGTCTCCAGCCACTTAAGTGAGGTGATTTATGTT
TGGTGCTATTGCTGGCGGTATTGCTTCTGCTCTTGCTGGTGGCGCCATGTCTAAATTGTTTGGAGGCGGTCAAAAAGCCGCCTCCGGTGGCATTCAAGGTGATGTGCTTGCTACCGATAACAATACTGTAGGCATGGGTGATGCTGGTATTAAATCTGCCATT
CAAGGCTCTAATGTTCCTAACCCTGATGAGGCCGCCCCTAGTTTTGTTTCTGGTGCTATGGCTAAAGCTGGTAAAGGACTTCTTGAAGGTACGTTGCAGGCTGGCACTTCTGCCGTTTCTGATAAGTTGCTTGATTTGGTTGGACTTGGTGGCAAGTCTGCCG
CTGATAAAGGAAAGGATACTCGTGATTATCTTGCTGCTGCATTTCCTGAGCTTAATGCTTGGGAGCGTGCTGGTGCTGATGCTTCCTCTGCTGGTATGGTTGACGCCGGATTTGAGAATCAAAAAGAGCTTACTAAAATGCAACTGGACAATCAGAAAGAGAT
TGCCGAGATGCAAAATGAGACTCAAAAAGAGATTGCTGGCATTCAGTCGGCGACTTCACGCCAGAATACGAAAGACCAGGTATATGCACAAAATGAGATGCTTGCTTATCAACAGAAGGAGTCTACTGCTCGCGTTGCGTCTATTATGGAAAACACCAATCTT
TCCAAGCAACAGCAGGTTTCCGAGATTATGCGCCAAATGCTTACTCAAGCTCAAACGGCTGGTCAGTATTTTACCAATGACCAAATCAAAGAAATGACTCGCAAGGTTAGTGCTGAGGTTGACTTAGTTCATCAGCAAACGCAGAATCAGCGGTATGGCTCTT
CTCATATTGGCGCTACTGCAAAGGATATTTCTAATGTCGTCACTGATGCTGCTTCTGGTGTGGTTGATATTTTTCATGGTATTGATAAAGCTGTTGCCGATACTTGGAACAATTTCTGGAAAGACGGTAAAGCTGATGGTATTGGCTCTAATTTGTCTAGGAA
ATAACCGTCAGGATTGACACCCTCCCAATTGTATGTTTTCATGCCTCCAAATCTTGGAGGCTTTTTTATGGTTCGTTCTTATTACCCTTCTGAATGTCACGCTGATTATTTTGACTTTGAGCGTATCGAGGCTCTTAAACCTGCTATTGAGGCTTGTGGCATT
TCTACTCTTTCTCAATCCCCAATGCTTGGCTTCCATAAGCAGATGGATAACCGCATCAAGCTCTTGGAAGAGATTCTGTCTTTTCGTATGCAGGGCGTTGAGTTCGATAATGGTGATATGTATGTTGACGGCCATAAGGCTGCTTCTGACGTTCGTGATGAGT
TTGTATCTGTTACTGAGAAGTTAATGGATGAATTGGCACAATGCTACAATGTGCTCCCCCAACTTGATATTAATAACACTATAGACCACCGCCCCGAAGGGGACGAAAAATGGTTTTTAGAGAACGAGAAGACGGTTACGCAGTTTTGCCGCAAGCTGGCTGC
TGAACGCCCTCTTAAGGATATTCGCGATGAGTATAATTACCCCAAAAAGAAAGGTATTAAGGATGAGTGTTCAAGATTGCTGGAGGCCTCCACTATGAAATCGCGTAGAGGCTTTGCTATTCAGCGTTTGATGAATGCAATGCGACAGGCTCATGCTGATGGT
TGGTTTATCGTTTTTGACACTCTCACGTTGGCTGACGACCGATTAGAGGCGTTTTATGATAATCCCAATGCTTTGCGTGACTATTTTCGTGATATTGGTCGTATGGTTCTTGCTGCCGAGGGTCGCAAGGCTAATGATTCACACGCCGACTGCTATCAGTATT
TTTGTGTGCCTGAGTATGGTACAGCTAATGGCCGTCTTCATTTCCATGCGGTGCACTTTATGCGGACACTTCCTACAGGTAGCGTTGACCCTAATTTTGGTCGTCGGGTACGCAATCGCCGCCAGTTAAATAGCTTGCAAAATACGTGGCCTTATGGTTACAG
TATGCCCATCGCAGTTCGCTACACGCAGGACGCTTTTTCACGTTCTGGTTGGTTGTGGCCTGTTGATGCTAAAGGTGAGCCGCTTAAAGCTACCAGTTATATGGCTGTTGGTTTCTATGTGGCTAAATACGTTAACAAAAAGTCAGATATGGACCTTGCTGCT
AAAGGTCTAGGAGCTAAAGAATGGAACAACTCACTAAAAACCAAGCTGTCGCTACTTCCCAAGAAGCTGTTCAGAATCAGAATGAGCCGCAACTTCGGGATGAAAATGCTCACAATGACAAATCTGTCCACGGAGTGCTTAATCCAACTTACCAAGCTGGGTT
ACGACGCGACGCCGTTCAACCAGATATTGAAGCAGAACGCAAAAAGAGAGATGAGATTGAGGCTGGGAAAAGTTACTGTAGCCGACGTTTTGGCGGCGCAACCTGTGACGACAAATCTGCTCAAATTTATGCGCGCTTCGATAAAAATGATTGGCGTATCCAA
CCTGCA

Bacterial phage PhiX174 genome (5,386 nucleotides) Frederick Sanger

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

History of Genome Sequencing
Late 1970s: Walter Gilbert and
Frederick Sanger develop
independent sequencing methods.

Walter Gilbert
1980: They share the Nobel Prize
in Chemistry.

Frederick Sanger

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

History of Genome Sequencing
Late 1970s: Walter Gilbert and
Frederick Sanger develop
independent sequencing methods.

Walter Gilbert
1980: They share the Nobel Prize
in Chemistry.

However, their approaches cost

about $1 per nucleotide.
Frederick Sanger

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Race to Sequence the Human
Genome
1990: Francis Collins and Human
Genome Project given $3 billion to
sequence human genome by
2005.
Francis Collins

Craig Venter

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Race to Sequence the Human
Genome
1990: Francis Collins and Human
Genome Project given $3 billion to
sequence human genome by
2005.
Francis Collins

1997: Craig Venter founds Celera

Genomics with same goal.

Craig Venter

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Race to Sequence the Human
Genome
2000: First
draft of human
genome
published.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From One Mammal Genome to
Many
Early 2000s: Many more mammalian
genomes are sequenced using Sanger’s
approach.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From One Mammal Genome to
Many
Problem: This approach was just too
expensive to scale to thousands of species.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Sequencing Cost Has Fallen Faster
than Moore’s Law

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Big Projects in “Next Generation”
Species Sequencing

Genome 10K:
Sequencing 10,000
vertebrate genomes.
i5K: Sequencing 5,000
arthropod genomes.

B10K: Sequencing
10,000 bird genomes.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

and Pevzner.
 We Now Have Over 2 Million
Human Genomes

BGI: World’s largest

sequencing center.

100,000 Genomes:
Sequenced 100,000 UK
resident genomes (2012-
2018).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
and Pevzner.
 Overview of Genome
Sequencing

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Overview of Genome
Sequencing

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Overview of Genome
Sequencing

(Lab
)

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Overview of Genome
Sequencing

(Lab
)

(Computationa
l)

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Overview of Genome
Sequencing

(Lab
)

(Computationa
l)

What does genome sequencing remind

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Genome Assembly = Overlap
Puzzle

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Complications of Genome
Assembly
1. DNA is double-stranded (and may
consist of multiple chromosomes).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Complications of Genome
Assembly
1. DNA is double-stranded (and may
consist of multiple chromosomes).

2. Reads have imperfect “coverage” of

the underlying genome – there may be
some regions that are not covered by any
reads.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Complications of Genome
Assembly
1. DNA is double-stranded (and may
consist of multiple chromosomes).

2. Reads have imperfect “coverage” of

the underlying genome – there may be
some regions that are not covered by any
reads.

3. Sequencing machines are error-prone.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Simplifying Assumptions for
Genome Assembly
1. DNA is single-stranded and consists of a
single chromosome.

2. Reads have perfect “coverage” of the

underlying genome: every substring of
length k is generated as a read. (k is
between 100 and 100,000)

3. Sequencing machines are error-free.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Simplifying Assumptions for
Genome Assembly
1. DNA is single-stranded and consists of a
single chromosome.

2. Reads have perfect “coverage” of the

underlying genome: every substring of
length k is generated as a read. (k is
between 100 and 100,000)

3. Sequencing machines are error-free.

STOP: How can we formulate a
computational problem for genome
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Formulating a Computational
Problem for Genome Assembly
Genome Assembly Problem. Reconstruct
a genome from reads.
Input: A collection of strings Reads.
Output: A string Genome reconstructed
from Reads.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Formulating a Computational
Problem for Genome Assembly
Genome Assembly Problem. Reconstruct
a genome from reads.
Input: A collection of strings Reads.
Output: A string Genome reconstructed
from Reads.

STOP: Is this a computational problem?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Formulating a Computational
Problem for Genome Assembly
Genome Assembly Problem. Reconstruct
a genome from reads.
Input: A collection of strings Reads.
Output: A string Genome reconstructed
from Reads.

STOP: Is this a computational problem?

Answer: No! We have no sense of what it

means to “reconstruct” a genome. How can
we fixBioinformatics
it? Algorithms: An Active Learning Approach. © 2020 Compeau
 Formulating a Computational
Problem for Genome Assembly
The k-mer composition of a string Text,
denoted Compositionk(Text), is the collection
of all k-mer substrings of Text (including
repeats).
Composition3(TATGGGGTGC) =
{ATG, GGG, GGG, GGT, GTG, TAT, TGC, TGG}

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Formulating a Computational
Problem for Genome Assembly
The k-mer composition of a string Text,
denoted Compositionk(Text), is the collection
of all k-mer substrings of Text (including
repeats).
Composition3(TATGGGGTGC) =
{ATG, GGG, GGG, GGT, GTG, TAT, TGC, TGG}

Note: The k-mers here are presented in

lexicographic order (i.e., how they would
appear in a dictionary) because we don’t
control order of reads produced by the
sequencing machine.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Formulating a Computational
Problem for Genome Assembly
The k-mer composition of a string Text,
denoted Compositionk(Text), is the collection
of all k-mer substrings of Text (including
repeats).
Composition3(TATGGGGTGC) =
{ATG, GGG, GGG, GGT, GTG, TAT, TGC, TGG}
String Reconstruction Problem.
Reconstruct a string from its k-mer
composition.
Input: A collection Patterns of k-mers.
Output: A string Text whose k-mer
composition is equal to Patterns.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Formulating a Computational
Problem for Genome Assembly
STOP: Now is this a well-defined
computational problem?

String Reconstruction Problem.

Reconstruct a string from its k-mer
composition.
Input: A collection Patterns of k-mers.
Output: A string Text whose k-mer
composition is equal to Patterns.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Formulating a Computational
Problem for Genome Assembly
STOP: Now is this a well-defined
computational problem?

Answer: Not quite ... what if Patterns =

{AAA, ZZZ}?
String Reconstruction Problem.
Reconstruct a string from its k-mer
composition.
Input: A collection Patterns of k-mers.
Output: A string Text whose k-mer
composition is equal to Patterns (if such a
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Toward an Algorithm for Genome
Assembly
Exercise: Reconstruct the string
corresponding to the following 3-mer
composition.

AAT ATG GTT TAA TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Toward an Algorithm for Genome
Assembly
Exercise: Reconstruct the string
corresponding to the following 3-mer
composition.

AAT ATG GTT TAA TGT

TAA
AAT
ATG
TGT
GTT
TAATGTT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Toward an Algorithm for Genome
Assembly
”Greedy” algorithm: for each k-
mer, look for the k-mer of maximum
overlap in each direction.

TAA
AAT
ATG
TGT
GTT
TAATGTT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Toward an Algorithm for Genome
Assembly
”Greedy” algorithm: for each k-
mer, look for the k-mer of maximum
overlap in each direction.

Genome assembly is trivial! We can

pack up and go home.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Toward an Algorithm for Genome
Assembly
AAT
”Greedy” algorithm: for each k- ATG
mer, look for the k-mer of maximum ATG
ATG
overlap in each direction. CAT
CCA
GAT
Genome assembly is trivial! We can GCC
pack up and go home. GGA
GGG
GTT
TAA
Exercise: Apply this algorithm to TGC
the 3-mer composition at right. TGG
TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
ATG
ATG
ATG
CAT
CCA
GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAA TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG
ATG
CAT
CCA
GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAAT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
ATG
CAT
CCA
GAT
GCC
GGA
GGG
GTT
STOP: Which one TAA
should we choose? TGC
TGG
TAATG TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
CAT
CCA
GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAATGC TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA
GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAATGCC TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAATGCCA TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAATGCCAT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
GGA
GGG
GTT
TAA
TGC
TGG
TAATGCCATG TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGG
GTT
TAA
TGC
TGG
TAATGCCATGG TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA GGG
GTT
TAA
TGC
TGG
TAATGCCATGGA TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA GGG
GAT GTT
TAA
TGC
TGG
TAATGCCATGGAT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA GGG
GAT GTT
ATG TAA
TGC
TGG
TAATGCCATGGATG TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA GGG
GAT GTT
ATG TAA
TGT TGC
TGG
TAATGCCATGGATGT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC ATG
GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA ??? GGG
GAT GTT
ATG TAA
TGT TGC
GTT TGG
TAATGCCATGGATGTT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Toward an Algorithm for Genome
Assembly
TAA AAT
AAT ATG
ATG ATG
TGC STOP: Why did our ATG
GCC algorithm fail? CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGA ??? GGG
GAT GTT
ATG TAA
TGT TGC
GTT TGG
TAATGCCATGGATGTT TGT
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Repeats Complicate String
Reconstruction

The greedy algorithm fails because of

repeats.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Repeats Complicate String
Reconstruction

The greedy algorithm fails because of

repeats.
Exercise: How many DNA 300-mers are
there? What do you think the odds are of a
repeat of length 300 in a random DNA string
of length 3 billion?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Repeats Complicate String
Reconstruction

The greedy algorithm fails because of

repeats.
Exercise: How many DNA 300-mers are
there? What do you think the odds are of a
repeat of length 300 in a random DNA string
of length 3 billion?
Repeats are very common in genomes; the
300-nucleotide Alu repeat occurs over a
million times (with minor changes) in every
human genome.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Repeats Make Eternity
II Unsolvable ...

Bioinformatics Algorithms: An Active Learning Approach. © 2020Courtesy:

Compeau Matej Bat’ha
 Even a 16-piece “Triazzle” Can
Take a Human Hours to Solve...
... so what hope do
we have of Courtesy: Dan Gilbert

assembling a
genome?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Interlude: How Are Reads
Sequenced?

[Link]
=fCd6B5HRaZ8

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Solution to Previous Exercise
TAA AAT
STOP: Is this AAT ATG
ATG
the only TGC
ATG
ATG
solution? GCC CAT
CCA CCA
CAT GAT
ATG GCC
TGG GGA
GGG GGG
GGA GTT
GAT TAA
ATG TGC
TGT TGG
GTT TGT
TAATGCCATGGGATGTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can View a Genome as a
“Path” in a Graph

Genome path: assign each read to a node,

connect adjacent reads with edges.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can View a Genome as a
“Path” in a Graph

Genome path: assign each read to a node,

connect adjacent reads with edges.

STOP: Can you still see the genome?

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can View a Genome as a
“Path” in a Graph

Genome path: assign each read to a node,

connect adjacent reads with edges.

STOP: Can you still see the genome?

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

STOP: Could you construct the genome

path if you only knew the 3-mer
composition?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 We Can View a Genome as a
“Path” in a Graph

Genome path: assign each read to a node,

connect adjacent reads with edges.

STOP: Can you still see the genome?

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Answer: Certainly, no ... we need to know

the order of the k-mers.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

• Prefix: First k – 1 letters in a k-mer.

• Suffix: Last k – 1 letters in a k-mer.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 A Graph Can Represent All
Overlapping Strings

Note: we can still see the genome path, but

we wouldn’t if we don’t know the order of k-
mers …

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Overlap Graph: Form a node for each read

in Patterns, then connect x to y if Suffix(x) =
Prefix(y).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Arranging k-mers Lexicographically
Makes Genome Vanish

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Arranging k-mers Lexicographically
Makes Genome Vanish

STOP: If we gave you this graph, what

would you look for to find the genome?

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We are Looking for a Hamiltonian
Path in the Overlap Graph

Hamiltonian path: A path through a graph

that touches each node exactly once.

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Here’s One Solution

STOP: What genome does the highlighted

path reconstruct?

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 And Here’s Another Solution

STOP: How about this highlighted path?

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We are Looking for a Hamiltonian
Path in the Overlap Graph

Note: The graph organizes our reads, but

we don’t have an algorithm for finding a
Hamiltonian path.

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We are Looking for a Hamiltonian
Path in the Overlap Graph

STOP: What does the overlap graph look like

if there are many repeats? What if there are
none?

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside 1: de Bruijn and Good

A binary string is k-
universal if it contains every
binary k-mer once.
Exercise: Find a 3-universal
string. Jack Good

Nicolaas de Bruijn

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside 1: de Bruijn and Good

A binary string is k-
universal if it contains every
binary k-mer once.
Note: a k-universal string
corresponds to a Hamiltonian Jack Good

path in the following overlap

graph.

000 001 010 011 100 101 110 111

Nicolaas de Bruijn

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside 1: de Bruijn and Good

1946: Good and de Bruijn

independently discover a way
to find k-universal strings.
They cannot imagine that their
Jack Good
approach will one day power
genome sequencing.

000 001 010 011 100 101 110 111

Nicolaas de Bruijn

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside 2: Two Ways to Represent
Graphs Computationally
Adjacency Matrix
c
a b c d e
a 0 1 0 0 1
b d b 0 0 1 1 0
c 1 0 0 0 0
d 1 0 0 0 0
a e e 0 1 1 1 0

Adjacency matrix: Ai,j = 1 if there is an

edge connecting node i to node j; Ai,j = 0
otherwise.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside 2: Two Ways to Represent
Graphs Computationally
Adjacency Matrix Adjacency List
c
a b c d e
a 0 1 0 0 1 a b, e
b d b 0 0 1 1 0 b c, d
c 1 0 0 0 0 c a
d 1 0 0 0 0 d a
a e e 0 1 1 1 0 e b, c, d

Adjacency matrix: Ai,j = 1 if there is an

edge connecting node i to node j; Ai,j = 0
otherwise.

Adjacency list: Dictionary; “key” node

i;“value” is list
Bioinformatics of Annodes
Algorithms: that
Active Learning i is
Approach. connected
© 2020 Compeau
 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assigning k-mers to Edges Instead
of Nodes
We start again with a “genome path”
corresponding to TAATGCCATGGGATGTT.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assigning k-mers to Edges Instead
of Nodes
We start again with a “genome path”
corresponding to TAATGCCATGGGATGTT.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

STOP: How should we label the nodes?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assigning k-mers to Edges Instead
of Nodes
Each node represents the (k – 1)-mer
corresponding to the overlap between
adjacent edges.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assigning k-mers to Edges Instead
of Nodes
Each node represents the (k – 1)-mer
corresponding to the overlap between
adjacent edges.

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

Unlike with the overlap graph, we will glue

together nodes that have the same label.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 First: Gluing AT Together

CC CC
CCA GCC CCA GCC

CA GC CA GC
CAT TGC TGC
CAT
AT TG ATG
TG
ATG
TAA AAT TGT GTT TAA AAT TGT GTT
ATG ATG
TA AA AT TG GT TT TA AA AT
AT TG GT TT
ATG
AT ATG
TG GAT TG
GAT TGG TGG
GA GG GA GG

GGA GGG GGA GGG

GG GG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Next: Gluing TG Together

CC CC
CCA GCC CCA GCC

CA GC CA GC
TGC
CAT CAT TGC
ATG
TG ATG
TAA AAT TGT GTT TAA AAT TGT GTT
ATG ATG
TA AA AT TG GT TT TA AA AT TG GT TT

ATG ATG
GAT TG GAT TGG
TGG
GA GG GA GG

GGA GGG GGA GGG

GG GG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Gluing GG Produces a “Loop”

CC CC
CCA GCC CCA GCC

CA GC CA GC

CAT TGC CAT TGC

ATG ATG
TAA AAT TGT GTT TAA AAT TGT GTT
ATG ATG
TA AA AT TG GT TT TA AA AT TG GT TT

ATG ATG
GAT TGG GAT TGG

GA GG GA GG
GGA
GGG
GGA GGG
GG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Gluing GG Produces a “Loop”

This graph is called CC

CCA GCC
the de Bruijn graph CA GC
of Text =
CAT TGC
TAATGCCATGGGATGTT ATG
TAA AAT TGT GTT
for k = 3. TA AA AT
ATG
TG GT TT

ATG
GAT TGG

GA GG
GGA
GGG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Gluing GG Produces a “Loop”

This graph is called CC

CCA GCC
the de Bruijn graph CA GC
of Text =
CAT TGC
TAATGCCATGGGATGTT ATG
TAA AAT TGT GTT
for k = 3. TA AA AT
ATG
TG GT TT

Exercise: Construct GAT

ATG
TGG
the de Bruijn graphs
GA GG
for k = 4 and k = 5. GGA
GGG
How do they differ
from k = 3?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
de Bruijn Graph Becomes Less ”Tangled”
as k Increases (fewer repeats)

k=3
k=4

k=5

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Gluing GG Produces a “Loop”

This graph is called CC

CCA GCC
the de Bruijn graph CA GC
of Text =
CAT TGC
TAATGCCATGGGATGTT ATG
TAA AAT TGT GTT
for k = 3. TA AA AT
ATG
TG GT TT

STOP: If we gave GAT

ATG
TGG
you this graph, could
GA GG
you reconstruct Text? GGA
GGG
How?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Genome Path is Still There

The genome path is

an Eulerian path in CC
CCA 6 5 GCC
the de Bruijn graph,
CA GC
or a path that uses
every edge exactly CAT 7 ATG 4 TGC
8
once. TA
TAA AAT
AA
ATG
AT
TGT GTT
TG14 GT 15 TT
1 2 3
13
ATG
GAT 12 9 TGG

11
GA GG
GGA
GGG
10

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

The Genome Path is Still There

The genome path is

an Eulerian path in CC
CCA 6 5 GCC
the de Bruijn graph,
CA GC
or a path that uses
every edge exactly CAT 7 ATG 4 TGC
8
once. TA
TAA AAT
AA
ATG
AT
TGT GTT
TG14 GT 15 TT
1 2 3
STOP: Can you ATG
13

construct the de GAT 12 9 TGG

Bruijn graph if you GA

GGA
11
GG
GGG
don’t already know 10

Text?
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Forming de Bruijn Graph from k-
mers

Exercise: Here are the 3-mers from our

original dataset represented as isolated
edges. By gluing nodes together, what do
you obtain?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Forming de Bruijn Graph from k-
mers

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 It’s the Same Graph…
CC
CCA GCC

CA GC

CAT TGC
ATG
TAA AAT TGT GTT
ATG
TA AA AT TG GT TT

ATG
GAT TGG

GA GG
GGA
GGG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Approach for Constructing de
Bruijn Graph
1. Form a node for every (k – 1)-mer
appearing as a prefix/suffix in Patterns.
2. For every string in Patterns, connect its
prefix to its suffix.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Approach for Constructing de
Bruijn Graph
1. Form a node for every (k – 1)-mer
appearing as a prefix/suffix in Patterns.
2. For every string in Patterns, connect its
prefix to its suffix.

STOP: Verify this approach for Patterns =

{AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG
TGT}.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Which Graph Would You Rather
Use?
Overlap Graph – find a Hamiltonian
cycle
AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

de Bruijn Graph – find an Eulerian

cycle

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Origin of “Hamiltonian”
Path/Cycle
Hamiltonian cycle: A
Hamiltonian path that
returns to its starting
node.

Exercise: Can you

find a Hamiltonian
cycle in this graph?
(What algorithm did
you use?)

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Origin of “Hamiltonian”
Path/Cycle
Icosian game: William Hamilton, 1857.
Objective is to place pegs 1-20 one at a time
in adjacent holes.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 The Bridges of Königsberg

STOP: Is it possible to walk across each

bridge exactly once and return to the
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 The Bridges of Königsberg

STOP: Is it possible to walk across each

bridge exactly once and return to the
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Leonhard Euler’s Insight (1735)

Define a graph:
• Nodes = 4 land masses
• Edges = 7 bridges

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Leonhard Euler’s Insight (1735)

Define a graph:
• Nodes = 4 land masses
• Edges = 7 bridges

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Leonhard Euler’s Insight (1735)

Note: The Bridges of Königsberg question

has a solution when this graph has an
Eulerian cycle.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Leonhard Euler’s Insight (1735)

STOP: Does this graph help you solve the

original question?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Leonhard Euler’s Insight (1735)

Answer: There is no solution because some

nodes have an odd degree (number of
incident edges).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Leonhard Euler’s Insight (1735)

Even better, Euler would prove how to

quickly determine whether a graph has an
Eulerian cycle.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Intractable Problems

Even better, Euler would prove how to

quickly determine whether a graph has an
Eulerian cycle.

Key Point: And yet no one has ever found a

polynomial-time algorithm to find a
Hamiltonian cycle in a graph!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Similar Problems with Different
Fates
Hamiltonian Cycle Problem
NP-
Input: a network with n nodes.
Complete
Output: “Yes” if there is a cycle visiting
every node in the network; “No”
otherwise.

Eulerian Cycle Problem

Input: a network with n nodes. Polynomial
Output: “Yes” if there is a cycle visiting
every edge in the network; “No”
otherwise.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Euler’s Theorem for Directed
Graphs
Indegree: Number of edges leading into a
node.
Outdegree: Number of edges leading out of
a node.
Balanced graph: Every node has indegree
equal to outdegree.

Balanced Unbalanced

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Euler’s Theorem for Directed
Graphs
Strongly connected graph: A graph
where it is possible to reach every node from
any other node.

Strongly
connected Disconnected

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Euler’s Theorem for Directed
Graphs
Strongly connected graph: A graph
where it is possible to reach every node from
any other node.
Euler’s Theorem: Every balanced, strongly
connected graph has an Eulerian cycle.

Strongly
connected Disconnected

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Take an arbitrary balanced, strongly

connected network, place an ant on any
starting node v0, and let it walk randomly.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

STOP: What must eventually happen when

the ant “gets stuck”?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Because the graph is balanced, the ant must

eventually get stuck at v0!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

If this cycle, which we call Cycle0, is Eulerian,

then we stop. Otherwise, move the ant to a
node on Cycle0 that still has unused edges,
called v1.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Make the ant traverse all of Cycle0 first, then

explore unused edges.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

The same reasoning implies that the ant will

eventually get stuck at v1, creating Cycle1.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

We simply iterate this procedure until we are

out of unused edges, when we have an
Eulerian cycle!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

We simply iterate this procedure until we are

out of unused edges, when we have an
Eulerian cycle!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

STOP: Why can we be sure that this process

will use all the edges?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Answer: Because the graph is strongly

connected! So note that we have used both
conditions in the theorem (balanced and
strongly connected).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Answer: Because the graph is strongly

connected! So note that we have used both
conditions in the theorem (balanced and
strongly connected).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Proof of Euler’s Theorem

Exercise: When will an “undirected” graph

have an Eulerian cycle?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Euler’s Theorem is
“Constructive”

Key Point: This is a “constructive proof”,

meaning it implies an algorithm for finding
an Eulerian cycle.
EulerianCycle(Graph)
v  arbitrary node in Graph
Cycle  randomly walk starting at v (don’t revisit edges)
until cycle
while there are unexplored edges in Graph
newStart  node in Cycle with unexplored edges
Cycle’  cycle formed by traversing Cycle (starting at
newStart)
and then randomly walking
Cycle ← Cycle’
return Cycle
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 From Eulerian Cycles to Paths

STOP: How do we find an Eulerian path in

this graph?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Eulerian Cycles to Paths

Answer: Simply draw an edge connecting

the two unbalanced nodes to form a
balanced graph. Eulerian cycle on right =
Eulerian path on left.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Eulerian Cycles to Paths
STOP: Why will the augmented de Bruijn
graph on the right be balanced for any
collection of strings Patterns?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Eulerian Cycles to Paths

Answer: For every node v in de Bruijn

graph, Indegree(v) and Outdegree(v) are
both equal to # of patterns containing v as
prefix/suffix, respectively.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can Assemble a Genome!
String Reconstruction Problem:
Reconstruct a string from its k-mer
composition.
Input: An integer k and a collection
Patterns of k-mers.
Output: A string Text with k-mer
composition equal to Patterns (if such a
1. string
Form de Bruijn graph G from Patterns.
exists).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can Assemble a Genome!
String Reconstruction Problem:
Reconstruct a string from its k-mer
composition.
Input: An integer k and a collection
Patterns of k-mers.
Output: A string Text with k-mer
composition equal to Patterns (if such a
1. string
Form de Bruijn graph G from Patterns.
exists).
2. Add edge to make modified graph G’
balanced.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can Assemble a Genome!
String Reconstruction Problem:
Reconstruct a string from its k-mer
composition.
Input: An integer k and a collection
Patterns of k-mers.
Output: A string Text with k-mer
composition equal to Patterns (if such a
1. string
Form de Bruijn graph G from Patterns.
exists).
2. Add edge to make modified graph G’
balanced.
3. Find Eulerian cycle in G’.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Can Assemble a Genome!
String Reconstruction Problem:
Reconstruct a string from its k-mer
composition.
Input: An integer k and a collection
Patterns of k-mers.
Output: A string Text with k-mer
composition equal to Patterns (if such a
1. string
Form de Bruijn graph G from Patterns.
exists).
2. Add edge to make modified graph G’
balanced.
3. Find Eulerian cycle in G’.
4. Infer Eulerian path in G from this cycle.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 We Can Assemble a Genome!
String Reconstruction Problem:
Reconstruct a string from its k-mer
composition.
Input: An integer k and a collection
Patterns of k-mers.
Output: A string Text with k-mer
composition equal to Patterns (if such a
1. string
Form de Bruijn graph G from Patterns.
exists).
2. Add edge to make modified graph G’
balanced.
3. Find Eulerian cycle in G’.
4. Infer Eulerian path in G from this cycle.
5. Convert “genome
Bioinformatics Algorithms: An Activepath” into© 2020
Learning Approach. string
Compeau Text.
 Aside: De Bruijn/Good’s
Question
Recall: a binary string is k-universal if it
contains every binary k-mer once.

STOP: How can we

find a k-universal
binary string?

Jack Good Nicolaas de Bruijn

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside: De Bruijn/Good’s
Question
Answer: Construct the “de Bruijn graph” for
Patterns = all binary k-mers; find Eulerian
path.
000 001 010 011 100 101 110 111
00 00 00 01 01 10 01 11 10 00 10 01 11 10 11 11

000
001
00 01

010
100 011
101
10 11
110
111
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Aside: De Bruijn/Good’s
Question
STOP: How can we find a 4-universal
circular string?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Aside: De Bruijn/Good’s
Question
STOP: How can we find a 4-universal
circular string?

Answer: Find an Eulerian cycle in dB graph

below. 0011
001 011
3
0010 1011
0001 2 0101 10 0111
0000 7 8 9 1111

1001 6 1 000 010 101 111 11 4 0110

15 14 13
1010
1000 16 0100 1101 12 1110
5
100 110
1100

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Outline

• Exploding Newspapers and Genome Sequencing

• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path
Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Complications of Genome
Assembly
1. Reads have imperfect “coverage” of the
underlying genome – there may be some
regions that are not covered by any reads.

2. Sequencing machines are error-prone.

3. Exact multiplicities of k-mers are unknown.

4. DNA is double-stranded (and may consist

of multiple chromosomes).

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Coverage is Never Perfect

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Should Define Coverage
Precisely
Coverage of k-
mer in genome:
Number of reads
that contain this k-
mer.

Plotting k-mer coverage over entire genome

Kawada et al., 2016
[Link]

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 We Should Define Coverage
Precisely
Coverage of k-
mer in genome:
Number of reads
that contain this k-
mer.
Coverage of
reads: Number of
nucleotides in reads
belongs divided by Plotting k-mer coverage over entire genome
Kawada et al., 2016

length of underlying [Link]

genome.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 We Should Define Coverage
Precisely
Coverage of k- STOP: Say that we
mer in genome: have a collection of
Number of reads length-300 reads with
that contain this k- 25x coverage. Can
mer. we apply the
Coverage of assembly algorithms
reads: Number of we have learned?
nucleotides in reads
belongs divided by
length of underlying
genome.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Boosting Coverage through Read
Breaking

ATGCCGTATGGACAACGACT ATGCCGTATGGACAACGACT
ATGCCGTATG ATGCC
GCCGTATGGA TGCCG
GTATGGACAA GCCGT
GACAACGACT CGTAT
GTATG
TATGG
ATGGA
TGGAC
Read breaking: Split each GGACA
read into all its k-mer GACAA
ACAAC
substrings (for a smaller CAACG
AACGA
value of k). ACGAC
CGACT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Boosting Coverage through Read
Breaking

ATGCCGTATGGACAACGACT ATGCCGTATGGACAACGACT
ATGCCGTATG ATGCC
GCCGTATGGA TGCCG
GTATGGACAA GCCGT
GACAACGACT CGTAT
GTATG
TATGG
ATGGA
TGGAC
Note: The smaller value of GGACA
k, the higher our coverage GACAA
ACAAC
will be, but also the more CAACG
AACGA
repeats and the more ACGAC
”tangled” our graph. CGACT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assembling Contigs

Even after read breaking, most assemblies

have gaps in their coverage, and we will not
have a true Eulerian path in the de Bruijn
graph.

Real assembly software instead tries to infer

(a small number of) contigs: contiguous
genome segments.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assembling Contigs

Even after read breaking, most assemblies

have gaps in their coverage, and we will not
have a true Eulerian path in the de Bruijn
graph.

Real assembly software instead tries to infer

(a small number of) contigs: contiguous
genome segments.

Can we find contigs in the de Bruijn graph?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Contigs Lurking in the de Bruijn
Graph
A path in a graph is called non-branching if
InDegree(v) = OutDegree(v) = 1 for each
“intermediate” node v in the path.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Contigs Lurking in the de Bruijn
Graph
A path in a graph is called non-branching if
InDegree(v) = OutDegree(v) = 1 for each
“intermediate” node v in the path.

A maximal non-branching path is a non-

branching path that cannot made longer in
either direction.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Contigs Lurking in the de Bruijn
Graph
A path in a graph is called non-branching if
InDegree(v) = OutDegree(v) = 1 for each
“intermediate” node v in the path.

A maximal non-branching path is a non-

branching path that cannot made longer in
either direction.

Note: In mathematics, “maximum” means

“global maximum”; “maximal” means “local
maximum”.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
Transforming dB Graph into
Paths

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Transforming dB Graph into
Paths
STOP: Why do you
think we are
interested in maximal
non-branching paths
in genome assembly?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Transforming dB Graph into
Paths
STOP: Why do you
think we are
interested in maximal
non-branching paths
in genome assembly?
Answer: They
represent ”subpaths”
that must be present
in any assembly, and
so we can be
confident in them.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Assembling Error-Prone Reads

STOP: Say we sequence both the correct

read CGTACGGACA and the incorrect read
CGTACGGACA. What will we see in the de
Bruijn graph after read breaking for k = 5?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Assembling Error-Prone Reads

STOP: Say we sequence both the correct

read CGTACGGACA and the incorrect read
CGTACGGACA. What will we see in the de
Bruijn graph after read breaking for k = 5?

Answer: A “bubble”!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Popping Bubbles

Bubble: Two disjoint short path (less than

some threshold length) connecting the same
pair of nodes in the de Bruijn graph.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Popping Bubbles

Bubble: Two disjoint short path (less than

some threshold length) connecting the same
pair of nodes in the de Bruijn graph.

STOP: How might we remove bubbles?

What would cause your approach to go
wrong?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Popping Bubbles

Inexact repeat: Repeated region in

genome with minor variations; the variations
look just like sequencing errors!

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Popping Bubbles

Inexact repeat: Repeated region in

genome with minor variations; the variations
look just like sequencing errors!

Lower “multiplicity” paths are likely errors;

this is one more benefit of higher coverage
in assembly.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 dB Graph of N. meningitidis
(Bacterium) After Removing Bubbles
Red edges represent repeats

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Inferring Multiplicities

We will not know a priori how often a read

really occurs in a genome.

STOP: How might we estimate the

multiplicity of a k-mer?

Answer: Estimate multiplicity of a k-mer

using read coverage (i.e., how many reads
this k-mer appears in) compared to
coverage of entire read set.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Pitfalls of Double-Stranded
DNA
DNA is double-stranded, and the two strands
are reverse complements of each other.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Pitfalls of Double-Stranded
DNA
Reads may come from either strand, so we need
to consider each read’s reverse complement.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Pitfalls of Double-Stranded
DNA
CAT
Note that this
example is ATA ATG TGT GTC TCA
trivial if we TA AT TG GT TC CA

had two de GAT

DeBruijn3(GATGTCATA)
Bruijn graphs GA

(one for the CAT

string, one for ATC

its reverse TA
TAT
AT
ATG
TG TC CA
complement). TGA ACA

GA AC
GAC DeBruijn3(TATGACATC)

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Pitfalls of Double-Stranded
DNA
The reality is CAT
that we see
ATC
the ATA TGT GTC TCA
TA AT TG GT TC CA
amalgamation TAT ATG
TGA ACA
of both graphs. GAT
GATGTCATA
GA AC TATGACATC
GAC

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Pitfalls of Double-Stranded
DNA
The reality is CAT
that we see
ATC
the ATA TGT GTC TCA
TA AT TG GT TC CA
amalgamation TAT ATG
GAT TGA ACA
of both graphs. GATGTCATA
GA AC TATGACATC
GAC

Even though neither string has a repeat, the

graph becomes tangled because ATG and
CAT are inverted repeats: the strings are
reverse complements of each other.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
de Bruijn Assembly in Research

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Outline
• Exploding Newspapers and Genome Sequencing
• The String Reconstruction Problem
• String Reconstruction as a Hamiltonian Path Problem
• String Reconstruction as an Eulerian Path Problem
• The Icosian Game and the Bridges of Konigsberg
• From Euler’s Theorem to an Algorithm for Genome
Assembly
• De Bruijn Graphs Face Harsh Realities of Assembly
• Bonus Content: Using Read-Pairs for Assembly

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Longer Reads Means More
Accuracy CCA

CC CCAT GCCA

CCA GCC CAT GCC

CA GC TGCC
CATG
TGC TGC
CAT ATGC
ATG TAAT AATG TGTT
ATGT TGT GTT
TAA AAT TGT GTT TAA AAT ATG
ATG 4-universal
TA AA AT TG GT TT ATGG
TGG
GATG
ATG TGGG
GAT
TGG
k=4
GGG
k=3
GAT
GA GG
GGA GGAT GGGA
GGG
CCA

k=5
TAATG AATGC ATGCC TGCCA GCCAT CCATG CATGG ATGGG TGGGA GGGAT GGATG GATGT ATGTT
TAAT AATG ATGC TGCC GCCA CCAT CATG ATGG TGGG GGGA GGAT GATG ATGT TGTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Reads to Read-Pairs

A huge amount of investment has been put

into making longer, more accurate,
inexpensive reads.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Reads to Read-Pairs

A huge amount of investment has been put

into making longer, more accurate,
inexpensive reads.
One innovation has been read-pairs: a pair
of reads is sequenced, approximately d
nucleotides apart.

200 bp 200 bp

“Insert
length”
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 From Reads to Read-Pairs

Checkpoint: Why might read-pairs help us

in genome assembly?

One innovation has been read-pairs: a pair

of reads is sequenced, approximately d
nucleotides apart.

200 bp 200 bp

“Insert
length”
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
and Pevzner.
 From Reads to Read-Pairs

Note: We will make the additional

assumption that d is fixed.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Reads to Read-Pairs

Note: We will make the additional

assumption that d is fixed.

(k, d)-mer: A pair of k-mers separated by d

symbols.
For example, (ATG|GGG) is a (3, 4)-mer in Text
= TAATGCCATGGGATGTT.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Reads to Read-Pairs

(k, d)-mer composition: The collection of

all (k, d)-mers in a string Text.

Below: (3,1)-composition of
TAATGCCATGGGATGTT. Note that there are no
repeated (3, 1)-mers!
AAT
-CC
A
TAA-GCC CA- GGG
C
ATG-
GAT T GG AT C
G- C- TG
AT GC C- GGG-TGT
GGA-G CAT AT
TT -GG G T GG-ATG
A

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 From Reads to Read-Pairs

Exercise: Generate the (3, 2)-mer

composition of TAATGCCATGGGATGTT.

Below: (3,1)-composition of
TAATGCCATGGGATGTT. Note that there are no
repeated (3, 1)-mers!
AAT
-CC
A
TAA-GCC CA- GGG
C
ATG-
GAT T GG AT C
G- C- TG
AT GC C- GGG-TGT
GGA-G CAT AT
TT -GG G T GG-ATG
A

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

A Computational Problem for Read-
Pair Assembly

Checkpoint: Can you formulate a

computational problem for genome assembly
from read-pairs?

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

A Computational Problem for Read-
Pair Assembly

Checkpoint: Can you formulate a

computational problem for genome assembly
from read-pairs?
String Reconstruction from Read-Pairs
Problem: Reconstruct a string from its
paired composition.
Input: A collection of paired k-mers
PairedReads and an integer d.
Output: A string Text with (k, d)-mer
composition equal to PairedReads (if such
a string exists).
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Idea 1: Transforming Read-Pairs
into Long “Virtual” Reads

Each (k, d)-mer must CC

be a path of k + d + 1 CCA GCC

in the de Bruijn graph CA GC

for k-mers. CAT ATG TGC

TAA AAT TGT GTT
ATG
AAT TA AA AT TG GT TT
-CC
A
GGG
TAA-GCC CCA- ATG
T G ATG- GAT TGG
GA TG ATC
G- C- TG
AT GC C- GGG-TGT GG
GA
GGA-G CAT AT GGA
TT -GG G T GG-ATG GGG
A

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Idea 1: Transforming Read-Pairs
into Long “Virtual” Reads

Example: highlighted CC
path corresponds to CCA GCC

AAT-CCA; we infer the CA GC

virtual read AATGCCA CAT ATG TGC

from this path. TAA AAT
ATG
TGT GTT
AAT TA AA AT TG GT TT
-CC
A
GGG
TAA-GCC CCA- ATG
T G ATG- GAT TGG
GA TG ATC
G- C- TG
AT GC C- GGG-TGT GG
GA
GGA-G CAT AT GGA
TT -GG G T GG-ATG GGG
A

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Not All Virtual Read Paths are Valid

Highlighted paths: virtual reads for (3, 3)-

mer AAT-ACA in DeBruijn3(AATCTGACATATGG).

AC AC
ACA GAC ACA GAC

CA GA CA GA
TC CT TC CT
CAT TCT CAT TCT
TGA TGA
ATC CTG ATC CTG
AAT TGG AAT TGG
AA AT TG GG AA AT TG GG

ATA ATG ATA ATG

TA TAT AT TA TAT AT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Not All Virtual Read Paths are
Valid
Exercise: What virtual reads do they spell
out?

AC AC
ACA GAC ACA GAC

CA GA CA GA
TC CT TC CT
CAT TCT CAT TCT
TGA TGA
ATC CTG ATC CTG
AAT TGG AAT TGG
AA AT TG GG AA AT TG GG

ATA ATG ATA ATG

TA TAT AT TA TAT AT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Not All Virtual Read Paths are
Valid
Exercise: What virtual reads do they spell
out?
AATCTGACA AATATGACA
AC AC
ACA GAC ACA GAC

CA GA CA GA
TC CT TC CT
CAT TCT CAT TCT
TGA TGA
ATC CTG ATC CTG
AAT TGG AAT TGG
AA AT TG GG AA AT TG GG

ATA ATG ATA ATG

TA TAT AT TA TAT AT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Not All Virtual Read Paths are
Valid
But only one of these reads occurs in the
original string AATCTGACATATGG!
AATCTGACA AATATGACA
AC AC
ACA GAC ACA GAC

CA GA CA GA
TC CT TC CT
CAT TCT CAT TCT
TGA TGA
ATC CTG ATC CTG
AAT TGG AAT TGG
AA AT TG GG AA AT TG GG

ATA ATG ATA ATG

TA TAT AT TA TAT AT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Not All Virtual Read Paths are
Valid
The presence of multiple paths in the de
Bruijn graph prevents us from inferring
virtual reads.
AATCTGACA AATATGACA
AC AC
ACA GAC ACA GAC

CA GA CA GA
TC CT TC CT
CAT TCT CAT TCT
TGA TGA
ATC CTG ATC CTG
AAT TGG AAT TGG
AA AT TG GG AA AT TG GG

ATA ATG ATA ATG

TA TAT AT TA TAT AT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Idea 2: Paired de Bruijn Graphs

Prefix/suffix of (k, d)-mer: The (k – 1, d +

1)-mer formed by taking prefix/suffix of each
k-mer.
Example: Prefix((GAC|TCA)) = (GA|TC),
Suffix((GAC|TCA)) = (AC|CA)

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Idea 2: Paired de Bruijn Graphs

Paired de Bruijn graph: Analogue of de

Bruijn graph for (k, d)-mer composition.
Assign each (k, d)-mer to an edge
connecting its prefix to its suffix. Then, glue
nodes with the same labels.
AA
G G AA CCAT
ATAT TAT CC
G GCCG A
T CAT TG CC CAT CCA
A A GG
G CA GGA GC
G ATAGT G CC
GGG
GG AT T C TT G CA
T A G GG
GA AA TA GTAA
C GC CC
GGG
TGT A
GG GG CCA TGG
G
GG GTGTA TG GT TG ATGC ATG
GT AT T G TG GG
G GC AT TG
TTA TG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Idea 2: Paired de Bruijn Graphs

Exercise: What will the paired de Bruijn

graph look like for the (3, 1)-mer
composition of TAATGCCATGGGATGTT? (Shown
below.)
AA
G G AA CCAT
ATAT TAT CC
G GCCG A
T CAT TG CC CAT CCA
A A GG
G CA GGA GC
G ATAGT G CC
GGG
GG AT T C TT G CA
T A G GG
GA AA TA GTAA
C GC CC
GGG
TGT A
GG GG CCA TGG
G
GG GTGTA TG GT TG ATGC ATG
GT AT T G TG GG
G GC AT TG
TTA TG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Idea 2: Paired de Bruijn Graphs

Exercise: What will the paired de Bruijn

graph look like for the (3, 1)-mer
composition of TAATGCCATGGGATGTT? (Shown
below.)
AA
G G AA CCAT
ATAT TAT CC
G GCCG A
T CAT TG CC CAT CCA
A A GG
G CA GGA GC
G ATAGT G CC
GGG
GG AT T C TT G CA
T A G GG
GA AA TA GTAA
C GC CC
GGG
TGT A
GG GG CCA TGG
G
GG GTGTA TG GT TG ATGC ATG
GT AT T G TG GG
G GC AT TG
TTA TG

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

Idea 2: Paired de Bruijn Graphs

Exercise: What will the paired de Bruijn

graph look like for the (3, 1)-mer
composition of TAATGCCATGGGATGTT? (Shown
below.)
GCC CCA CAT
TGG GGG GGA
TGC GC CC CA AT
ATG TG GG GG GA ATG
GAT
TAA AAT ATG
GCC CCA CAT
TA AA AT TG GG GG GA
GC CC CA AT TG GT TT
TGG GGG GGA
ATG TGT GTT

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Cycles
Exercise: Below is a paired de Bruijn graph
constructed from nine (2,1)-mers.
Reconstruct the genome spelled by the
Eulerian path (AG|AG)  (GC|GC)  (CA|CT) 
(AG|TG)  (GC|GC)  (CT|CT)  (TG|TG)  (GC|GC)
 (CT|CA). A
T
AG CA
TG CT
GC
AG GC CT
A AG G C CA T
A G C A

TG CT
TG CT
T
T

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Cycles
Answer: Shown below. Note that every
column has the same nucleotides, which we
call “consistent”.
AG-AG
GC-GC
CA-CT
A
AG-TG T
GC-GC AG
TG
GC
CA
CT
CT-CT A
AG
AG G
GC
C
CT
CA T
TG-TG A G C A

GC-GC TG
TG
CT
CT
CT-CA T
AGCAGCTGCTGCA T

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Paths
Exercise: Reconstruct the genome
corresponding to the Eulerian path (AG|AG) 
(GC|GC)  (CT|CT)  (TG|TG)  (GC|GC)  (CA|CT)
 (AG|TG)  (GC|GC)  (CT|CA).

A
T
AG CA
TG CT
GC
AG GC CT
A AG G C CA T
A G C A

TG CT
TG CT
T
T

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Paths
Answer: Now, some columns disagree, and
we cannot infer a single genome!

AG-AG
GC-GC
CT-CT
A
TG-TG T
GC-GC AG
TG
GC
CA
CT
CA-CT A
AG
AG G
GC
C
CT
CA T
AG-TG A G C A

GC-GC TG
TG
CT
CT
CT-CA T
AGC?GC?GCTGCA T

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Paths
In other words, for k-mers, every Eulerian
path in the de Bruijn graph corresponds to a
genome, but for (k, d)-mers, we have to
check for consistency.
AG-AG
GC-GC
CT-CT
A
TG-TG T
GC-GC AG
TG
GC
CA
CT
CA-CT A
AG
AG G
GC
C
CT
CA T
AG-TG A G C A

GC-GC TG
TG
CT
CT
CT-CA T
AGC?GC?GCTGCA T

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 Reconstructing Genome from
Eulerian Paths
We can reconstruct a genome precisely
when the string constructed from prefixes
coincides with the string constructed from
suffixes.
AG-AG
GC-GC PrefixString =
CA-CT
AG-TG AGCAGCTGCT
GC-GC SuffixString =
CT-CT
TG-TG AGCTGCTGCA
GC-GC
CT-CAGenome =
AGCAGCTGCTGCA
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau
 Reconstructing Genome from
Eulerian Paths
We can reconstruct a genome precisely
when the string constructed from prefixes
coincides with the string constructed from
suffixes.
AG-AG
GC-GC PrefixString =
CT-CT
TG-TG AGCTGCAGCT
GC-GC SuffixString =
CA-CT
AG-TG AGCTGCTGCA
GC-GC
CT-CAGenome = AGC?GC?
AGC?GC?GCTGCAGCTGCA

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 An Algorithm for Read-Pair
Assembly
1. Construct the paired de Bruijn graph.
2. Find an Eulerian cycle in this graph.
3. Produce PrefixString and SuffixString from
the Eulerian cycle.
4. Are they consistent? If so, produce the
genome. If not, return to step 2.

Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau

 An Algorithm for Read-Pair
Assembly
1. Construct the paired de Bruijn graph.
2. Find an Eulerian cycle in this graph.
3. Produce PrefixString and SuffixString from
the Eulerian cycle.
4. Are they consistent? If so, produce the
genome. If not, return to step 2.

Better: produce all Eulerian cycles (instead

of relying on random walking). Enumerating
all Eulerian cycles is beyond scope of this
lecture.
Bioinformatics Algorithms: An Active Learning Approach. © 2020 Compeau