Global optimization for scaffolding and completing genome assemblies

DOI10.1016/J.ENDM.2018.01.020MaRDI QIDQ1742221zbMATH OpenOpenAlexWikidataFDO

Authors Sebastien François, Rumen Andonov, D. Lavenier, Hristo N. Djidjev

Publication date 11 April 2018

Full work available at URL https://hal.inria.fr/hal-01499859/file/RR-9050%20%281%29.pdf

Mathematics Subject Classification ID

Linear programming (90C05) Protein sequences, DNA sequences (92D20) Mixed integer programming (90C11)

Recommendations

• Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds
• On the linearization of scaffolds sharing repeated contigs
• Better approximation algorithms for scaffolding problems
• New results about the linearization of scaffolds sharing repeated contigs
• Approximation algorithms for the scaffolding problem and its generalizations

Cites work

• An Eulerian path approach to DNA fragment assembly
• Exact methods for solving the elementary shortest and longest path problems
• The greedy path-merging algorithm for contig scaffolding

Cited in

(9)

• OMGS: optical map-based genome scaffolding
• Optimal Omnitig Listing for Safe and Complete Contig Assembly
• Instance guaranteed ratio on greedy heuristic for genome scaffolding
• The longest run subsequence problem
• Gap filling as exact path length problem
• A mixed integer linear programming algorithm for plasmid binning
• Economic genome assembly from low coverage illumina and nanopore data
• The greedy path-merging algorithm for contig scaffolding
• On the linearization of scaffolds sharing repeated contigs

Describes a project that uses

Uses Software

• ART
• ScaffMatch
• BESST
• QUAST
• GRASS
• Gurobi

This page was built for publication: Global optimization for scaffolding and completing genome assemblies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1742221)