Global Optimization for Scafolding and Completing Genome Assemblies

Sebastien François 1 Rumen Andonov 1, * Dominique Lavenier 1 Hristo Djidjev 2
* Corresponding author
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 scafolding 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 outperforms other widely-used assembly solvers by the accuracy of the results.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01567134
Contributor : Rumen Andonov <>
Submitted on : Friday, July 21, 2017 - 6:07:06 PM
Last modification on : Friday, September 13, 2019 - 9:49:21 AM

File

inoc_17.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01567134, version 1

Citation

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

Share

Metrics

Record views

226

Files downloads

70