Orthology Relation and Gene Tree Correction: Complexity Results
From MaRDI portal
Publication:5283821
DOI10.1007/978-3-662-48221-6_5zbMath1367.92086OpenAlexW2238809220MaRDI QIDQ5283821
Nadia El-Mabrouk, Manuel Lafond
Publication date: 25 July 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-48221-6_5
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) Computational methods for problems pertaining to biology (92-08)
Related Items (7)
From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Beyond representing orthology relations by trees ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ Reconciling event-labeled gene trees with MUL-trees and species networks
Cites Work
- Unnamed Item
- The node-deletion problem for hereditary properties is NP-complete
- Comparison of phylogenetic trees
- Orthology relations, symbolic ultrametrics, and cographs
- Cograph Editing: Complexity and Parameterized Algorithms
- The complexity of some edge deletion problems
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Error Detection and Correction of Gene Trees
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
This page was built for publication: Orthology Relation and Gene Tree Correction: Complexity Results
