Ghent University

Faculty of Sciences

Computational Biology

Genome assembly
(graph algorithms)

Prof. Dr. Peter Dawyndt

[Link]@[Link]
@dawyndt
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Who are these people?
The human genome is a three billion nucleotide
long "book" written in the A, C, G, T alphabet.

Leonhard Euler William Rowan Hamilton Nicolaas Govert de Bruijn

(1707 – 1783) (1805 – 1865) (1918 – 2012)
Who are these people?
The human genome is a three billion nucleotide
long "book" written in the A, C, G, T alphabet.

Some genomes are 100× larger than the human

genome.

Volland JM, Gonzalez-Rizzo S, Gros O, Tyml T, Ivanova N,

Schulz F, Goudeau D, Elisabeth NH, Nath N, Udwary D,
Malmstrom RR (2022). A centimeter-long bacterium with
Amoeba dubia Paris japonica
DNA compartmentalized in membrane-bound organelles.
bioRxiv.
Why sequencing 1000s of species?

Applications in medicine (genomes of fungi-producing

bacteria), agriculture (oil palm genome), biotechnology
(genomes of energy-producing cyanobacteria), etc., etc., etc.
Caenorhabditis elegans
Caenorhabditis elegans, also known as C.
elegans, is a nematode, a model organism
and the first multicellular-organism to have
a genome that was completely sequenced.

Scientific work on or utilizing

C. elegans has produced
6 Nobel Prize winners.
 1977
1980

Walter Walter
Gilbert Gilbert
Fred Sanger
Fred Sanger

develop
share
DNA
Nobel
sequencing
Prize formethods
developing
independently
DNA sequencing
from each
methods
other

Still, their sequencing methods were too expensive

($3 billion to sequence the human genome).

Collins F.S. et al. (2003). Nature 422, 835-847.

 1990
1997 Francis Collins

The public Human Genome

Project aims to sequence the
human genome by 2005.
Craig Venter

Found Celera Genomics, a private

company, with the same goal.

Collins F.S. et al. (2003). Nature 422, 835-847.

 Two sequencing strategies
hierarchical shotgun sequencing cloned genomes
public Human Genome Project (HUGO)
genomes divided into large
segments of known order

ordered genome segments

multiple genome portions are

sheared into variable sized
segments

unordered sequenced segments

computational automated assembly

resulting overlapping sequence

segments (the higher the coverage
the better the quality of the
sequencing)
Commins J, Toft C, Fares MA (2009). Computational
biology methods and their application to the comparative
genomics of endocellular symbiotic bacteria of insects. overlapping sequence segments
Biological procedures online 11(1), 52. combined to construct the genome
consensus
 Two sequencing strategies
whole genome shotgun (WGS) sequencing
cloned genomes
private Human Genome Project (Celera)
multiple genomes are sheared into
variable sized segments

unordered sequenced segments

computational automated assembly

resulting overlapping sequence

segments (the higher the coverage
the better the quality of the
sequencing)

overlapping sequence segments

Commins J, Toft C, Fares MA (2009). Computational combined to construct the genome
biology methods and their application to the comparative consensus
genomics of endocellular symbiotic bacteria of insects.
Biological procedures online 11(1), 52.
 2000

entire genome of
1997
Homo sapiens sapiens

Craig Venter

Found Celera Genomics, a private

company, with the same goal.

Collins F.S. et al. (2003). Nature 422, 835-847.

From human to mouse to …

Early 2000s: Many more mammalian genomes are sequenced

using the same Sanger sequencing method, but it is clear that
new technology is needed for further progress.
Next generation sequencing
 late 2000s: the market for new sequencing machines
takes off
• Illumina reduces the cost of sequencing a human genome
from $3 billion to $100,000
• Complete Genomics builds a genomic factory in Silicon
Valley that sequences hundreds of genomes per month
• Beijing Genome Institute orders hundreds of sequencing
machines, becoming the world's largest sequencing
center.
Personalized genomics
Few mutations → big difference …
Different people have slightly different genomes: on average
roughly 1 mutation in 1000 nucleotides.

The 1 in 1000 nucleotides difference accounts for height, high

cholesterol susceptibility and thousands of genetic diseases.

