2.6 Genome scaffolding and gap filling

Genome scaffolding and gap filling are crucial steps in reconstructing complete genome sequences. These processes involve ordering and orienting contigs into larger structures called scaffolds, and then attempting to close the gaps between them.

These techniques help overcome challenges like repetitive sequences, sequencing errors, and incomplete coverage. By using various data sources and algorithms, researchers can improve the accuracy and completeness of genome assemblies, enabling better downstream analyses and insights into genetic information.

Genome assembly challenges

• Genome assembly is the process of reconstructing a complete genome sequence from shorter DNA fragments, which presents several challenges due to the complexity and size of genomes
• These challenges can lead to fragmented assemblies, misassemblies, and gaps in the reconstructed genome sequence, affecting the accuracy and completeness of the assembly

Repetitive sequences

Top images from around the web for Repetitive sequences

• 

  Frontiers | Different Modes of Gene Duplication Show Divergent Evolutionary Patterns and ... View original

  Is this image relevant?

• 

  Frontiers | An Improved Melon Reference Genome With Single-Molecule Sequencing Uncovers a Recent ... View original

  Is this image relevant?

• 

  Frontiers | Different Modes of Gene Duplication Show Divergent Evolutionary Patterns and ... View original

  Is this image relevant?

• 

  Frontiers | An Improved Melon Reference Genome With Single-Molecule Sequencing Uncovers a Recent ... View original

  Is this image relevant?

1 of 2

Top images from around the web for Repetitive sequences

• 

  Frontiers | Different Modes of Gene Duplication Show Divergent Evolutionary Patterns and ... View original

  Is this image relevant?

• 

  Frontiers | An Improved Melon Reference Genome With Single-Molecule Sequencing Uncovers a Recent ... View original

  Is this image relevant?

• 

  Frontiers | Different Modes of Gene Duplication Show Divergent Evolutionary Patterns and ... View original

  Is this image relevant?

• 

  Frontiers | An Improved Melon Reference Genome With Single-Molecule Sequencing Uncovers a Recent ... View original

  Is this image relevant?

1 of 2

• Repetitive sequences, such as transposable elements, satellite DNA, and segmental duplications, are abundant in many genomes and can span hundreds to thousands of base pairs
• These sequences can cause ambiguities during assembly, as the shorter sequencing reads may not be long enough to span the entire repetitive region, making it difficult to determine their correct placement
• Repetitive sequences can lead to collapsed repeats in the assembly, where multiple copies of the repeat are represented as a single copy, or expanded repeats, where the number of copies is overestimated

Sequencing errors

• Sequencing technologies are not perfect and can introduce errors in the DNA sequence, such as substitutions, insertions, or deletions of nucleotides
• These errors can create false overlaps between sequencing reads, leading to misassemblies or fragmented contigs
• Sequencing errors can also introduce false variations in the assembled genome, which can be mistaken for true biological variations, such as single nucleotide polymorphisms (SNPs) or structural variations

Incomplete coverage

• Sequencing coverage refers to the average number of times each base in the genome is represented in the sequencing reads
• Incomplete coverage can occur due to biases in the sequencing process, such as GC content bias or uneven amplification, leading to regions of the genome with low or no coverage
• Insufficient coverage can result in gaps in the assembled genome sequence, as there may not be enough overlapping reads to bridge certain regions, especially those with repetitive or complex sequences

Scaffolding

• Scaffolding is the process of ordering and orienting contigs (contiguous sequences) into larger structures called scaffolds, which represent the relative positions and orientations of the contigs in the genome
• Scaffolding aims to bridge gaps between contigs and provide a more complete and accurate representation of the genome structure

Scaffold graph construction

• Scaffold graph construction involves creating a graph representation of the contigs and their connections based on additional information, such as mate-pair or paired-end reads
• In a scaffold graph, nodes represent contigs, and edges represent the connections between contigs based on the linking information
• The graph structure allows for the identification of the most likely order and orientation of contigs, considering the constraints imposed by the linking data

