Correcting gene trees by leaf insertions: complexity and approximation

DOI10.1016/J.ENTCS.2016.03.004zbMATH Open1345.92099OpenAlexW2337528775WikidataQ113317701 ScholiaQ113317701MaRDI QIDQ737083FDOQ737083

Authors Stefano Beretta, Riccardo Dondi

Publication date 5 August 2016

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

zbMATH Keywords

algorithmscomputational complexityphylogenomicscomputational biologygene tree correctionsgene tree-species tree reconciliation

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Correcting gene tree by removal and modification: tractability and approximability
• Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability
• Gene tree correction for reconciliation and species tree inference: complexity and algorithms
• Orthology relation and gene tree correction: complexity results
• A general framework for gene tree correction based on duplication-loss reconciliation

Cites work

• scientific article; zbMATH DE number 1113970 (Why is no real title available?)
• Complexity insights of the minimum duplication problem
• Correcting gene tree by removal and modification: tractability and approximability
• DLS-trees: a model of evolutionary scenarios
• From Gene Trees to Species Trees
• Gene tree correction for reconciliation and species tree inference: complexity and algorithms
• Inapproximability results for the lateral gene transfer problem
• Reconciling Gene Trees with Apparent Polytomies
• Reconciling a gene tree to a species tree under the duplication cost model
• Some APX-completeness results for cubic graphs

Cited in

(4)

• Optimal Completion of Incomplete Gene Trees in Polynomial Time Using OCTAL
• Correcting gene tree by removal and modification: tractability and approximability
• Gene Tree Correction by Leaf Removal and Modification: Tractability and Approximability
• Orthology relation and gene tree correction: complexity results

Describes a project that uses

Uses Software

• Genetree
• Notung

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q737083)