Integer Programming Approach for Nested Pairs Genome Scaffolding

Victor Epain (1) , Rumen Andonov (1)

1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics

Scaffolding step in the genome assembly aims to determine the order and the orientation of a huge number of previously assembled genomic fractions (contigs/scaffolds). Here we introduce a particular case of this problem and denote it by Nested Pairs Scaffolding. We formulate it as an optimisation problem and propose an integer programming formulation for its resolution. The performed computational results on real and synthetic data show an excellent behaviour of our formulation.

Mots clés: De novo genome assembly; Contig; Scaffolding; Elementary longest path problem; Integer programming; NP-Hard problem

Domaines: Recherche opérationnelle [math.OC]; Bio-informatique [q-bio.QM]; Algorithme et structure de données [cs.DS]

Victor Epain, Rumen Andonov. Integer Programming Approach for Nested Pairs Genome Scaffolding. 2022. ⟨hal-03613353⟩