Submit a preprint


Consistency of orthology and paralogy constraints in the presence of gene transfersuse asterix (*) to get italics
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>
You should fill this box only if you chose 'All or part of the results presented in this preprint are based on data'. URL must start with http:// or https://
You should fill this box only if you chose 'Scripts were used to obtain or analyze the results'. URL must start with http:// or https://
You should fill this box only if you chose 'Codes have been used in this study'. URL must start with http:// or https://
orthology, phylogenetic network, algorithms, fixed-parameter tractability
NonePlease indicate the methods that may require specialised expertise during the peer review process (use a comma to separate various required expertises).
Computational complexity, Design and analysis of algorithms, Evolutionary Biology, Graph theory
No need for them to be recommenders of PCI Math Comp Biol. Please do not suggest reviewers for whom there might be a conflict of interest. Reviewers are not allowed to review preprints written by close colleagues (with whom they have published in the last four years, with whom they have received joint funding in the last four years, or with whom they are currently writing a manuscript, or submitting a grant proposal), or by family members, friends, or anyone for whom bias might affect the nature of the review - see the code of conduct
e.g. John Doe []
2021-06-30 15:01:44
Barbara Holland