Genome Assembly (coding class)

Genome Assembly (Part I)

AGRO 5431
16 February 2026

Key Definitions

• Contig: A gap-free consensus sequence derived from assembling reads.

• Scaffold: One or more contigs that have been ordered and oriented using paired-end and mate-pair constraints, containing sized gaps that are filled with N’s.

• Super-scaffold: Chromosome scaffolds generated by anchoring individual scaffolds with maps or conserved synteny.

Considerations Before Starting

• Genome Size:

  • Larger genomes require more resources for assembly, including computational power and memory.

• Repetitive Sequences:

  • Frequency, length, and conservation of repeat copies are crucial.

  • More repetitive genomes necessitate longer reads or long-distance mate-pairs to resolve their structure.

  • Assembling repeats longer than the sequence read lengths is particularly challenging.

• AT Content:

  • High imbalances in AT composition can lead to low information content and more frequent spurious sequence similarities, complicating assembly.

• Ploidy:

  • It is easier to assemble a haploid or homozygous diploid individual due to reduced complexity in genetic variation.

• Sequencing Technology:

  • The choice of sequencing technology depends on answers to above questions and the specific goals/needs of the assembly.

• Assembly Software:

  • Software must be compatible with the chosen sequencing technology and consider memory requirements, processing speed, hardware requirements, robustness, and the ease of installation and operation.

• Biological Questions:

  • Understand the biological questions driving the assembly project to guide considerations and choices throughout the process (Referenced: Nagarajan and Pop, NRG 2013).

Genome Assembler

• Definition: A program that constructs a genome assembly from a set of sequencing reads as input.

  • Steps in Assembly:

  1. Pre-process the reads.

  2. Find overlaps between reads.

  3. Generate a graph from these overlaps.

  4. Traverse the graph to generate the assembly sequence.

  • Different assemblers utilize varied algorithms for these steps, but the fundamental sequence of operations remains consistent.

Input Reads Considerations

• The sequence reads for assembly must satisfy three critical properties:

  • Length: Longer reads generally provide better assembly outcomes.

  • Accuracy: Higher accuracy is paramount to avoid errors in the assembly.

  • Evenness of Representation: Consistent representation across the genome aids in more reliable assembly outcomes.

Assemblers for Sanger Reads

• Initial assemblers adopted greedy algorithms and overlap-layout-consensus (OLC) based algorithms for assembly.

  • These tools are well suited for longer reads with low error rates.

• Types of Assemblers:

  • Greedy: Examples include TIGR Assembler, phrap, CAP3.

  • Graph-based OLC: Examples include Celera Assembler, Arachne, Newbler.

Greedy Based Assembly Algorithm

• General Process:

  1. Construct a rough map of fragment overlaps.

  2. Identify the largest scoring overlap among fragments.

  3. Merge the two fragments sharing the overlap.

  4. Repeat the process until no more merges are possible.

Basics of Graphs in Assembly

• Graphs are utilized to systematically represent the data involved in genome assembly.

  • Components of a Graph:

  • Nodes: Represent data points (e.g., sequence reads).

  • Edges: Represent paths connecting nodes (e.g., overlaps).

  • Directed Graphs: These contain edges that have a direction indicating the point of traversal.

• Graph Algorithms: Various algorithms exist to locate specific nodes or paths within the graph, providing essential functionality for genome assembly.

Graph-based OLC Assembly Process

• Overlap: This step computes and builds the basic assembly graph from the sequencing reads.

• Layout: This compresses the graph into contigs up to the points of divergence (forks).

• Consensus: The final genome sequence is determined based on the compressed graph, though gaps may occur when contigs/scaffolds cannot be joined together.

• The OLC approach does not scale well when handling short reads with high coverage due to the requirement for maintaining extensive overlap information in the graph.

• Node and Edge Representation:

  • Nodes represent the reads, while edges represent quality overlaps between these reads.

  • The goal is to find a Hamiltonian path through the graph that visits each node exactly once.

Lander-Waterman Statistics

• Variables Used:

  • $G$: Genome length

  • $n$: Number of sequences

  • $L$: Length of sequences

  • $c$: Coverage $= rac{nL}{G}$

  • $t$: Minimum overlap

  • $au$: $au = rac{(L – t)}{L}$

• Theoretical Expectation:

  • The expected number of contigs can be estimated with $ext{Expected } = ne^{-c au}$.

  • The model tests the feasibility of shotgun sequence assembly based on Poisson statistics, estimating the count of gaps in coverage (i.e., the anticipated number of contiguous DNA segments) derived from a particular set of parameters.

• Example Calculation:

  • Given a 1 Mb genome, with 5,000 reads, and average read length of ~600 bp, the expected coverage can be calculated as 3x.

Challenges in Genome Assembly

• Genome assembly with short reads presents significant computational challenges:

  • Numerous short reads must be processed for overlapping.

  • Coverage is high but can also be uneven, contributing to fragmentation as reads can be shorter than the majority of repeat sequences present in the genome.

Assemblers for Short NGS Reads

• De Bruijn Graphs:

  • Concept originally developed by de Bruijn in the 1940s.

  • First applied in genome assembly by Pevzner in 1989.

• Functionality of De Bruijn Graphs:

  • Reads are hashed into k-mers, which form the basis of a de Bruijn graph constructed in memory.

  • The graph can be efficiently traversed to yield a consensus (visiting each edge exactly once).

  • This methodology eliminates the necessity to store pairwise overlapping information for reads, which enhances scalability.

