Global Optimization Methods for Genome Scaffolding

Sebastien François 1 Rumen Andonov 1 Hristo Djidjev 2 Dominique Lavenier 1
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : We develop a method for solving genome scaffolding as a problem of finding a long simple path in a graph defined by the contigs that satisfies additional constraints encoding the insert-size information. Then we solve the resulting mixed integer linear program to optimality using the Gurobi solver. We test our algorithm on several chloroplast genomes and show that it is fast and outperforms other widely-used assembly algorithms by the accuracy of the results.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01385665
Contributor : Dominique Lavenier <>
Submitted on : Friday, October 21, 2016 - 5:52:14 PM
Last modification on : Thursday, February 7, 2019 - 4:49:16 PM

File

WCB16_paper_6.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01385665, version 1

Citation

Sebastien François, Rumen Andonov, Hristo Djidjev, Dominique Lavenier. Global Optimization Methods for Genome Scaffolding. 12th International Workshop on Constraint-Based Methods for Bioinformatics , Sep 2016, Toulouse, France. ⟨hal-01385665⟩

Share

Metrics

Record views

566

Files downloads

206