GAGATTAAACTATAACTTATTAGGCCGAGTTCCCGCTATG
GGAAAGGTTCGAGTTGCAGTATATCCTCGCCGTTCATCGT
TGATTCCACCCACCGTTATAAGTAGTAACGGAGTCAGCCG
TGTTCGGGAAAATCGGACCTGTACGGTAGAAGTCCAGCAG
GAGATTAAACTATAACTTATTAGGCCGAGTTCCCGCTATG
GCTCGCTACGGTAAACAAGTAGTAAGCTACCCAAAATCGT
GGAAAGGTTGGAGTTGCAGTATATCCTCGCCGTTCATCGT
AATGTGCAGAAAGAACAGCCGCCCAAGTGAGCATGTCCAT
TGATTCCACCCACCGTTATAAGTAGTAACGGAGTCAGCCG
TGTTCGGGAAAATCGGACCTGTACGGTAGAAATCCAGCAG
GAGATTAAACTATAACTTATTAGGCCGAGTTCCCGCTATG
GCTCGCTACGGTAAGCAAGTAGTAAGCTACCCAAAATCGT
GGAAAGGTTAGAGTTGCAGTATATCCTCGCCGTTCATCGT
AATGTGCAGAAAGAACAGCCGCCCAAGTGAGCATGTCCAT
TGATTCCACCCACCGTTATAAGTAGTAACGGAGTCAGCCG
TGTTCGGGAAAATCGGACCTGTACGGTAGAATTCCAGCAG
GCTCGCTACGGTAACCAAGTAGTAAGCTACCCAAAATCGT
AATGTGCAGAAAGAACAGCCGCCCAAGTGAGCATGTCCAT
Personalized medicine
 2010: Nicholas Volker became the first human being to
be saved by genome sequencing
• doctors could not diagnose his condition, so he went
through dozens of surgeries
• sequencing revealed a rare mutation in a XIAP gene linked
to a defect in his immune system
• this led doctors to use immune therapy,
which save the child's life
10.000 genomes and beyond
 2010: scientists launch a project to sequence 1.000
human genomes and 10.000 vertebrate genomes

 now: human genome sequencing costs around $1.000

Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
The newspaper problem
The newspaper problem
The newspaper problem
 Generating reads
GTAACCCG
GTAACCCGGTGGAACGGACTCGGGGACACATACAACATACGAATATCCGTGCGGGCCTGTCAGTGGGTCCCACAAAGCCA
GTGGAACGG ACTCGGG GACACA TACAACATACG AATATCCGT GCGGGCCT GTCAGTG GGTCCCACAA AGCCA
GTAACC
GTAACCCGGTGGAACGGACTCGGGGACACATACAACATACGAATATCCGTGCGGGCCTGTCAGTGGGTCCCACAAAGCCA
CGGTGGAACGG ACTCGG GGACACAT ACAACAT ACGAATATC CGTGCG GGCCTGTC AGTGGGTC CCACAAAGCCA
GTAACCCGG
GTAACCCGGTGGAACGGACTCGGGGACACATACAACATACGAATATCCGTGCGGGCCTGTCAGTGGGTCCCACAAAGCCA
TGGAACG GACTCGGG GACACATA CAACATACG AATAT CCGTGCGG GCCTGTC AGTGG GTCCCAC AAAGCCA
GTAACGTAACCCGGTGGAACGGACTCGGGGACACATACAACATACGAATATCCGTGCGGGCCTGTCAGTGGGTCCCACAAAGCCA
CCGGTGGAACG GACTCGGG GACAC ATACAACATAC GAAT ATCCGTGCG GGCCT GTCAGT GGGTCC CACAAAGCCA

rea
ds
 Generating reads
GTAACCCG ACTCGGG GACACA TACAACATACG AATATCCGT GCGGGCCT GTCAGTG GGTCCCACAA AGCCA
GTAACC CGGTGGAACGG ACTCGG GGACACAT ACAACAT ACGAATATC CGTGCG GGCCTGTC AGTGGGTC CCACAAAGCCA
GTAACCCGG TGGAACG GACTCGGG GACACATA CAACATACG AATAT GCCTGTC AGTGG GTCCCAC AAAGCCA
GTAAC CCGGTGGAACG GACAC ATACAACATAC GAAT ATCCGTGCG GGCCT GTCAGT GGGTCC CACAAAGCCA

AATA
T CCGT

G
T GC
G
CC
AT
 Genome assembly
ple (unsequenced) genome copies

read generation (sequencing)

reads

genome assembly
ssembled genome
…GTAACCCGGTGGAACGGACTCGGGGACACATACAACATACGAATATCCGTGCGGGCCTGTCAGTGGGTCCCACAAAGCCA…
What makes assembly difficult?
 modern sequencing machines cannot read an entire
genome one nucleotide at a time from beginning to end
(like we read a book)
 sequencing machines can only shred the genome and
generate short reads
 genome assembly is not entirely the same as a jigsaw
puzzle as we must use overlapping reads to reconstruct
the genome: a giant overlap puzzle!
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Genome assembly problem

problem description
 reconstruct a genome from a given collection of reads
 input: a collection of strings Reads
 output: a string Genome reconstructed from Reads

This is not a computational problem!

k-mer composition
COMPOSITION3(TAATGCCATGGGATGTT) =
TAA
AAT
ATG
TGC
GCC
CCA
CAT
ATG
TGG
GGG
GGA
GAT
ATG
TGT
GTT
 k-mer composition
COMPOSITION3(TAATGCCATGGGATGTT) =
TAA AAT ATG TGC TAA
GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
AAT
ATG
TGC
GCC
CCA
CAT
ATG
TGG
GGG
GGA
GAT
ATG
TGT
GTT
 k-mer composition
