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

computational complexityrandomized algorithmAPX-hardnesscomparative genomicsminimum duplication problem

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 2185622 (Why is no real title available?)
• 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
• New results on optimizing rooted triplets consistency
• Reconciling Gene Trees with Apparent Polytomies
• Reconciling a gene tree to a species tree under the duplication cost model
• 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

(4)

• Complexity insights of the minimum duplication problem
• Correcting gene trees by leaf insertions: complexity and approximation
• Correcting gene tree by removal and modification: tractability and approximability
• An approximation algorithm for computing a parsimonious first speciation in the gene duplication model

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)