TY - GEN

T1 - Combining Orthology and Xenology Data in a Common Phylogenetic Tree

AU - Hellmuth, Marc

AU - Miche, Mira

AU - Nøjgaard, Nikolai

AU - Schaller, David

AU - Stadler, Peter F.

PY - 2021

Y1 - 2021

N2 - In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels λ(e). The orthology and paralogy relations between genes are a special case of a map δ on the pairs of leaves of T defined by δ(x, y) = q if the last common ancestor lca (x, y) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map ε with m∈ ε(x, y) if m∈ λ(e) for at least one edge e along the path from lca (x, y) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps (δ, ε) derives from a tree (T, t, λ) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (T
δ, t
δ) that explains δ and the (unique) least-resolved edge labeled tree (T
ε, λ
ε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.

AB - In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels λ(e). The orthology and paralogy relations between genes are a special case of a map δ on the pairs of leaves of T defined by δ(x, y) = q if the last common ancestor lca (x, y) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map ε with m∈ ε(x, y) if m∈ λ(e) for at least one edge e along the path from lca (x, y) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps (δ, ε) derives from a tree (T, t, λ) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (T
δ, t
δ) that explains δ and the (unique) least-resolved edge labeled tree (T
ε, λ
ε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.

KW - Binary relations

KW - Consistency

KW - Fitch map

KW - Mathematical phylogenetics

KW - Rooted trees

KW - Symbolic ultrametric

U2 - 10.1007/978-3-030-91814-9_5

DO - 10.1007/978-3-030-91814-9_5

M3 - Article in proceedings

SN - 9783030918132

T3 - Lecture Notes in Computer Science

SP - 53

EP - 64

BT - Advances in Bioinformatics and Computational Biology - 14th Brazilian Symposium on Bioinformatics, BSB 2021, Proceedings

A2 - Stadler, Peter F.

A2 - Walter, Maria Emilia M. T.

A2 - Hernandez-Rosales, Maribel

A2 - Brigido, Marcelo M.

PB - Springer

T2 - 14th Brazilian Symposium on Bioinformatics, Virtual

Y2 - 22 November 2021 through 26 November 2021

ER -