Linearizing genomes: exact methods and local search

DOI10.1007/978-3-030-38919-2_41MaRDI QIDQ3297780zbMATH OpenOpenAlexFDO

Authors Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller

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

genome linearizationpolynomial local search

Mathematics Subject Classification ID

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

Recommendations

• Revisiting the minimum breakpoint linearization problem
• Revisiting the minimum breakpoint linearization problem
• New results about the linearization of scaffolds sharing repeated contigs
• How easy is local search?
• Finding Local Genome Rearrangements

Cites work

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

Cited in

(4)

• Solving the gene duplication feasibility problem in linear time
• New results about the linearization of scaffolds sharing repeated contigs
• The matrix iteration algorithm solving an enumeration problem on bacterial complete genomes
• Combinatorial Pattern Matching

Describes a project that uses

Uses Software

• htd

This page was built for publication: Linearizing genomes: exact methods and local search

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