×

zbMATH — the first resource for mathematics

Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors. (English) Zbl 1347.05234
Campêlo, Manoel (ed.) et al., LAGOS ’15. Selected papers of the 8th Latin-American algorithms, graphs, and optimization symposium, Praia das Fontes, Beberibe, Brazil, May 11–15, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 50, 337-342, electronic only (2015).
Summary: A collection \(\mathcal{P}\) of phylogenetic trees is compatible if there is a tree that displays all the relationships among species exhibited by the trees in \(\mathcal{P}\). We give a simple characterization of compatibility based on graph triangulation. We then study how to deal with incompatibility through edge contraction and tree deletion, and introduce the notion of a phylogenetic minor.
For the entire collection see [Zbl 1342.05003].

MSC:
05C83 Graph minors
92D10 Genetics and epigenetics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A. V.; Sagiv, Y.; Szymanski, T. G.; Ullman, J. D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM J. Comput., 10, 3, 405-421, (1981) · Zbl 0462.68086
[2] Bordewich, M.; Huber, K. T.; Semple, C., Identifying phylogenetic trees, Discrete Mathematics, 300, 1-3, 30-43, (2005) · Zbl 1071.92024
[3] Bryant, D.; Lagergren, J., Compatibility of unrooted phylogenetic trees is FPT, Theor. Comput. Sci., 351, 296-302, (2006) · Zbl 1086.68097
[4] Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, Journal of Combinatorial Theory, Series B, 92, 2, 325-357, (2004) · Zbl 1061.05088
[5] Steel, M. A., The complexity of reconstructing trees from qualitative characters and subtrees, Journal of Classification, 9, 91-116, (1992) · Zbl 0766.92002
[6] Vakati, S., Fixed parameter algorithms for compatible and agreement supertree problems, (2013), Iowa State University, Ph.D. thesis
[7] Vakati, S.; Fernández-Baca, D., Graph triangulations and the compatibility of unrooted phylogenetic trees, Appl. Math. Lett., 24, 5, 719-723, (2011) · Zbl 1209.05055
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.