Complexity insights of the minimum duplication problem

DOI10.1016/j.tcs.2014.02.025zbMath1359.68117MaRDI QIDQ2440167

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

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 complexity; randomized algorithm; APX-hardness; comparative genomics; minimum duplication problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D15: Problems related to evolution

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

92D10: Genetics and epigenetics

68W20: Randomized algorithms

92-08: Computational methods for problems pertaining to biology

Related Items

Maximum cuts in edge-colored graphs, Correcting gene tree by removal and modification: tractability and approximability, Correcting gene trees by leaf insertions: complexity and approximation

Uses Software

• Genetree

Cites Work

• Unnamed Item
• New results on optimizing rooted triplets consistency
• Some APX-completeness results for cubic graphs
• Reconciling a gene tree to a species tree under the duplication cost model
• Complexity Insights of the Minimum Duplication Problem
• An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model
• The gene evolution model and computing its associated probabilities
• Reconciling Gene Trees with Apparent Polytomies
• From Gene Trees to Species Trees
• Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs
• An upper bound for the chromatic number of a graph and its application to timetabling problems