Partial homology relations - satisfiability in terms of di-cographs

Nikolai Nøjgaard*, Nadia El-Mabrouk, Daniel Merkle, Nicolas Wieseke, Marc Hellmuth

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

128 Downloads (Pure)

Abstrakt

Directed cographs (di-cographs) play a crucial role in the reconstruction of evolutionary histories of genes based on homology relations which are binary relations between genes. A variety of methods based on pairwise sequence comparisons can be used to infer such homology relations (e.g. orthology, paralogy, xenology). They are satisfiable if the relations can be explained by an event-labeled gene tree, i.e., they can simultaneously co-exist in an evolutionary history of the underlying genes. Every gene tree is equivalently interpreted as a so-called cotree that entirely encodes the structure of a di-cograph. Thus, satisfiable homology relations must necessarily form a di-cograph. The inferred homology relations might not cover each pair of genes and thus, provide only partial knowledge on the full set of homology relations. Moreover, for particular pairs of genes, it might be known with a high degree of certainty that they are not orthologs (resp. paralogs, xenologs) which yields forbidden pairs of genes. Motivated by this observation, we characterize (partial) satisfiable homology relations with or without forbidden gene pairs, provide a quadratic-time algorithm for their recognition and for the computation of a cotree that explains the given relations.

OriginalsprogEngelsk
TitelComputing and Combinatorics : 24th International Conference, COCOON 2018, Proceedings
RedaktørerDaming Zhu, Lusheng Wang
Vol/bind10976
ForlagSpringer
Publikationsdato2018
Sider403-415
ISBN (Trykt)978-3-319-94775-4
ISBN (Elektronisk)978-3-319-94776-1
DOI
StatusUdgivet - 2018
Begivenhed24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, Kina
Varighed: 2. jul. 20184. jul. 2018

Konference

Konference24th International Conference on Computing and Combinatorics Conference, COCOON 2018
LandKina
ByQing Dao
Periode02/07/201804/07/2018
NavnLecture Notes in Computer Science
Vol/bind10976
ISSN0302-9743

    Fingerprint

Citationsformater

Nøjgaard, N., El-Mabrouk, N., Merkle, D., Wieseke, N., & Hellmuth, M. (2018). Partial homology relations - satisfiability in terms of di-cographs. I D. Zhu, & L. Wang (red.), Computing and Combinatorics: 24th International Conference, COCOON 2018, Proceedings (Bind 10976, s. 403-415). Springer. Lecture Notes in Computer Science, Bind. 10976 https://doi.org/10.1007/978-3-319-94776-1_34