COMPOSITION3(TAATGCCATGGGATGTT) =
TAA
TAA AAT
AAT ATG
ATG TGC
TGC GCC
GCC CCA
CCA CAT
CAT ATG
ATG TGG
TGG GGG
GGG GGA
GGA GAT
GAT ATG
ATG TGT
TGT GTT
GTT
=
AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

e.g. lexicographic order (like in a dictionary)

 String reconstruction problem
COMPOSITION3(TAATGCCATGGGATGTT) =
TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
=
AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT

e.g. lexicographic order (like in a dictionary)

problem description
 reconstruct a string from its k-mer composition
 input: a collection of k-mers
 output: a string Genome such that
COMPOSITIONk(Genome) is equal to the given collection
of k-mers
 Naive reconstruction approach

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

backtracking
Naive reconstruction approach
ATG ATG CAT CCA GAT GCC GGA GGG GTT TGC TGG

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

TAA
AAT
ATG
Naive reconstruction approach

TAA
AAT
ATG
TGC
GCC
CCA
CAT
ATG
TGG
GGG
GGA
GAT
ATG
TGT
GTT
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
 Representing a genome as a path
COMPOSITION3(TAATGCCATGGGATGTT) =

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
 Representing a genome as a path
COMPOSITION3(TAATGCCATGGGATGTT) =

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

Can we reconstruct this genome path without knowing the

genome TAATGCCATGGGATGTT, only from its composition?

Yes, we simply need to connect k-mer1 with k-mer2 if

SUFFIX(k-mer1) = PREFIX(k-mer2), e.g. TAA → AAT
 Representing a genome as a graph

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

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

Yes, we simply need to connect k-mer1 with k-mer2 if

SUFFIX(k-mer1) = PREFIX(k-mer2), e.g. TAA → AAT
 Representing a genome as a graph

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

Can we still find the genome path in this graph?

 Representing a genome as a graph

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

Can we still find the genome path in this graph?

 Where is the genomic path?

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

Nodes are arranged from left to right in lexicographic order.

 Where is the genomic path?
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT

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

Nodes are arranged from left to right in lexicographic order.

 Where is the genomic path?
TAATGCCATGGGATGTT

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

What are we trying to find in this graph?

Hamiltonian path: a path that visits each node in the graph

exactly once.
 Hamiltonian path problem
TAATGCCATGGGATGTT

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

problem description
 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once
Hamiltonian path problem

problem description
 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once
 Hamiltonian path problem
icosian game (1857)

William Rowan Hamilton

(1805 – 1865)

problem description
 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
 Multiple genomics paths
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 Multiple genomics paths
TAATGCCATGGGATGTT
TAA
TAAT
TAATG
TAATGG
TAATGGG
TAATGGGA
TAATGGGAT
TAATGGGATG
TAATGGGATGC
TAATGGGATGCC
TAATGGGATGCCA
TAATGGGATGCCAT
TAATGGGATGCCATG
TAATGGGATGCCATGT
TAATGGGATGCCATGTT

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 A slightly different path
TAATGCCATGGGATGTT
TAATGCCATGGGATGTT

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

3-mers as nodes

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

3-mers as edges
How do we label the starting
and ending node of an edge?
TAA
PREFIX(TAA) TA AA SUFFIX(TAA)
 A slightly different path
TAATGCCATGGGATGTT

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

3-mers as nodes

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

3-mers as edges
2-mers as nodes
 Gluing identically labeled nodes
TAATGCCATGGGATGTT

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
 Gluing identically labeled nodes
TAATGCCATGGGATGTT

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
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

CAT TGC

AT ATG TG

TGG GGG GGA GAT ATG TGT GTT

TAA AAT
TA AA AT ATG TG GG GG GA AT TG GT TT
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

CAT TGC

AT ATG TG

TGG GGG GGA GAT ATG TGT GTT

TAA AAT
TA AA AT ATG TG GG GG GA AT TG GT TT
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC CC

CCA CCA GCC GCC

CA CA GC GC

CAT CAT TGC TGC

AT AT ATG ATG
TG TG

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

AT AT TG TG
ATG ATG
GAT GAT TGG TGG

GA GA GG GG

GGA GGA GGG GGG

GG GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

GC
CA
TGC
CAT
ATG TG

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

GAT ATG TG
TGG
GA
GG
GGA
GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

GCC
CCA
GC
CA
TGC
ATG TG
CAT

TAA AAT ATG TG TGT GT GTT TT

TA AA AT

GAT
ATG TG

GA TGG

GG
GGA
GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

GCC
CCA
GC
CA
TGC
ATG TG
CAT

TAA AAT ATG TG TGT GT GTT TT

TA AA AT

GAT
ATG TG

GA TGG

GG
GGA
GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

GCC
CCA
GC
CA
TGC

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

GGA GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG

GGA GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG

