Mark Jones, Manuel Lafond, Celine ScornavaccaPlease use the format "First name initials family name" as in "Marie S. Curie, Niels H. D. Bohr, Albert Einstein, John R. R. Tolkien, Donna T. Strickland"
<p style="text-align: justify;">Orthology and paralogy relations are often inferred by methods based on gene sequence similarity that yield a graph depicting the relationships between gene pairs. Such relation graphs frequently contain errors, as they cannot be explained via a gene tree that contains the depicted orthologs/paralogs while being consistent with the species evolution. Previous research has mostly focused on correcting such errors in some minimal way, for instance by changing a minimum number of relations to attain consistency. In this work, we ask: could the errors in the orthology predictions be explained by lateral gene transfer? We formalize this question by allowing gene transfers to behave either as a speciation or as a duplication, expanding the space of valid orthology graphs. We then provide a variety of algorithmic results regarding the underlying problems. Namely, we show that deciding if a relation graph R is consistent with a given species network N with known transfer highways is NP-hard, and that it is W[1]-hard under the parameter “minimum number of transfers”. During the process, we define a novel algorithmic problem called Antichain on trees, which may be useful for other reductions. We then present an FPT algorithm for the decision problem based on the degree of the gene tree associated with R. We also study analogous problems in the case that the transfer highways on a species tree are unknown.</p>
orthology, phylogenetic network, algorithms, fixed-parameter tractability
Computational complexity, Design and analysis of algorithms, Evolutionary Biology, Graph theory
