Module 3

Genome Assembly & Comparative Genomics

Assembly reconstructs a genome from shotgun reads using overlap-layout-consensus (for long reads) or de Bruijn graphs (for short reads). Long-read sequencing (ONT, PacBio HiFi) has transformed assembly quality. Comparative genomics then aligns assembled genomes to reveal synteny and rearrangements.

1. De Bruijn Graphs

A de Bruijn graph on k-mers: for each (k−1)-mer X and (k−1)-mer Y that overlap in the middle, draw an edge X → Y labelled by their joined k-mer. Assembly becomes finding an Eulerian path.

\[ \text{Nodes}: (k-1)\text{-mers}\quad \text{Edges}: k\text{-mers},\ X \to Y\ \text{if}\ X[1:] = Y[:-1] \]

Short-read assemblers (SPAdes, ABySS, Velvet) build de Bruijn graphs, collapse bubbles from sequencing errors, resolve repeats with paired-end information, and emit contigs. Pevzner 2001 demonstrated the approach; modern variants use succinct graph representations for human-scale assemblies.

2. Long-Read Assembly (OLC)

Long reads (ONT 10–100 kb, PacBio HiFi 15–25 kb with 99%+ accuracy) favour overlap-layout-consensus: pairwise align all reads, build an overlap graph, then consensus each path. Flye, Canu, hifiasm, and Verkko are current tools. Near-telomere-to-telomere human assemblies (T2T, Nurk 2022 Science) now span each chromosome end-to-end — closing the ~8% of the genome that short-read assembly had left unresolved.

Simulation: De Bruijn Graph

Python

script.py38 lines

import numpy as np, matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import matplotlib.patches as mp

# De Bruijn graph: split reads into k-mers; edges connect overlapping k-mers
reads = ['ATGGCGT', 'GGCGTGC', 'CGTGCAT']
k = 4
nodes = set()
edges = []
for r in reads:
    for i in range(len(r) - k + 1):
        kmer = r[i:i+k]
        a, b = kmer[:-1], kmer[1:]
        nodes.add(a); nodes.add(b)
        edges.append((a, b))
nodes = sorted(nodes)

# Circular layout
n = len(nodes)
angles = np.linspace(0, 2*np.pi, n, endpoint=False)
pos = {nd: (np.cos(a), np.sin(a)) for nd, a in zip(nodes, angles)}

fig, ax = plt.subplots(figsize=(8, 8), facecolor='#0a0a1a')
ax.set_facecolor('#111827'); ax.axis('off')
for a, b in edges:
    xa, ya = pos[a]; xb, yb = pos[b]
    ax.annotate('', xy=(xb, yb), xytext=(xa, ya),
                arrowprops=dict(arrowstyle='->', color='#2dd4bf', lw=1.5, alpha=0.7))
for nd, (x, y) in pos.items():
    ax.plot(x, y, 'o', color='#fbbf24', markersize=28, markeredgecolor='#5eead4')
    ax.text(x, y, nd, ha='center', va='center', color='#0a0a1a', fontsize=9, fontweight='bold')
ax.set_title(f'De Bruijn graph, k-1={k-1}',
             color='#5eead4', fontweight='bold')
plt.tight_layout()
plt.savefig('output.png', dpi=120, bbox_inches='tight', facecolor='#0a0a1a')
print('Assembly = finding an Eulerian path in the de Bruijn graph')
print('SPAdes, ABySS, Velvet all implement variants with bubble/tip removal')

Click Run to execute the Python code

Code will be executed with Python 3 on the server

3. Assembly Quality & N50

N50 is the contig length such that 50% of the assembly resides in contigs of that length or longer. Higher N50 — larger contigs — is better. BUSCO scores assess completeness by checking for expected single-copy orthologs. Both metrics together define assembly quality for a given genome.

4. Comparative Genomics

Once assembled, genomes are compared with whole-genome aligners: MUMmer (exact- match-based), LAST, minimap2. Synteny blocks reveal conserved gene orders; rearrangement breakpoints mark genome evolution events. Tools like Mauve, progressiveCactus, and SynTracker integrate whole-clade alignment. Pan-genome construction adds presence/absence variation to the reference picture.

Key References

• Pevzner, P. A. et al. (2001). “An Eulerian path approach to DNA fragment assembly.” Proc. Natl. Acad. Sci., 98, 9748–9753.

• Bankevich, A. et al. (2012). “SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing.” J. Comput. Biol., 19, 455–477.

• Nurk, S. et al. (2022). “The complete sequence of a human genome.” Science, 376, 44–53.

• Marcais, G. & Kingsford, C. (2011). “A fast, lock-free approach for efficient parallel counting of k-mers.” Bioinformatics, 27, 764–770.

Share:X Reddit LinkedIn

← Module 2 Module 4: Transcriptomics →