Mate-pair reads

• Mate-pair reads are sequencing reads generated from DNA fragments with a larger insert size (2-5 kb or more) compared to standard paired-end reads
• These reads span larger distances in the genome and can provide long-range connectivity information for scaffolding
• Mate-pair reads can help bridge gaps between contigs and resolve repetitive regions, as they can span these problematic areas and provide linking information

Paired-end reads

• Paired-end reads are sequencing reads generated from both ends of DNA fragments with a known orientation and approximate distance between them
• The distance between paired-end reads is typically shorter than mate-pair reads (200-500 bp) but can still provide valuable linking information for scaffolding
• Paired-end reads can help orient contigs and estimate the size of gaps between them based on the expected insert size of the library

Long-read technologies

• Long-read sequencing technologies, such as Pacific Biosciences (PacBio) and Oxford Nanopore Technologies (ONT), generate reads that can span several kilobases to hundreds of kilobases in length
• These longer reads can directly span repetitive regions and provide continuous sequence information, facilitating the assembly of complex genomes
• Long reads can be used for scaffolding by directly connecting contigs or by providing a backbone for hybrid assembly approaches that combine long and short reads

Gap filling

• Gap filling is the process of attempting to close the gaps between contigs in a scaffold by generating or identifying sequences that can fill these gaps
• Gap filling aims to improve the continuity and completeness of the genome assembly by reducing the number and size of gaps

Gap identification

• Gap identification involves locating the gaps between contigs in a scaffold based on the available linking information and the expected distance between contigs
• Gaps can be identified by analyzing the scaffold graph and identifying regions where there are no connecting edges between contigs or where the distance between contigs exceeds the expected insert size of the linking reads
• The size and location of gaps can be estimated based on the linking information and the size of the contigs flanking the gap

Local assembly methods

• Local assembly methods aim to fill gaps by performing a targeted assembly of the reads that map to the regions flanking the gap
• These methods extract the reads that align to the contigs on either side of the gap and attempt to assemble them into a contiguous sequence that spans the gap
• Local assembly can be performed using short reads, mate-pair reads, or a combination of both, depending on the available data and the size of the gap

Reference-based approaches

• Reference-based gap filling approaches utilize a closely related reference genome to guide the gap filling process
• These methods align the contigs flanking the gap to the reference genome and attempt to identify the corresponding sequence in the reference that can fill the gap
• Reference-based approaches can be effective when a high-quality reference genome is available for a closely related species, but they may not capture species-specific variations or novel sequences

De novo gap filling

• De novo gap filling methods attempt to fill gaps without relying on a reference genome, using only the sequencing reads and the assembly information
• These approaches often involve iterative rounds of local assembly, where the reads mapping to the gap region are assembled, and the resulting contigs are incorporated back into the assembly
• De novo gap filling can be computationally intensive and may require multiple iterations to close larger gaps or resolve complex regions

Scaffolding algorithms

• Scaffolding algorithms are computational methods designed to order and orient contigs into scaffolds based on linking information from paired-end reads, mate-pair reads, or other sources of long-range connectivity
• These algorithms aim to find the most likely arrangement of contigs that satisfies the constraints imposed by the linking data while minimizing conflicts and inconsistencies

Greedy algorithms

• Greedy scaffolding algorithms make locally optimal decisions at each step, iteratively joining contigs into scaffolds based on the strongest linking evidence
• These algorithms typically start with the longest contigs and progressively add shorter contigs to the scaffolds, prioritizing the links with the highest support or consistency
• Examples of greedy scaffolding algorithms include SSPACE, SOPRA, and GRASS

Graph-based algorithms

• Graph-based scaffolding algorithms represent the contigs and their connections as a graph, where nodes represent contigs and edges represent the linking information
• These algorithms often use advanced graph theory concepts, such as minimum spanning trees, maximum likelihood paths, or network flow optimization, to find the most likely arrangement of contigs
• Graph-based algorithms can handle complex linking patterns and can be more robust to errors and inconsistencies in the data compared to greedy approaches
• Examples of graph-based scaffolding algorithms include BESST, ScaffMatch, and Opera

