MIP Scaffolder

MIP Scaffolder applies mixed integer programming to scaffold contigs from short-read sequencing data to produce high-quality assemblies of large genomes.

Key Features:

• Mixed Integer Programming (MIP): Applies mixed integer programming to the scaffolding problem and divides the task into smaller subproblems to manage computational complexity.
• Graph Representation: Represents contigs and their linking information as a graph and identifies biconnected components to solve subproblems independently.
• Subproblem Size Restriction: Restricts the size of subproblems to ensure they are solvable by mixed integer programming without compromising accuracy.
• Performance and Accuracy: Demonstrates superior or equivalent scaffold quality compared with SOPRA and SSPACE in analyses of large genomes.

Scientific Applications:

• Large-genome assembly from short reads: Scaffolding of large genomes assembled from short-read sequencing data to improve assembly contiguity.
• Complete genome sequence construction: Supporting the construction of more complete genome sequences by producing accurate scaffolds.
• Evolutionary studies: Facilitating comparative and evolutionary genomics through improved assembly quality.
• Disease gene identification: Enabling more reliable disease gene identification via improved genomic assemblies.
• Personalized medicine: Supporting personalized medicine applications that require accurate reference assemblies.

Methodology:

The method decomposes the scaffolding problem by representing contigs as a graph, identifying biconnected components, restricting subproblem sizes, and solving each component independently with mixed integer programming.