Understanding k-mers

• Definition: A k-mer is defined as any substring of length ‘k’ derived from a longer sequence.

  • Example for 3-mers derived from the sequence ATCGATAGC: ATC, TCG, CGA, GAT, ATA, TAG, AGC.

• Assemblers Limitation:

  • Assemblers generally avoid even k-values to prevent many k-mers from becoming reverse complements of their own sequences, which can create ambiguities related to the strand-specific nature of the assembly graph.

• Insights from K-mer Analysis:

  • K-mer analysis can also yield crucial insights related to error rate, coverage, repeat content, duplication, and sequence complexity.

Complexities in De Bruijn Graphs

• Repetitive Sequences:

  • Graphs can become complex due to SNPs, read errors, and repetitive elements.

  • To resolve these complexities, advanced error correction algorithms can be applied, along with the use of long reads, paired-end reads, and mate pairs.

Long Read Assemblies

• Most long read assemblers utilize variations of the OLC approach, with some newer types employing de Bruijn graphs.

  • These assemblers specifically target low-error rate reads (e.g., HiFi, ONT duplex reads).

  • Larger k-mer sizes should be utilized with long reads, ideally k being larger than the size of the repeats to ensure effective representation in the graph.

• Historical Context: All mainstream assemblers are fundamentally built upon basic assembly algorithms established since the mid-1990s.

Assembly Quality Across Sequencing Technologies

• Contiguity Measurement:

  • A larger N50 value signifies higher contiguity of an assembly, which will be explored in detail in future classes (Referenced: Belser et al., Nature Plants, 2018).

Challenges to T2T Assembly

• Structural Recalcitrant Sequences, such as repeats, complicate the assembly process further, encompassing:

  • Structural variations and sequence variations.

Workflow for High-Quality Assemblies

• General Steps:

  1. Raw Accurate Long Reads: Initiate assembly with high-fidelity long reads.

  2. Error Correction: Apply correction algorithms to refine raw reads.

  3. Initial Assembly: Construct the assembly graph based on corrected reads.

  4. Tangle Resolution: Resolve tangles in the initial assembly graph.

  5. Gap Patching: Patch any short gaps in between contiguous sequences with ultra-long reads.

  6. Final Assembly Refinement: Create the ultra-long assembly graph and incorporate long-range data to finalize the assembly.

  (Referenced: Li and Durbin, NRG, 2024).

Common Data Types for High-Quality Assemblies

• A variety of data types are utilized in the assembly process to achieve high quality.

  • Note: Not all data types are necessary to generate an assembly focused solely on the gene space (Referenced: Li and Durbin, NRG, 2024).

High-throughput Chromosome Conformation Capture (Hi-C)

• Overview: This chromatin conformation capture technique is employed to create chromatin interaction maps and provides valuable long-range data.

  • Interaction density tends to be higher among sequences that are closer together on the same haploid chromosome, making it especially beneficial for phasing polyploid genomes.

Optical Mapping

• Definition: Optical mapping involves the generation of ordered, genome-wide, high-resolution restriction maps.

  • It utilizes single, stained molecules of DNA to elucidate the architecture of the genome.

  • This method provides dense genome-wide anchor points for the ordering and orientation of sequencing contigs or scaffolds.

BioNano Genomics

• Methodology: The nicking endonuclease creates single-strand cuts, and fluorescently labeled nucleotides are incorporated during repair.

  • Practical Note: BioNano maps are becoming less utilized as ultra-long reads come into play, as they can often provide longer sequences that can resolve repeats more efficiently.

Comparing Different Assemblers

• Hybrid vs. Non-hybrid Assemblies:

  • A breakdown of two categories:

  • Hybrid Assembly Technologies: Combine different sequencing techniques (e.g., Illumina with ONT).

  • Non-hybrid Assemblies: Use a single technology stream (e.g., ONT or HIFI alone).

• Assemblers Used: Examples include Hifiasm, Shasta, Wengan, HiCanu, and Miniasm, among others, all of which utilize different combinations of data and sequencing technologies (Referenced: Espinosa et al., Genomics, 2023).

Heterozygosity and Ploidy

• Ploidy Levels:

  • Diploid individuals contain two copies of each chromosome, which are similar yet not identical.

  • Polyploid organisms hold even more copies of chromosomes, presenting ongoing challenges in genome assembly.

  • Phased assemblies are being developed to handle these complexities in assembly processes, particularly in distinguishing between alleles.

Genome Assembly Contamination

• Sources of Contamination:

  • Sample contamination can introduce foreign DNA into processed samples.

  • Common errors during processing and handling data can lead to further contamination.

• Specific Example: The AluY repeat is a primate-specific repeat that represents abundant human DNA contamination identifiable in non-primate genome databases (Referenced: Longo et al., PLoSOne 2011).

• Continued Challenges: Contaminant identification and control are ongoing challenges within assembly projects, especially in non-target genomes.

Key Takeaways on Genome Assembly

• Genome assemblies reflect the best representation of original chromosomes from which sequencing reads were derived.

• Understanding the biological context and limitations of a genome assembly is critical before initiating projects.

• Assembling repetitive sequences is complex and often requires longer reads than the repeat lengths themselves.

• The overlap and de Bruijn graph methods stand as the most commonly employed strategies in genome assembly.

• Heterozygosity and polyploidy contribute significantly to assembly challenges, often necessitating additional data for accurate phasing of haplotypes.