GGA GGG

GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG
GG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GG GGG
GGA
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG
Gluing identically labeled nodes
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

DEBRUIJN3(TAATGCCATGGGATGTT)
 Gluing identically labeled nodes
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT
CC

CCA GCC
Where is the Genome
hiding in this graph? CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

DEBRUIJN3(TAATGCCATGGGATGTT)
Gluing identically labeled nodes
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
GAT TGG

What are we trying to find in this graph?

GA GG
GGA GGG

Eulerian path: a path that visits each edge in the graph exactly
once. DEBRUIJN3(TAATGCCATGGGATGTT)
Eulerian path problem
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT
CC

CCA GCC

CA GC

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

ATG
problem description
GAT TGG

 find an Eulerian path in a graph

GA GG
GGA
 input: a graph GGG

 output: a path visiting every edge in the graph exactly

once
DEBRUIJN (TAATGCCATGGGATGTT)
3
Eulerian path problem

problem description
 find an Eulerian path in a graph
 input: a graph
 output: a path visiting every edge in the graph exactly
once
Eulerian vs Hamiltonian paths

Hamiltonian path problem

 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once

Eulerian path problem

 find an Eulerian path in a graph
 input: a graph
 output: a path visiting every edge in the graph exactly
once
Eulerian vs Hamiltonian paths

Hamiltonian path problem

 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once

Eulerian path problem

 find an Eulerian path in a graph
 input: a graph
 output: a path visiting every edge in the graph exactly
once
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Eulerian vs Hamiltonian paths

Hamiltonian path problem

 find a Hamiltonian path in a graph
 input: a graph
 output: a path visiting every node in the graph exactly
once

Eulerian path problem

 find an Eulerian path in a graph
 input: a graph
 output: a path visiting every edge in the graph exactly
once
 Eulerian vs Hamiltonian paths

Which of these two problems

would you prefer to solve?

While Euler solved the Eulerian path problem (even for

a city with million of bridges), nobody has developed a
fast algorithm for the Hamiltonian path problem.
NP-complete problems
The Hamiltonian path problem belongs to a collection containing
thousands of computational problems for which no fast
algorithms are known.

I can’t find an
efficient
algorithm, I
guess I’m just
too dumb.

Garey MR, Johnson DS (1979).

Computers and intractability.
San Francisco: freeman.
A change of attitude
That would be an excellent argument, but the question of
whether or not NP-complete problems can be solved efficiently is
one of the seven Millenium Problems in mathematics.

I can’t find an
efficient
algorithm,
because no
such algorithm
is possible.

Garey MR, Johnson DS (1979).

Computers and intractability.
San Francisco: freeman.
The modern state of affairs

NP-complete problems are all equivalent: find an efficient

solution to one, and you have an efficient solution to all of them.

I can’t find an
efficient
algorithm, but
neither can all
these famous
people.

Garey MR, Johnson DS (1979).

Computers and intractability.
San Francisco: freeman.
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Eulerian path problem
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT

CC We constructed the de
Bruijn graph from Genome,
CCA GCC but in reality, Genome is
unknown!
CA GC

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

problem description
GAT
ATG
TGG
 find an Eulerian path in a graph
 input: a graph GA GGA GG
GGG
 output: a path visiting every edge in the graph exactly
once
DEBRUIJN (TAATGCCATGGGATGTT)
3
Genome → de Bruijn graph
TAATGCCATGGGATGTT

CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG
 k-mers → Genome
TAATGCCATGGGATGTT

CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 k-mers → de Bruijn → Genome
TAATGCCATGGGATGTT

CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

AAT TGC CCA ATG GGG GAT TGT

 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

AAT TGC CCA ATG GGG GAT TGT

 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

AAT TGC CCA ATG GGG GAT TGT

 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

AAT TGC CCA ATG GGG GAT TGT

AA AT TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

AAT TGC CCA ATG GGG GAT TGT

AA AT TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

AA AAT TGC CCA ATG GGG GAT TGT

AT TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

AAT
TGC CCA ATG GGG GAT TGT
AT TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

AAT
TGC CCA ATG GGG GAT TGT
AT TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA AAT ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

TGC CCA ATG GGG GAT TGT

TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA AAT ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

TGC CCA ATG GGG GAT TGT

TG GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA AAT ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

TGC
CCA ATG GGG GAT TGT
GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

TAA AAT ATG GCC CAT TGG GGA ATG GTT

TA AA AT TG GC CC CA AT TG GG GG GA AT TG GT TT

TGC
CCA ATG GGG GAT TGT
GC CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

CCA ATG GGG GAT TGT

CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

CCA ATG GGG GAT TGT

CC CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

CCA
ATG GGG GAT TGT
CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

CCA
ATG GGG GAT TGT
CA AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

ATG GGG GAT TGT

AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

ATG GGG GAT TGT

AT TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

ATG
GGG GAT TGT
TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

