ArticleAlgorithms for molecular biology : AMB2017
Approximating the correction of weighted and unweighted orthology and paralogy relations.
Article in Algorithms for molecular biology : AMB, 2017. The graph could read no effect estimate from its abstract, so it casts no vote on the map. Cited by 9 papers.
What it found
Each row is one number read from the abstract, on the scale the paper reported it, with its interval. Left of the dashed line favours the treatment, right favours the comparator. Under each row is the sentence it came from. New to these charts? A ten-minute tutorial.
The abstract states no effect estimate the extractor could read, or names no intervention and outcome on the map, so this paper lights no cell and moves no belief. It is still indexed, cited and linked below.
The trial behind it
Trials whose registry record cites this paper, or whose number appears in the abstract. A trial that started after this paper was published is citing it as background, not reporting it.
Neither the registry nor the abstract names a trial number. If this is a trial report, that itself is worth knowing.
Who cites it
9 citing papers in PubMed, 22 citations in OpenAlex.
- Indirect identification of horizontal gene transfer.Journal of mathematical biology · 2021Article
- Best match graphs and reconciliation of gene trees with species trees.Journal of mathematical biology · 2020Article
- Reconstruction of time-consistent species trees.Algorithms for molecular biology : AMB · 2020Article
- Reconciling event-labeled gene trees with MUL-trees and species networks.Journal of mathematical biology · 2019Article
- Best match graphs.Journal of mathematical biology · 2019Article
- Reconciling multiple genes trees via segmental duplications and losses.Algorithms for molecular biology : AMB · 2019Article
- Accurate prediction of orthologs in the presence of divergence after duplication.Bioinformatics (Oxford, England) · 2018Article
- Time-consistent reconciliation maps and forbidden time travel.Algorithms for molecular biology : AMB · 2018Article
- Biologically feasible gene trees, reconciliation maps and informative triples.Algorithms for molecular biology : AMB · 2017Article
Corrections and comments
PubMed lists nothing against this paper. Absence here is not a guarantee, only a check that was made.
Authors and funding
3 authors at 3 institutions in 2 countries.
Funding
No grant is acknowledged in the PubMed record.
Abstract
backgroundGiven a gene family, the relations between genes (orthology/paralogy), are represented by a relation graph, where edges connect pairs of orthologous genes and "missing" edges represent paralogs. While a gene tree directly induces a relation graph, the converse is not always true. Indeed, a relation graph is not necessarily "satisfiable", i.e. does not necessarily correspond to a gene tree. And even if that holds, it may not be "consistent", i.e. the tree may not represent a true history in agreement with a species tree. Previous studies have addressed the problem of correcting a relation graph for satisfiability and consistency. Here we consider the weighted version of the problem, where a degree of confidence is assigned to each orthology or paralogy relation. We also consider a maximization variant of the unweighted version of the problem.
resultsWe provide complexity and algorithmic results for the approximation of the considered problems. We show that minimizing the correction of a weighted graph does not admit a constant factor approximation algorithm assuming the unique game conjecture, and we give an
conclusionsWe 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.
Indexed as
Identifiers
What OpenQuestion holds
Registered trials
Read under generation 80e0d062 · epoch 390. Bibliography from PubMed, PubMed Central and OpenAlex; grants from NIH RePORTER; trial links from ClinicalTrials.gov; estimates, votes and beliefs from the OpenQuestion graph.