Inferring phylogenetic trees from the knowledge of rare evolutionary events. (English) Zbl 1386.05186

Summary: Rare events have played an increasing role in molecular phylogenetics as potentially homoplasy-poor characters. In this contribution we analyze the phylogenetic information content from a combinatorial point of view by considering the binary relation on the set of taxa defined by the existence of a single event separating two taxa. We show that the graph-representation of this relation must be a tree. Moreover, we characterize completely the relationship between the tree of such relations and the underlying phylogenetic tree. With directed operations such as tandem-duplication-random-loss events in mind we demonstrate how non-symmetric information constrains the position of the root in the partially reconstructed phylogeny.


05C90 Applications of graph theory
05C05 Trees
92D15 Problems related to evolution


Full Text: DOI arXiv


[1] Abascal, F; Posada, D; Zardoya, R, The evolution of the mitochondrial genetic code in arthropods revisited, Mitochondrial DNA, 23, 84-91, (2012)
[2] Ashkenazy, H; Cohen, O; Pupko, T; Huchon, D, Indel reliability in indel-based phylogenetic inference, Genome Biol Evol, 6, 3199-3209, (2014)
[3] Bernt, M; Merkle, D; Rasch, K; Fritzsch, G; Perseke, M; Bernhard, D; Schlegel, M; Stadler, PF; Middendorf, M, Crex: inferring genomic rearrangements based on common intervals, Bioinformatics, 23, 2957-2958, (2007)
[4] Boore, JL, The use of genome-level characters for phylogenetic reconstruction, Trends Ecol Evol, 21, 439-446, (2006)
[5] Boore, JL; Brown, WM, Big trees from little genomes: mitochondrial gene order as a phylogenetic tool, Curr Opin Genet Dev, 8, 668-674, (1998)
[6] Brandstdt, A; Le, VB; Rautenbach, D, Exact leaf powers, Theor Comput Sci, 411, 2968-2977, (2010) · Zbl 1193.05141
[7] Bryant, D; Steel, M, Extension operations on sets of leaf-labelled trees, Adv Appl Math, 16, 425-453, (1995) · Zbl 0863.92012
[8] Calamoneri, T; Sinaimeri, B, Pairwise compatibility graphs: a survey, SIAM Rev, 58, 445-460, (2016) · Zbl 1342.05058
[9] Calamoneri, T; Montefusco, E; Petreschi, R; Sinaimeri, B, Exploring pairwise compatibility graphs, Theor Comput Sci, 468, 23-36, (2013) · Zbl 1258.05104
[10] Chaudhuri K, Chen K, Mihaescu R, Rao S (2006) On the tandem duplication-random loss model of genome rearrangement. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms. ACM, pp 564-570 · Zbl 1192.92017
[11] Deeds, EJ; Hennessey, H; Shakhnovich, EI, Prokaryotic phylogenies inferred from protein structural domains, Genome Res, 15, 393-402, (2005)
[12] Dekker MCH (1986). Reconstruction methods for derivation trees. Master’s thesis, Vrije Universiteit, Amsterdam, Netherlands
[13] Donath A, Stadler PF (2014) Molecular morphology: higher order characters derivable from sequence information. In: Wägele JW, Bartolomaeus T (eds) Deep Metazoan phylogeny: the backbone of the tree of life. New insights from analyses of molecules, morphology, and theory of data analysis, chap. 25. de Gruyter, Berlin, pp 549-562
[14] Durocher S, Mondal D, Rahman MS, (2013) On graphs that are not PCGs. In: Ghosh SK, Tokuyama T (eds) WALCOM: algorithms and computation: Proceedings of 7th international workshop, WALCOM 2013, Kharagpur, India, 14-16 February, 2013. Springer, Berlin Heidelberg, pp. 310-321
[15] Dutilh, BE; Snel, B; Ettema, TJ; Huynen, MA, Signature genes as a phylogenomic tool, Mol Biol Evol, 25, 1659-1667, (2008)
[16] Forst, CV; Schulten, K, Phylogenetic analysis of metabolic pathways, J Mol Evol, 52, 471-489, (2001)
[17] Forst, CV; Flamm, C; Hofacker, IL; Stadler, PF, Algebraic comparison of metabolic networks, phylogenetic inference, and metabolic innovation, BMC Bioinform., 7, 67, (2006)
[18] Fritzsch, G; Schlegel, M; Stadler, PF, Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny, J Theor Biol, 240, 511-520, (2006)
[19] Hartmann T, Chu AC, Middendorf M, Bernt M (2016) Combinatorics of tandem duplication random loss mutations on circular genomes. IEEEACM Trans Comput Biol Bioinform PP(99):1-1
[20] Hellmuth M, Wieseke N (2015) On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions. In: Xu D, Du D, Du D (eds) Computing and Combinatorics, vol. 9198 of Lecture Notes Computer Science. Springer International Publishing, pp 609-623 · Zbl 1468.05227
[21] Hellmuth, M; Wieseke, N; Pontarotti, P (ed.), From sequence data including orthologs, paralogs, and xenologs to gene and species trees, 373-392, (2016), Cham
[22] Hellmuth M, Wieseke N (2017) On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions. J Comb Optim. https://doi.org/10.1007/s10878-017-0111-7 · Zbl 1468.05227
[23] Hellmuth, M; Hernandez-Rosales, M; Huber, KT; Moulton, V; Stadler, PF; Wieseke, N, Orthology relations, symbolic ultrametrics, and cographs, J Math Biol, 66, 399-420, (2013) · Zbl 1408.05038
[24] Hellmuth, M; Wieseke, N; Lechner, M; Lenhof, HP; Middendorf, M; Stadler, PF, Phylogenomics with paralogs, Proc Natl Acad Sci, 112, 2058-2063, (2015)
[25] Hellmuth, M; Stadler, PF; Wieseke, N, The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations, J Math Biol, (2016) · Zbl 1368.05023
[26] Hennig W (1950) Grundzüge einer Theorie der Phylogenetischen Systematik. Deutscher Zentralverlag, Berlin
[27] Hernandez-Rosales, M; Hellmuth, M; Wieseke, N; Huber, KT; Moulton, V; Stadler, PF, From event-labeled gene trees to species trees, BMC Bioinform, 13, s6, (2012)
[28] Krauss, V; Thümmler, C; Georgi, F; Lehmann, J; Stadler, PF; Eisenhardt, C, Near intron positions are reliable phylogenetic markers: an application to holometabolous insects, Mol Biol Evol, 25, 821-830, (2008)
[29] Lafond, M; El-Mabrouk, N, Orthology and paralogy constraints: satisfiability and consistency, BMC Genomics, 15, s12, (2014)
[30] Lavrov, DV, Key transitions in animal evolution: a mitochondrial DNA perspective, Integr Comp Biol, 47, 734-743, (2007)
[31] Mazurie, A; Bonchev, D; Schwikowski, B; Buck, GA, Phylogenetic distances are encoded in networks of interacting pathways, Bioinformatics, 24, 2579-2585, (2008)
[32] Mehnaz S, Rahman MS (2013). Pairwise compatibility graphs revisited. In: 2013 International conference on informatics, electronics and vision (ICIEV), pp 1-6
[33] Misof, B; Fleck, G, Comparative analysis of mt LSU rrna secondary structures of odonates: structural variability and phylogenetic signal, Insect Mol Biol, 12, 535-47, (2003)
[34] Prohaska, SJ; Fried, C; Amemiya, CT; Ruddle, FH; Wagner, GP; Stadler, PF, The shark hoxn cluster is homologous to the human hoxd cluster, J Mol Evol, 58, 212-217, (2004)
[35] Rogozin, IB; Sverdlov, AV; Babenko, VN; Koonin, EV, Analysis of evolution of exon-intron structure of eukaryotic genes, Brief Bioinform, 6, 118-134, (2005)
[36] Rokas, A; Holland, PW, Rare genomic changes as a tool for phylogenetics, Trends Ecol Evol, 15, 454-459, (2000)
[37] Sankoff, D; Leduc, G; Antoine, N; Paquin, B; Lang, BF; Cedergren, R, Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome, Proc Natl Acad Sci USA, 89, 6575-6579, (1992)
[38] Sempere, LF; Cole, CN; McPeek, MA; Peterson, KJ, The phylogenetic distribution of metazoan micrornas: insights into evolutionary complexity and constraint, J Exp Zoolog B Mol Dev Evol, 306, 575-588, (2006)
[39] Semple C, Steel M (2003) Phylogenetics, vol. 24 of Oxford lecture series in mathematics and its applications. Oxford University Press, Oxford
[40] Shedlock, AM; Okada, N, SINE insertions: powerful tools for molecular systematics, BioEssays, 22, 148-160, (2000)
[41] Simmons, MP; Ochoterena, H, Gaps as characters in sequence-based phylogenetic analyses, Syst Biol, 49, 369-381, (2000)
[42] Stechmann, A; Cavalier-Smith, T, The root of the eukaryote tree pinpointed, Curr Biol, 13, r665-r666, (2003)
[43] Tang J, Wang LS (2005). Improving genome rearrangement phylogeny using sequence-style parsimony. In: Karypis G, Bourbakis NG, Tsai J (eds) Proceedings of the IEEE fifth symposium on bioinformatics and bioengineering (BIBE’05). IEEE Computer Society, Los Alamitos, CA, pp 137-144
[44] Wagner, G; Stadler, PF, Quasi-independence, homology and the unity of type: a topological theory of characters, J Theor Biol, 220, 505-527, (2003)
[45] Wang, LS; Warnow, T; Moret, BM; Jansen, RK; Raubeson, LA, Distance-based genome rearrangement phylogeny, J Mol Evol, 63, 473-483, (2006)
[46] Yang, S; Doolittle, RF; Bourne, PE, Phylogeny determined by protein domain content, Proc Natl Acad Sci USA, 102, 373-378, (2005)
[47] Yanhaona MN, Bayzid MS, Rahman MS (2010). Discovering pairwise compatibility graphs. In: Thai MT, Sahni S (eds) Computing and combinatorics: Proceedings of 16th annual international conference, COCOON 2010, Nha Trang, Vietnam, 19-21 July , 2010. Springer, Berlin Heidelberg, pp 399-408 · Zbl 1286.05144
[48] Yanhaona MN, Hossain KSMT, Rahman MS (2008). Pairwise compatibility graphs. In: Nakano Si, Rahman MS, (eds) WALCOM: Algorithms and computation: proceedings second international workshop, WALCOM 2008, Dhaka, Bangladesh, 7-8 February, 2008. Springer, Berlin Heidelberg, pp 222-233
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.