ATG
GGG GAT TGT
TG GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GGG GAT TGT

GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GGG GAT TGT

GG GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GGG
GAT TGT
GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GGG
GAT TGT
GG GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GAT TGT
GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GAT TGT
GA AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GAT
TGT
AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

GAT
TGT
AT TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

TGT
TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

TGT
TG GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

TGT

GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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

TGT

GT
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

We are not done gluing yet!

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
 k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)

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
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

CAT TGC

AT ATG TG

TGG GGG GGA GAT ATG TGT GTT

TAA AAT
TA AA AT ATG TG GG GG GA AT TG GT TT
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

CAT TGC

AT ATG TG

TGG GGG GGA GAT ATG TGT GTT

TAA AAT
TA AA AT ATG TG GG GG GA AT TG GT TT
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC CC

CCA CCA GCC GCC

CA CA GC GC

CAT CAT TGC TGC

AT AT ATG ATG
TG TG

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

AT AT TG TG
ATG ATG
GAT GAT TGG TGG

GA GA GG GG

GGA GGA GGG GGG

GG GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

GC
CA
TGC
CAT
ATG TG

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

GAT ATG TG
TGG
GA
GG
GGA
GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

GCC
CCA
GC
CA
TGC
ATG TG
CAT

TAA AAT ATG TG TGT GT GTT TT

TA AA AT

GAT
ATG TG

GA TGG

GG
GGA
GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

GCC
CCA
GC
CA
TGC
ATG TG
CAT

TAA AAT ATG TG TGT GT GTT TT

TA AA AT

GAT
ATG TG

GA TGG

GG
GGA
GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

GCC
CCA
GC
CA
TGC

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

GGA GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG

GGA GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG

GGA GGG

GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG
GG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GG GGG
GGA
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG
k-mers → de Bruijn
COMPOSITION3(TAATGCCATGGGATGTT)
CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

DEBRUIJN3(COMPOSITION3(TAATGCCATGGGATGTT))
 k-mers → de Bruijn
DEBRUIJN

DEBRUIJN(k-mers)
for each k-mer from k-mers
represent k-mer as edge between PREFIX(k-mer) and SUFFIX(k-mer)
glue ALL nodes with identical labels
DEBRUIJN

DEBRUIJN(k-mers)
form a node for each (k-1)-mer from k-mers
for each k-mer from k-mers
connect PREFIX(k-mer) with SUFFIX(k-mer) by an edge
 Universal string problem
000 001 010 011 100 101 110 111

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

0 0

1 0

0 1

1 1

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111
00 00 00 01 01 10 01 11 10 00 00 00 11 10 11 11

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111
00 00 00 01 01 10 01 11 10 00 00 00 11 10 11 11

000
001
00 01

010
100 011
101

10 11
110 111

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem
000 001 010 011 100 101 110 111
00 00 00 01 01 10 01 11 10 00 00 00 11 10 11 11

000
001 0 0
00 01
1 0
010
100 011
101
0 1
10 11
110 1 1
111

problem description
 find a k-universal circular string: a circular string
containing each binary k-mer exactly once
 input: an integer k
 output: a k-universal circular string
de Bruijn (1946)
 Universal string problem

0011
001 011

0001 0010 1011 0111

0101

1001 0000
Does this graph
000 010
have an Eulerian
101
cycle?
111 1111 0110
If yes, then how can we find it?
1010
1000 0100 1101 1110

100 110
1100
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Eulerian cycle problem

problem description
 find an Eulerian cycle in a graph
 input: a graph
 output: a cycle visiting every edge in the graph exactly
once
Eulerian cycle problem

problem description
 find an Eulerian cycle in a graph
 input: a graph
 output: a cycle visiting every edge in the graph exactly
once
Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem
1 in, 2 out

Is this graph Eulerian?

A graph is Eulerian if it contains an Eulerian cycle.

Eulerian cycle problem
1 in, 2 out

A graph is balanced if INGEDREE(n) = OUTDEGREE(n) for each

node n.

A graph is Eulerian if it contains an Eulerian cycle.

 Eulerian cycle problem

0011
Is this graph 001 011

balanced?

0001 0010 1011 0111

0101

1001 0000 000 010 101 111 1111 0110

1010
1000 0100 1101 1110

100 110
1100
Every Eulerian graph is balanced.
 Euler's theorem

0011
Is this graph 001 011

balanced?

0001 0010 1011 0111

0101

1001 0000 000 010 101 111 1111 0110

1010
Every 1000
balanced* graph
0100 is Eulerian. 1101 1110

* and strongly connected, of course!

100 110
1100
Every Eulerian graph is balanced.
Euler's theorem

Every balanced* graph is Eulerian.

* and strongly connected, of course!
Euler's theorem

Every balanced* graph is Eulerian.

* and strongly connected, of course!
Euler's theorem

Let's recruit an ant that randomly walks through the graph. The
ant cannot use the same edge twice!
 Euler's theorem

Can the ant get stuck?

