ILP-based maximum likelihood genome scaffolding.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• High-throughput sequencing (HTS) generates short reads, leading to fragmented genome assemblies.
• Scaffolding contigs into larger structures is challenging due to library artifacts and repeat mapping errors.
• Existing methods struggle with scalability and accuracy for large genomes and complex samples.

Purpose of the Study:

• To introduce SILP2, a scalable genome scaffolding algorithm.
• To address challenges in read mapping uncertainty and contig coverage non-uniformity.
• To develop novel metrics for evaluating scaffolding tool performance.

Main Methods:

• Developed SILP2, a scalable scaffolding algorithm utilizing a maximum likelihood model.
• Employed integer linear programming to solve the model, capturing read mapping uncertainty.
• Applied a Non-Serial Dynamic Programming (NSDP) paradigm for processing large mammalian genomes.

Main Results:

• SILP2 demonstrates improved scalability and accuracy compared to OPERA and MIP for human-sized genomes.
• The algorithm significantly outperforms existing methods on low-complexity metagenomic samples.
• SILP2 achieves better scalability through a more efficient NSDP algorithm than its predecessor.

Conclusions:

• SILP2 effectively scaffolds large mammalian genomes, producing the longest and most accurate scaffolds.
• The integer linear programming formulation is flexible for handling metagenomic samples.
• SILP2 represents a significant advancement in scalable and accurate genome scaffolding.