ScaffoldScaffolder

ScaffoldScaffolder scaffolds diploid genomes by identifying and classifying homologous contigs within scaffold graphs to reconstruct haplotype-specific scaffolds.

Key Features:

• Identification of Homologous Sequences: Identifies homologous sequences within "bubble" structures in scaffold graphs that indicate heterozygous regions in diploid assemblies.
• Machine Learning Classification: Applies machine learning to classify sequences within partial bubbles as homologous or non-homologous to support haplotype-specific scaffold reconstruction.
• Novel Metrics for Accuracy Assessment: Introduces four metrics—contig sequencing depth, contig homogeneity, phase group homogeneity, and heterogeneity between phase groups—for evaluating diploid scaffolding accuracy.
• Homolotigs Identification: Defines "homolotigs" (heterozygous homologous contigs) and trains models on homolotig pairs to identify homologous sequences across datasets, assuming error-free reads.
• Addressing Contig Orientation Problems: Formalizes the contig orientation challenge as the MAX-DIR problem, provides a linear-time reduction from the NP-complete MAX-CUT problem to MAX-DIR, and employs a greedy heuristic that outperforms other heuristics on scaffold graphs.
• Detection of Inverted Repeats: Implements a method to detect inverted repeats and inversion variants relevant to genetic mechanisms and disease.

Scientific Applications:

• Diploid genome assembly: Reconstructs haplotype-specific scaffolds in diploid genome assembly projects.
• Genetic diversity studies: Enables analysis of heterozygosity and homologous variation in population and diversity studies.
• Disease genetics: Supports detection of inversion variants and inverted repeats implicated in disease genetics.
• Evolutionary biology: Facilitates comparative and evolutionary analyses requiring accurate phasing and haplotype resolution.

Methodology:

Performs graph-based analysis of scaffold graphs and bubble structures, applies machine learning classification trained on homolotig pairs, computes the four scaffold accuracy metrics, uses a linear-time reduction from MAX-CUT to MAX-DIR and a greedy heuristic for contig orientation, and applies a method for detecting inverted repeats and inversion variants.