Linearizing Genomes: Exact Methods and Local Search

DOI10.1007/978-3-030-38919-2_41zbMath1447.92251OpenAlexW2999738520MaRDI QIDQ3297780

Annie Chateau, Mathias Weller, Rodolphe Giroudeau, Tom Davot

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-02332049/file/main.pdf

zbMATH Keywords

polynomial local searchgenome linearization

Mathematics Subject Classification ID

Integer programming (90C10) Dynamic programming (90C39) Genetics and epigenetics (92D10)

Uses Software

• htd

Cites Work

• How easy is local search?
• Treewidth. Computations and approximations
• Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
• On the linearization of scaffolds sharing repeated contigs
• New results about the linearization of scaffolds sharing repeated contigs
• A complexity and approximation framework for the maximization scaffolding problem
• Simple Local Search Problems that are Hard to Solve
• On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
• On Finding and Verifying Locally Optimal Solutions

This page was built for publication: Linearizing Genomes: Exact Methods and Local Search