If yes, in what nodes?

The constructed cycle is not Eulerian. Can we extend it?

Euler's theorem

3 1

 start at a node in the constructed cycle with unexplored edges

 traverse already constructed (green) cycle and return back to
starting node
 random exploration of unexplored edges in the graph
Euler's theorem

8
7

1
3
6
4 2

 start at a node in the constructed cycle with unexplored edges

 traverse already constructed (green-blue) cycle and return back
to starting node
 random exploration of unexplored edges in the graph
Euler's theorem
9

8
10
7
11
1
EULERIANCYCLE

3
EULERIANCYCLE(BalancedGraph)
form Cycle by randomly 6 walking in BalancedGraph
4 2
(avoiding already visited edges)
while Cycle is not Eulerian
5
select a node newStart in Cycle with unexplored outgoing edges
form Cycle' by
traversing Cycle from newStart
and randomly walking afterwards
Cycle ← Cycle'
return Cycle
 Universal string problem
3
0011
001 011

2 7 9 10
0001 0010 1011 0111
8
EULERIANCYCLE

0101
EULERIANCYCLE(BalancedGraph)
1001 0000 form
000 Cycle by 010 randomly 101 walking in 111
BalancedGraph
1111 0110
6 1 (avoiding already visited edges) 11 4
while Cycle is not Eulerian1010
select
1000
a node newStart
0100
in14
Cycle with unexplored1110
1101
outgoing edges
form
16 Cycle' by15 13 12
traversing Cycle from newStart
and randomly walking afterwards
100 110
Cycle ← Cycle' 1100
return Cycle 5
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
 k-mers → de Bruijn → Genome
TAATGCCATGGGATGTT

CC

CCA GCC

CA GC

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

ATG
GAT TGG

GA GG
GGA GGG

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 Multiple Eulerian paths
TAATGCCATGGGATGTT

CC CC CC

CCA GCC CCA GCC CCA GCC

CA GC CA GC CA GC

CAT TGC CAT TGC CAT TGC

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

ATG ATG ATG

GAT TGG GAT TGG GAT TGG

GA GG GA GG GA GG
GGA GGG GGA GGG GGA GGG

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 Multiple Eulerian paths
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT TAA
TAAT
TAATG
TAATGG
TAATGGG
TAATGGGA
TAATGGGAT
TAATGGGATG
TAATGGGATGC
TAATGGGATGCC
TAATGGGATGCCA
TAATGGGATGCCAT
TAATGGGATGCCATG
TAATGGGATGCCATGT
TAATGGGATGCCATGTT

CC CC

CCA GCC CCA GCC

CA GC CA GC

CAT TGC CAT TGC

ATG ATG
TAA AAT ATG TGT GTT TAA AAT ATG TGT GTT
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

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
 Breaking genome into contigs
TAATGCCATGGGATGTT
TAATGGGATGCCATGTT
CC
TGCCAT
CCA GCC

CA GC

CAT TGC
ATG ATG
TAA AAT ATG TGT GTT
TAAT TA ATG
AA AT TG GT TT TGTT
ATG ATG
GAT TGG

GA GG
GGA GGG
GGGAT GGG TGG
 Paired-end reads
tiple identical copies of genome

randomly cut genomes into

large equally sized fragments
fragments

paird-end
sequencing: generate
read pair two reads from the
ends of each fragment,
200 bp 200 bp separated by a fixed
insert size distance
From k-mers to paired k-mers
genome
…GTAACCCGGTGGAACGGACTCGGGGA…
read1 read2

A paired k-mer is a pair of k-mers at a fixed distance d apart in

Genome, e.g. ACC and ACT are at distance d=11 apart.

Disclaimers
 read1 and read2 are typically sampled from different strands
(→ … ← rather than → … →)
 the distance between pair-end reads is measured with errors
Paired k-mer composition
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT) =
TAA GCC
AAT CCA
ATG CAT
TGC ATG
GCC TGG
CCA GGG
CAT GGA
ATG GAT
TGG ATG
GGG TGT
GGA GTT
We will represent a paired (k,d)-mer as a 2-line expression, e.g.
the paired (3,1)-mer TAA GCC is represented as
TAA
GCC
 String reconstruction problem
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT) =
TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA
GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT
 String reconstruction problem
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT) =
TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA
GCC CCA CAT ATG TGG GGG GGA GAT ATG TGT GTT

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

problem description
 reconstruct a string from its paired k-mer composition
 input: a collection of paired k-mers
 output: a string Genome such that
PairedCOMPOSITIONk,d(Genome) is equal to the given collection
of paired k-mers
 String reconstruction problem

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

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

problem description
 reconstruct a string from its paired k-mer composition
 input: a collection of paired k-mers
 output: a string Genome such that
PairedCOMPOSITIONk,d(Genome) is equal to the given collection
of paired k-mers
 String reconstruction problem

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

How do we label the starting and ending node of an edge?

