Complexity insights of the minimum duplication problem

DOI10.1016/J.TCS.2014.02.025MaRDI QIDQ2440167zbMATH OpenOpenAlexFDO

Authors Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi, Florian Sikora

Publication date 27 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.02.025

zbMATH Keywords

APX-hardnesscomparative genomicscomputational complexityminimum duplication problemrandomized algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10) Problems related to evolution (92D15)

Recommendations

• Complexity insights of the minimum duplication problem
• scientific article; zbMATH DE number 1303034
• Computing a smallest multi-labeled phylogenetic tree from rooted triplets
• An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
• Reconciling a gene tree to a species tree under the duplication cost model

Cites work

• An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Complexity insights of the minimum duplication problem
• From Gene Trees to Species Trees
• scientific article; zbMATH DE number 2185622 (Why is no real title available?)
• New results on optimizing rooted triplets consistency
• Reconciling a gene tree to a species tree under the duplication cost model
• Reconciling Gene Trees with Apparent Polytomies
• Resolving rooted triplet inconsistency by dissolving multigraphs
• Some APX-completeness results for cubic graphs
• The gene evolution model and computing its associated probabilities

Cited in

(6)

• Complexity insights of the minimum duplication problem
• An approximation algorithm for computing a parsimonious first speciation in the gene duplication model
• scientific article; zbMATH DE number 1303034 (Why is no real title available?)
• Correcting gene tree by removal and modification: tractability and approximability
• FullSynesth: syntenic reconciliation of a set of consistent gene trees
• Correcting gene trees by leaf insertions: complexity and approximation

Describes a project that uses

Uses Software

• Genetree

This page was built for publication: Complexity insights of the minimum duplication problem

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