MeDuSa

MeDuSa performs genome scaffolding by ordering and orienting contigs using information from multiple related draft or closed genomes to improve de novo assembly accuracy.

Key Features:

• Multi-Draft Utilization: Uses multiple related genomes (draft or closed) as references to inform contig order and orientation.
• Combinatorial Optimization Approach: Formalizes scaffolding as a combinatorial optimization problem on graphs to represent contig relationships.
• Constant Factor Approximation Algorithm: Solves the graph-based optimization using a constant-factor approximation algorithm to produce efficient approximate solutions.
• No Requirement for Prior Knowledge or Paired End Reads: Operates without requiring prior phylogenetic knowledge of the dataset or paired end read libraries.
• High Accuracy and Performance: Benchmarks on real bacterial datasets demonstrate high scaffolding accuracy and competitive performance relative to traditional scaffolders.
• Versatility Across Organisms: Primarily tested on bacterial genomes and evaluated on eukaryotic datasets, indicating potential applicability across prokaryotic and eukaryotic assemblies.

Scientific Applications:

• Genome finishing: Improves contig ordering and orientation within genome finishing pipelines for de novo assemblies.
• Comparative, functional, and structural genomics: Produces scaffolded assemblies that facilitate comparative and evolutionary analyses as well as functional and structural studies.
• Sequencing projects without paired-end data: Enhances assembly contiguity in sequencing workflows where paired end read libraries are unavailable.

Methodology:

Constructs a graph-based combinatorial optimization formulation using multiple draft or closed reference genomes and applies a constant-factor approximation algorithm to determine contig order and orientation, without requiring paired-end reads or prior phylogenetic knowledge.