TAA
TAA TA GCC AA TAA
PAIREDPREFIX(GCC ) GC CC
PAIREDSUFFIX(GCC )
 String reconstruction problem

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

How do we label the starting and ending node of an edge?

TAA
TAA TA GCC AA TAA
PAIREDPREFIX(GCC ) GC CC
PAIREDSUFFIX(GCC )
 String reconstruction problem

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

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

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT
ATG
GAT
TGG GGG GGA
TG ATG GG TGT GG GTT GA
AT TG GT TT
Gluing identically labeled nodes

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT ATG
TGG GGG GGA GAT
TG ATG GG TGT GG GTT GA
AT TG GT TT
Gluing identically labeled nodes

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT TGG ATG
GGG GGA GAT
TG ATG GG TGT GG GTT GA
AT TG GT TT
Gluing identically labeled nodes

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT
Paired de Bruijn graph

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT

PAIREDDEBRUIJN3,1(TAATGCCATGGGATGTT)
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

GCC CAT TGG GGA ATG GTT

AAT TGC CCA ATG GGG

CCA ATG GGG GAT TGT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

AAT TGC CCA ATG GGG

AA CCA AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CC CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

AAT TGC CCA ATG GGG

AA CCA AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CC CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

AAT
AA TGC CCA ATG GGG
CCA
CC AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
AA AAT
CC CCA TGC CCA ATG GGG
AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
AAT
CCA TGC CCA ATG GGG
AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA ATG GCC CAT TGG GGA

TA GCC AA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
AAT
CCA TGC CCA ATG GGG
AT TG ATG GC CC GGG CA AT GAT TG GG TGT GG
CA AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

TGC CCA ATG GGG

TG ATG GC CC GGG CA AT GAT TG GG TGT GG
AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

TGC CCA ATG GGG

TG ATG GC CC GGG CA AT GAT TG GG TGT GG
AT TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
TGC
ATG CCA ATG GGG
GC CC GGG CA AT GAT TG GG TGT GG
TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
TGC
ATG CCA ATG GGG
GC CC GGG CA AT GAT TG GG TGT GG
TG GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

CCA ATG GGG

CC GGG CA AT GAT TG GG TGT GG
GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

CCA ATG GGG

CC GGG CA AT GAT TG GG TGT GG
GG GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
CCA
GGG ATG GGG
CA AT GAT TG GG TGT GG
GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
CCA
GGG ATG GGG
CA AT GAT TG GG TGT GG
GG GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

ATG GGG
AT GAT TG GG TGT GG
GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT

ATG GGG
AT GAT TG GG TGT GG
GA AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
ATG
GAT GGG
TG GG TGT GG
AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT TGG GGA

TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
ATG
GAT GGG
TG GG TGT GG
AT TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

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

GGG
GG TGT GG
TG GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGA
TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT GAT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
GGG
TGT
GG
GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGA
TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT GAT TG ATG GG GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
GGG
TGT
GG
GT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA
TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT GAT TG ATG GG TGT GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

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

We are not done gluing yet!

 Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)

TAA AAT ATG TGC GCC CCA CAT ATG TGG GGG GGA
TA GCC AA CCA AT CAT TG ATG GC TGG CC GGG CA GGA AT GAT TG ATG GG TGT GG GTT GA
GC CC CA AT TG GG GG GA AT TG GT TT
Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)
GCC CCA CAT
TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT
ATG
GAT
TGG GGG GGA
TG ATG GG TGT GG GTT GA
AT TG GT TT
Gluing identically labeled nodes
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)
GCC CCA CAT
TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT ATG
TGG GGG GGA GAT
TG ATG GG TGT GG GTT GA
AT TG GT TT
Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)
GCC CCA CAT
TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG

TA GCC AA CCA AT CAT TG
GC CC CA AT TGG ATG
GGG GGA GAT
TG ATG GG TGT GG GTT GA
AT TG GT TT
Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)
GCC CCA CAT
TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT
Paired k-mers → paired de Bruijn
PAIREDCOMPOSITION3,1(TAATGCCATGGGATGT
T)
GCC CCA CAT
TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT

PAIREDDEBRUIJN3,1(PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT))
 Paired k-mers → paired de Bruijn
PAIREDDEBRUIJN

PAIREDDEBRUIJN(paired-k-mers)
for each pair from paired-k-mers
represent pair as edge between
PAIREDPREFIX(pair) and PAIREDSUFFIX(pair)
glue ALL nodes with identical labels
PAIREDEBRUIJN

PAIREDDEBRUIJN(paired-k-mers)
form a node for each paired (k-1)-mer from paired-k-mers
for each pair from paired-k-mers
connect PAIREDPREFIX(pair) with
PAIREDSUFFIX(pair) by an edge
 Multiple Eulerian paths
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
TAATGCCATGGGAT
TAATGCCATGGGATG
TAATGCCATGGGATGT
TAATGCCATGGGATGTT TAA
TAAT
TAATG
TAATGG
TAATGGG
TAATGGGA
TAATGGGAT
TAATGGGATG
TAATGGGATGC
TAATGGGATGCC
TAATGGGATGCCA
TAATGGGATGCCAT
TAATGGGATGCCATG
TAATGGGATGCCATGT
TAATGGGATGCCATGTT

