Combining Orthology and Xenology Data in a Common Phylogenetic Tree
Resumo
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.
Palavras-chave:
Mathematical phylogenetics, Rooted trees, Binary relations, Symbolic ultrametric, Fitch map, Consistency
Referências
Bansal, M.S., Alm, E.J., Kellis, M.: Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 28, i283–i291 (2012). https://doi.org/10.1093/bioinformatics/bts225
Böcker, S., Dress, A.W.M.: Recovering symbolically dated, rooted trees from symbolic ultrametrics. Adv. Math. 138, 105–125 (1998). https://doi.org/10.1006/aima.1998.1743
Bryant, D., Lagergren, J.: Compatibility of unrooted phylogenetic trees is FPT. Theor. Comput. Sci. 351, 296–302 (2006). https://doi.org/10.1016/j.tcs.2005.10.033
Fitch, W.: Homology: a personal view on some of the problems. Trends Genet. 16, 227–231 (2000). https://doi.org/10.1016/S0168-9525(00)02005-9
Geiß, M., Anders, J., Stadler, P.F., Wieseke, N., Hellmuth, M.: Reconstructing gene trees from Fitch’s xenology relation. J. Math. Biol. 77(5), 1459–1491 (2018). https://doi.org/10.1007/s00285-018-1260-8
Geiß, M., et al.: Best match graphs and reconciliation of gene trees with species trees. J. Math. Biol. 80(5), 1459–1495 (2020). https://doi.org/10.1007/s00285-020-01469-y
Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13, 338–355 (1984). https://doi.org/10.1137/0213024
Hellmuth, M.: Biologically feasible gene trees, reconciliation maps and informative triples. Algorithms Mol. Biol. 12, 23 (2017). https://doi.org/10.1186/s13015-017-0114-z
Hellmuth, M., Hernandez-Rosales, M., Huber, K.T., Moulton, V., Stadler, P.F., Wieseke, N.: Orthology relations, symbolic ultrametrics, and cographs. J. Math. Biol. 66, 399–420 (2013). https://doi.org/10.1007/s00285-012-0525-x
Hellmuth, M., Long, Y., Geiß, M., Stadler, P.F.: A short note on undirected Fitch graphs. Art Discrete Appl. Math. 1, P1.08 (2018). https://doi.org/10.26493/2590-9770.1245.98c
Hellmuth, M., Schaller, D., Stadler, P.F.: Compatibility of partitions, hierarchies, and split systems (2021, submitted). arXiv arXiv:2104.14146
Hellmuth, M., Seemann, C.R., Stadler, P.F.: Generalized Fitch graphs II: sets of binary relations that are explained by edge-labeled trees. Discrete Appl. Math. 283, 495–511 (2020). https://doi.org/10.1016/j.dam.2020.01.036
Hellmuth, M., Stadler, P.F., Wieseke, N.: The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations. J. Math. Biol. 75(1), 199–237 (2016). https://doi.org/10.1007/s00285-016-1084-3
Hellmuth, M., Seemann, C.R., Stadler, P.F.: Generalized Fitch graphs III: symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees. Discrete Math. Theor. Comput. Sci 23(1), 13 (2021)
Jones, M., Lafond, M., Scornavacca, C.: Consistency of orthology and paralogy constraints in the presence of gene transfers (2017). arXiv arXiv:1705.01240
Lafond, M., Hellmuth, M.: Reconstruction of time-consistent species trees. Algorithms Mol. Biol. 15, 16 (2020). https://doi.org/10.1186/s13015-020-00175-0
Nøjgaard, N., Geiß, M., Merkle, D., Stadler, P.F., Wieseke, N., Hellmuth, M.: Time-consistent reconciliation maps and forbidden time travel. Algorithms Mol. Biol. 13, 2 (2018). https://doi.org/10.1186/s13015-018-0121-8
Schaller, D., Hellmuth, M., Stadler, P.F.: A linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set (2021, submitted). arXiv arXiv:2107.00072
Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)
Tofigh, A., Hallett, M., Lagergren, J.: Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans. Comput. Biol. Bioinform 8(2), 517–535 (2011). https://doi.org/10.1109/TCBB.2010.14
Böcker, S., Dress, A.W.M.: Recovering symbolically dated, rooted trees from symbolic ultrametrics. Adv. Math. 138, 105–125 (1998). https://doi.org/10.1006/aima.1998.1743
Bryant, D., Lagergren, J.: Compatibility of unrooted phylogenetic trees is FPT. Theor. Comput. Sci. 351, 296–302 (2006). https://doi.org/10.1016/j.tcs.2005.10.033
Fitch, W.: Homology: a personal view on some of the problems. Trends Genet. 16, 227–231 (2000). https://doi.org/10.1016/S0168-9525(00)02005-9
Geiß, M., Anders, J., Stadler, P.F., Wieseke, N., Hellmuth, M.: Reconstructing gene trees from Fitch’s xenology relation. J. Math. Biol. 77(5), 1459–1491 (2018). https://doi.org/10.1007/s00285-018-1260-8
Geiß, M., et al.: Best match graphs and reconciliation of gene trees with species trees. J. Math. Biol. 80(5), 1459–1495 (2020). https://doi.org/10.1007/s00285-020-01469-y
Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13, 338–355 (1984). https://doi.org/10.1137/0213024
Hellmuth, M.: Biologically feasible gene trees, reconciliation maps and informative triples. Algorithms Mol. Biol. 12, 23 (2017). https://doi.org/10.1186/s13015-017-0114-z
Hellmuth, M., Hernandez-Rosales, M., Huber, K.T., Moulton, V., Stadler, P.F., Wieseke, N.: Orthology relations, symbolic ultrametrics, and cographs. J. Math. Biol. 66, 399–420 (2013). https://doi.org/10.1007/s00285-012-0525-x
Hellmuth, M., Long, Y., Geiß, M., Stadler, P.F.: A short note on undirected Fitch graphs. Art Discrete Appl. Math. 1, P1.08 (2018). https://doi.org/10.26493/2590-9770.1245.98c
Hellmuth, M., Schaller, D., Stadler, P.F.: Compatibility of partitions, hierarchies, and split systems (2021, submitted). arXiv arXiv:2104.14146
Hellmuth, M., Seemann, C.R., Stadler, P.F.: Generalized Fitch graphs II: sets of binary relations that are explained by edge-labeled trees. Discrete Appl. Math. 283, 495–511 (2020). https://doi.org/10.1016/j.dam.2020.01.036
Hellmuth, M., Stadler, P.F., Wieseke, N.: The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations. J. Math. Biol. 75(1), 199–237 (2016). https://doi.org/10.1007/s00285-016-1084-3
Hellmuth, M., Seemann, C.R., Stadler, P.F.: Generalized Fitch graphs III: symmetrized Fitch maps and sets of symmetric binary relations that are explained by unrooted edge-labeled trees. Discrete Math. Theor. Comput. Sci 23(1), 13 (2021)
Jones, M., Lafond, M., Scornavacca, C.: Consistency of orthology and paralogy constraints in the presence of gene transfers (2017). arXiv arXiv:1705.01240
Lafond, M., Hellmuth, M.: Reconstruction of time-consistent species trees. Algorithms Mol. Biol. 15, 16 (2020). https://doi.org/10.1186/s13015-020-00175-0
Nøjgaard, N., Geiß, M., Merkle, D., Stadler, P.F., Wieseke, N., Hellmuth, M.: Time-consistent reconciliation maps and forbidden time travel. Algorithms Mol. Biol. 13, 2 (2018). https://doi.org/10.1186/s13015-018-0121-8
Schaller, D., Hellmuth, M., Stadler, P.F.: A linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set (2021, submitted). arXiv arXiv:2107.00072
Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)
Tofigh, A., Hallett, M., Lagergren, J.: Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans. Comput. Biol. Bioinform 8(2), 517–535 (2011). https://doi.org/10.1109/TCBB.2010.14
Publicado
22/11/2021
Como Citar
HELLMUTH, Marc; MICHEL, Mira; NØJGAARD, Nikolai N.; SCHALLER, David; STADLER, Peter F..
Combining Orthology and Xenology Data in a Common Phylogenetic Tree. In: SIMPÓSIO BRASILEIRO DE BIOINFORMÁTICA (BSB), 14. , 2021, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 53-64.
ISSN 2316-1248.