Hybrid approaches

• Hybrid scaffolding approaches combine multiple sources of information or different algorithmic strategies to improve the accuracy and completeness of the scaffolding process
• These approaches may integrate data from different sequencing technologies (e.g., short reads and long reads), use a combination of greedy and graph-based methods, or incorporate additional information such as physical maps or genetic linkage data
• Hybrid approaches aim to leverage the strengths of different data types and algorithms to overcome the limitations of individual methods and produce high-quality scaffolds
• Examples of hybrid scaffolding approaches include RAILS, LINKS, and SALSA

Gap filling algorithms

• Gap filling algorithms are computational methods designed to close the gaps between contigs in a scaffold by generating or identifying sequences that can span these gaps
• These algorithms utilize various strategies, such as local assembly, reference-based approaches, or de novo methods, to generate gap-filling sequences

GapCloser

• GapCloser is a gap filling tool that is part of the SOAPdenovo package, which is commonly used for de novo genome assembly
• It uses a local assembly approach to fill gaps by extracting reads that map to the contigs flanking the gap and performing a targeted assembly of these reads
• GapCloser iteratively extends the contigs into the gap region using a k-mer-based approach, attempting to find overlaps between the reads and the contig ends

GapFiller

• GapFiller is a standalone gap filling tool that uses a hybrid approach combining local assembly and reference-based methods
• It first aligns the contigs flanking the gap to a reference genome (if available) to identify potential gap-filling sequences
• If no suitable reference-based sequence is found, GapFiller performs a local assembly of the reads mapping to the gap region using a seed-and-extend approach

GMcloser

• GMcloser is a gap filling tool that uses a reference-based approach to close gaps in a draft genome assembly
• It aligns the contigs flanking the gap to a closely related reference genome and extracts the corresponding sequence from the reference to fill the gap
• GMcloser can handle multiple reference genomes and can fill gaps using a consensus sequence derived from multiple alignments

TGS-GapCloser

• TGS-GapCloser is a gap filling tool designed to close gaps using long reads generated by third-generation sequencing (TGS) technologies, such as PacBio or Oxford Nanopore
• It utilizes the long reads to directly span the gaps between contigs, providing a continuous sequence that can close the gap
• TGS-GapCloser can handle errors and variations in the long reads by performing a local alignment and consensus calling step to refine the gap-filling sequence

Quality assessment

• Quality assessment is the process of evaluating the accuracy, completeness, and contiguity of a genome assembly, including the scaffolds and gap-filled sequences
• Various metrics and approaches are used to assess the quality of an assembly and identify potential issues or areas for improvement

Scaffold N50 metric

• The scaffold N50 is a commonly used metric to assess the contiguity of a genome assembly at the scaffold level
• It represents the length of the scaffold at which 50% of the total assembly length is contained in scaffolds of that size or larger
• A higher scaffold N50 value indicates a more contiguous assembly, with fewer and larger scaffolds

Gap statistics

• Gap statistics provide information about the number, size, and distribution of gaps in the scaffolded assembly
• These statistics can include the total number of gaps, the average and median gap size, and the gap size distribution
• Lower gap statistics (fewer and smaller gaps) generally indicate a more complete and contiguous assembly

Misassembly detection

• Misassembly detection involves identifying regions in the assembly where the order or orientation of contigs is incorrect or where there are chimeric joins between unrelated sequences
• Misassemblies can be detected using various approaches, such as comparing the assembly to a reference genome, analyzing read coverage and consistency, or using long-range information from mate-pair or long reads
• Tools like QUAST, REAPR, and FRCbam can be used to detect and quantify misassemblies in an assembly

Completeness evaluation

• Completeness evaluation assesses the extent to which the assembly captures the full content of the genome, including genes, regulatory elements, and other biologically relevant features
• Completeness can be evaluated using benchmarking sets of conserved genes, such as single-copy orthologs, or by comparing the assembly to a closely related reference genome
• Tools like BUSCO and CEGMA can be used to assess the completeness of an assembly based on the presence and completeness of conserved gene sets