CC CC

CCA GCC CCA GCC

CA GC CA GC

CAT TGC CAT TGC

ATG ATG
TAA AAT ATG TGT GTT TAA AAT ATG TGT GTT
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

AAT ATG ATG ATG CAT CCA GAT GCC GGA GGG GTT TAA TGC TGG TGT
Unique Eulerian path
TAA
TAAT
TAATG
TAATGC
TAATGCC
TAATGCCA
TAATGCCAT
TAATGCCATG
TAATGCCATGG
TAATGCCATGGG
TAATGCCATGGGA
GCC
GCCA
GCCAT
GCCATG
GCCATGG
GCCATGGG
GCCATGGGA
GCCATGGGAT
GCCATGGGATG
GCCATGGGATGT
GCCATGGGATGTT

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT

PAIREDDEBRUIJN3,1(PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT))
Unique Eulerian path
TAATGCCATGGGAGTT

GCC CCA CAT

TGC GC TGG CC GGG CA GGA AT
ATG TG GG GG GA

TAA AAT ATG TGG GGG GGA

ATG
TA GCC AA CCA AT CAT TG ATG GG TGT GG GTT GA
GAT
GC CC CA AT TG GT TT

PAIREDDEBRUIJN3,1(PAIREDCOMPOSITION3,1(TAATGCCATGGGATGTT))
Outline
 what is genome sequencing?
 exploding newspapers
 the string reconstruction problem
 string reconstruction as a Hamiltonian path problem
 string reconstruction as an Eulerian path problem
 similar problems with different fates
 de Bruijn graphs
 Euler's theorem
 assembling read-pairs
 de Bruijn graphs face harsh realities of assembly
Some unrealistic assumptions
 perfect coverage
(every k-mer from the genome is represented by a read)
 error-free reads
 known multiplicities of k-mers
 fixed distance between paired reads
…
Some unrealistic assumptions
 imperfect coverage
(every k-mer from the genome is represented by a read)
 error-prone reads
 unknown multiplicities of k-mers
 inexact distance between paired reads
…
Imperfect coverage
ATGCCGTATGGACAACGACT
ATGCCGTATG
GCCGTATGGA
GTATGGACAA
GACAACGACT

250-nucleotide reads generated by Illumina technology capture

only a small fraction of the 250-mers from the genome, thus
violating the key assumption of de Bruijn graphs.
Imperfect coverage
ATGCCGTATGGACAACGACT
ATGCC
ATGCCGTATG
TGCCG
GCCGTATGGA
GCCGT
GTATGGACAA
CCGTA GACAACGACT
CGTAT
GTATG
GTATG
TATGG
ATGGA
TGGAC
GGACA
GACAA
GACAA
ACAAC
CAACG
AACGA
ACGAC
CGACT
Error-prone reads
ATGCCGTATGGACAACGACT
ATGCCGTATG
GCCGTATGGA
GTATGGACAA
GACAACGACT
CGTAcGGACA
Error-prone reads
ATGCCGTATGGACAACGACT
ATGCC
TGCCG
GCCGT
CCGTA
CGTAT
GTATG
GTATG
TATGG
ATGGA
TGGAC
GGACA
CGTAc GACAA
GACAA
GTAcG ACAAC
TAcGG CAACG
AcGGA AACGA
cGGAC ACGAC
GGACA CGACT
 Error-prone reads
ATGCCGTATGGACAACGACT
ATGCCGTATG
GCCGTATGGA
GTATGGACAA
GACAACGACT
CGTAcGGACA

ATGCC TGCCG GCCGT CCGTA CGTAT GTATG TATGG ATGGA TGGAC GGACA
ATGC TGCC GCCG CCGT CGTA GTAT TATG ATGG TGGA GGAC GACA

GTAc TAcG AcGG cGGA

CGTAc GTAcG TAcGG AcGGA cGGAC

Bubble!
Error-prone reads
Error-prone reads

De Bruijn graph of the N. meningitidis genome after removing

bubbles. The red edges represent repeats, not bubbles.
Hybrid assembly
Who are these people?

10 scientists and enterpreneurs who made their genomes

available in 2009 for the Personal Genome Project (PGP).
Who are these people?

 personal genome sequencing will soon expand to

millions of individuals
 we have already sequenced tens of thousands of
species, with thousands of individuals for key species
 thousands of cancer genomes have already been
sequenced, and genome sequencing has become a
routine technique in medicine
Questions
The sky is the limit…

"In mathematical terms the final proof

is the equivalent of splitting the atom
or finding the structure of DNA"

 Simon Singh (in Fermat's Last Theorem)