Correcting gene tree by removal and modification: tractability and approximability

DOI10.1016/j.jda.2015.03.005zbMath1337.68122OpenAlexW1987603868WikidataQ62044767 ScholiaQ62044767MaRDI QIDQ491623

Stefano Beretta, Riccardo Dondi, Mauro Castelli

Publication date: 18 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.03.005

zbMATH Keywords

computational biologyparameterized complexityapproximation complexitygene tree correctiongene tree reconciliation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Related Items (1)

Correcting gene trees by leaf insertions: complexity and approximation

Uses Software

• Genetree
• Notung

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Non deterministic polynomial optimization problems and their approximations
• Complexity insights of the minimum duplication problem
• Gene tree correction for reconciliation and species tree inference: complexity and algorithms
• Reconciling a gene tree to a species tree under the duplication cost model
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Reconciling Gene Trees with Apparent Polytomies
• From Gene Trees to Species Trees
• Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability

This page was built for publication: Correcting gene tree by removal and modification: tractability and approximability