×

On the comparison of incompatibility of split systems across different numbers of taxa. (English) Zbl 1467.92138

Summary: We consider the problem of the minimum number of phylogenetic trees it would take to display all splits in a given set, a problem related to \(k\)-compatibility. A set of trees that displays every single possible split is termed a universal tree set. In this note, we find the universal incompatibility \(U(n)\), the minimal size of a universal tree set for \(n\) taxa. By normalising incompatibility using \(U(n)\), one can then compare incompatibility of split systems across different numbers of taxa. We demonstrate this application by comparing two SplitsTree networks derived from archaeal genomes, with different numbers of taxa.

MSC:

92D15 Problems related to evolution
92B10 Taxonomy, cladistics, statistics in mathematical biology

Software:

GitHub; OEIS; MAFFT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ban, N.; Beckmann, R.; Cate, JHD; Dinman, JD; Dragon, F.; Ellis, SR; Lafontaine, DLJ; Lindahl, L.; Liljas, A.; Lipton, JM, A new system for naming ribosomal proteins, Curr Opin Struct Biol, 24, 165-169 (2014)
[2] Bandelt, H.; Forster, P.; Röhl, A., Median-joining networks for inferring intraspecific phylogenies, Mol Biol Evolut, 16, 1, 37-48 (1999)
[3] Buneman P (1971) The recovery of trees from measures of dissimilarity. Mathematics in the Archaeological and Historical Sciences
[4] Dilworth, RP, A decomposition theorem for partially ordered sets, Math, 50, 161-166 (1950) · Zbl 0038.02003
[5] Dress A, Klucznik M, Koolen J, and Moulton \(V (2001) 2kn - {2k+1 \atopwithdelims ()2}\): a note on extremal combinatorics of cyclic split systems. Séminaire Lotharingien de Combinatoire, 47: 17 · Zbl 0989.05123
[6] Felsenstein, J., Inferring phylogenies (2004), MA: Sinauer associates Sunderland, MA
[7] Goyal, N.; Zhou, Z.; Karimi, IA, Metabolic processes of Methanococcus maripaludis and potential applications, Microbial Cell Factories, 15, 1, 107 (2016)
[8] Hendriksen M (2020)MinimalTreeSets. https://github.com/mahendriksen/minimaltreesets. https://github.com/mahendriksen/MinimalTreeSets. GitHub repository
[9] Holland B and Moulton V (2003) Consensus networks: a method for visualising incompatibilities in collections of trees. In: International workshop on algorithms in bioinformatics, pages 165-176. Springer
[10] Huson, DH; Bryant, D., Application of phylogenetic networks in evolutionary studies, Mol Biol Evol, 23, 2, 254-267 (2006)
[11] Karzanov A, Lomonosov M (1978) Systems of flows in undirected networks. pages 59-66
[12] Katoh, K.; Misawa, K.; Kuma, K.; Miyata, T., MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform, Nucl Acids Res, 30, 14, 3059-3066 (2002)
[13] Kummer, EE, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J für die reine und Angew Math, 44, 93-146 (1852)
[14] Little, CHC; Grant, DD; Holton, DA, On defect-\(d\) matchings in graphs, Discrete Math, 13, 1, 41-54 (1975) · Zbl 0304.05120
[15] Nelson-Sathi, S.; Sousa, FL; Roettger, M.; Lozada-Chávez, N.; Thiergart, T.; Janssen, A.; Bryant, D.; Landan, G.; Schönheit, P.; Siebers, B., Origins of major archaeal clades correspond to gene acquisitions from bacteria, Nature, 517, 7532, 77-80 (2015)
[16] OEIS Foundation Inc. (2020) The on-line encyclopedia of integer sequences. https://oeis.org/A002661
[17] O’Leary, NA; Wright, MW; Brister, JR; Ciufo, S.; Haddad, D.; McVeigh, R.; Rajput, B.; Robbertse, B.; Smith-White, B.; Ako-Adjei, D., Reference sequence (refseq) database at ncbi: current status, taxonomic expansion, and functional annotation, Nucl Acids Res, 44, D1, D733-D745 (2016)
[18] Semple, C.; Steel, M., Phylogenetics (2003), Oxford: Oxford University Press, Oxford · Zbl 1043.92026
[19] Sperner, E., Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift, 27, 1, 544-548 (1928) · JFM 54.0090.06
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.