Correcting gene trees by leaf insertions: complexity and approximation

DOI10.1016/j.entcs.2016.03.004zbMath1345.92099OpenAlexW2337528775WikidataQ113317701 ScholiaQ113317701MaRDI QIDQ737083

Riccardo Dondi, Stefano Beretta

Publication date: 5 August 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2016.03.004

zbMATH Keywords

algorithmscomputational complexitycomputational biologyphylogenomicsgene tree correctionsgene tree-species tree reconciliation

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) Approximation algorithms (68W25)

Uses Software

• Genetree
• Notung

Cites Work

• Unnamed Item
• Correcting gene tree by removal and modification: tractability and approximability
• Some APX-completeness results for cubic graphs
• Complexity insights of the minimum duplication problem
• Gene tree correction for reconciliation and species tree inference: complexity and algorithms
• Inapproximability results for the lateral gene transfer problem
• DLS-trees: a model of evolutionary scenarios
• Reconciling a gene tree to a species tree under the duplication cost model
• Reconciling Gene Trees with Apparent Polytomies
• From Gene Trees to Species Trees

This page was built for publication: Correcting gene trees by leaf insertions: complexity and approximation