Complexity insights of the minimum duplication problem

DOI10.1016/j.tcs.2014.02.025zbMath1359.68117OpenAlexW2181191890MaRDI 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 complexityrandomized algorithmAPX-hardnesscomparative genomicsminimum duplication problem

Mathematics Subject Classification ID

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

Related Items (3)

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

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

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