Challenges and limitations

• Despite advances in scaffolding and gap filling methods, there are still several challenges and limitations that can affect the quality and completeness of genome assemblies

Chimeric sequences

• Chimeric sequences are artificial joins between unrelated sequences that can occur during the assembly process, particularly in regions with repetitive or complex sequences
• Chimeric sequences can lead to misassemblies and incorrect representations of the genome structure
• Identifying and resolving chimeric sequences can be challenging, as they may not be easily distinguishable from true biological variations or rearrangements

Misassemblies

• Misassemblies are regions in the assembly where the order or orientation of contigs is incorrect, leading to a misrepresentation of the true genome structure
• Misassemblies can arise from various sources, such as chimeric sequences, incorrect linking information, or errors in the assembly algorithms
• Detecting and correcting misassemblies can be difficult, particularly in the absence of a high-quality reference genome or long-range connectivity information

Unresolved gaps

• Despite the application of gap filling methods, some gaps in the assembly may remain unresolved due to various factors, such as repetitive sequences, low coverage regions, or limitations of the available data and algorithms
• Unresolved gaps can affect the continuity and completeness of the assembly and may hinder downstream analyses, such as gene annotation or comparative genomics
• Closing all gaps in a genome assembly may not always be possible, particularly for large and complex genomes with extensive repetitive content

Computational complexity

• Scaffolding and gap filling algorithms can be computationally intensive, particularly for large and complex genomes with high levels of repetitive sequences or heterozygosity
• The computational complexity of these methods can increase with the size of the genome, the amount of sequencing data, and the complexity of the linking information
• Scaling these algorithms to handle large datasets or multiple genomes can be challenging and may require significant computational resources and optimization efforts

Advances in scaffolding and gap filling

• Recent advances in sequencing technologies, computational methods, and data integration approaches have led to improvements in scaffolding and gap filling strategies, enabling the generation of more complete and accurate genome assemblies

Optical mapping

• Optical mapping is a technique that generates high-resolution physical maps of genomes by imaging and analyzing long, fluorescently labeled DNA molecules
• These physical maps provide long-range connectivity information that can be used for scaffolding and validating the assembly
• Optical mapping data can help resolve complex regions, identify misassemblies, and anchor scaffolds to chromosomes

Chromosome conformation capture

• Chromosome conformation capture (3C) techniques, such as Hi-C and Dovetail, capture the spatial proximity of DNA sequences in the nucleus, providing long-range connectivity information for scaffolding
• These methods generate contact frequency maps that reflect the three-dimensional organization of the genome, allowing for the ordering and orientation of scaffolds into chromosome-scale assemblies
• Hi-C and Dovetail data can help resolve complex regions, identify misassemblies, and provide a framework for genome-wide scaffolding

Single-molecule sequencing

• Single-molecule sequencing technologies, such as PacBio and Oxford Nanopore, generate long reads that can span tens to hundreds of kilobases, providing continuous sequence information for scaffolding and gap filling
• These long reads can directly resolve repetitive regions and complex structures, reducing the need for complex computational methods to infer the genome structure
• Single-molecule sequencing data can be used for hybrid assembly approaches, where long reads are combined with short reads to generate high-quality, contiguous assemblies

Artificial intelligence approaches

• Artificial intelligence (AI) and machine learning (ML) approaches are being increasingly applied to genome assembly, scaffolding, and gap filling problems
• These methods can learn patterns and features from large datasets, such as sequencing reads or assembly graphs, to make predictions and guide the assembly process
• AI and ML approaches can be used for tasks such as error correction, repeat resolution, scaffolding, and gap filling, potentially improving the accuracy and efficiency of these processes
• Examples of AI-based tools for genome assembly include LINKS, which uses long read information for scaffolding, and DeepVariant, which uses deep learning for variant calling and assembly polishing