Approximating the correction of weighted and unweighted orthology and paralogy relations.

CONCLUSIONS: We provided complexity and algorithmic results for variants of the problem of correcting a relation graph for satisfiability and consistency. For the maximization variants we were able to design polynomial time approximation schemes, while for the weighted minimization variants we were able to provide the first inapproximability results. PMID: 28293276 [PubMed]
Source: Algorithms for Molecular Biology : AMB - Category: Molecular Biology Authors: Tags: Algorithms Mol Biol Source Type: research