<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
X-Trees and Weighted Quartet Systems
Andreas W.M. Dress1 and Péter L. Erdős2
1Forschungsschwerpunkt Mathematisierung-Struktubildugprozesse, University of Bielefeld P.O. Box 100131, 33501 Bielefeld, Germany
2A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, P.O. Box 127 1364 Hungary
Annals of Combinatorics 7 (2) p.155-169 June, 2003
AMS Subject Classification: 05C05, 92D15, 92B05
In this note, we consider a finite set X and maps W from the set of all 2, 2-splits of X into . We show that such a map W is induced, in a canonical way, by a binary X-tree for which a positive length is associated to every inner edge e if and only if (i) exactly two of the three numbers W(ab|cd), W(ac|bd), and W(ad|cb) vanish, for any four distinct elements a, b, c, d in X, (ii) a d and W(ab|xc) + W(ax|cd) = W(ab|cd) holds for all a, b, c, d, x in X with #{a, b, c, x} = #{b, c, d, x}=4 and W(ab|cx), W(ax|cd) > 0 and (iii) W(ab|uv) min(W(ab|uw), W(ab|vw)) holds for any five distinct elements a, b, u, v, w in X. Possible generalizations regarding arbitrary R-trees and applications regarding tree-reconstruction algorithms are indicated.
Keywords: biological systematics, phylogeny, phylogenetic combinatorics, evolutionary trees, tree reconstruction, X-trees, quartet methods, quartet systems, weighted quartet systems.


1. H.-J. Bandelt and A. Dress, Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math. 7 (1986) 309–343.

2. S. Böcker, From subtrees to supertrees, Ph.D. Thesis, Universität Bielefeld, 1999, pp. 1–100.

3. S. Böcker, A.W.M. Dress, and M.A. Steel, Patching up X-trees, Ann. Combin. 3 (1999) 1–12.

4. S. Böcker, D. Bryant, A.W.M. Dress, and M.A. Steel, Algorithmic aspects of tree amalgamation, J. Algorithm 37 (2000) 522–537.

5. H. Colonius and H.H. Schultze, Trees constructed from empirical relations, Braunschweiger Berichte aus dem Institut fuer Psychologie 1 (1977).

6. H. Colonius and H.H. Schultze, Tree structure for proximity data, British J. Math. Statist. Psych. 34 (1981) 167–180.

7. J.H. Badger and P. Kearney, Picking fruit from the tree of life, In: Proc. 16th ACM Symp. Appl. Comput., Las Vegas, March 11–14, 2001, pp. 61–67.

8. A. Ben-Dor, B. Chor, D. Graur, R. Ophir, and D. Pelleg, Constructing phylogenies from quartets: elucidation of Eutherian superordinal relationships, J. Comput. Biol. 5 (3) (1998) 377–390.

9. V. Berry, T. Jiang, P. Kearney, M. Li, and T. Wareham, Quartet cleaning: improved algorithms and simulations, In: Algorithms—ESA'99, 7th European Symposium on Algorithms Prague, Chezh Rep. Lect. Notes Comput. Sci., Vol. 1643, 1999, pp. 313–324.

10. V. Berry and O. Gascuel, Inferring evolutionary trees with strong combinatorial evidence, Theoret. Comput. Sci. 240 (2000) 271–298.

11. V. Berry, D. Bryant, T. Jiang, P. Kearney, M. Li, T. Wareham, and H. Zhang, A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract), In: ACM Symp. on Discrete Algorithms SODA2000, 2000, pp. 287–296.

12. O. Bininda-Emonds, S.G. Brady, J. Kim, and M.J. Sanderson, Scaling of accuracy in extremely large phylogenetic trees, In: 6th Pacific Symp. on Biocomputing, 2001, pp. 547– 558.

13. D.J. Bryant and M.A. Steel, Extension operations on sets of leaf-labelled trees, Adv. Appl. Math. 16 (1995) 425–453.

14. D. Bryant and M. Steel, Fast algorithms for constructing optimal trees from quartets, In: Proc. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, 1999, pp. 147–155.

15. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archaeological and Historical Sciences, F.R. Hodson, D.G. Kendall, and P. Tautu, Eds., Edinburgh University Press, Edinburgh, 1971, pp. 387–395.

16. B. Chor, Form quartets to phylogenetic trees, In: SOFSEM'8: Theory and Practice of Informatics, B. Rovan, Ed., Lecture Notes in Computer Science, Vol. 1521, Springer-Verlag, 1998, pp. 36–53.

17. M. Csűrös and M-Y. Kao, Provable and accurate recovery of evolutionary trees through harmonic greedy triplets, SIAM J. Comput. 31 (2001) 306–322.

18. M. Csűrös, Fast recovery of evolutionary trees with thousands of nodes, J. Comput. Biol. 9 (2002) 277–297.

19. M.C.H. Dekker, Reconstruction methods for derivation trees, Master's Thesis, Vrije Universiteit, Amsterdam, 1986.

20. A. Dress, M. Hendy, K. Huber, and V. Moulton, Enumerating the vertices of the Buneman graph, Preprints Forschungsschwerpunkt Mathematisierung/Strukturbildungsprozesse, 117, 1997.

21. P.L. Erdős, M.A. Steel, L.A. Székely, and T. Warnow, Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule, Comput. Artificial Intelligence 16 (2) (1997) 217–227.

22. P.L. Erdős, M.A. Steel, L.A. Székely, and T. Warnow, Inferring big trees from short quartets, In: Automata, Languages and Programming 24th International Colloquium, ICALP'7, Bologna, Italy, July 7–11, 1997, P. Degano, R. Gorrieri, A. Marchetti-Spaccamela, Eds., Lecture Notes in Computer Science, Vol. 1256, 1997, pp. 827–837.

23. J. Gramm and R. Niedermeier, Minimum quartet inconsistency is fixed parameter tractable, In: Combinatorial Pattern Matching, CPM2001, A. Amir and G.M. Landau Eds., Israel, Jerusalem, LNCS 2089, 2001, pp. 241–256.

24. S. Grünewald, The quartet joining algorithm, manuscript, Bielefeld, 2002.

25. D. Huson, S. Nettles, L. Parida, T. Warnow, and S. Yooseph, The disk-covering method for tree reconstruction, In: Proceedings of "Algorithms and Experiments," ALEX'98, Trento, Italy, 1998, pp. 62–75.

26. D. Huson, S. Nettles, K. Rice, T.Warnow, and S. Yooseph, Hybrid tree reconstruction methods, ACM J. Exp. Alg. 4 (1998) Article 5.

27. D.H. Huson, S.M. Nettles, and T.J. Warnow, Disk-covering, a fast-converging method for phylogenetic tree reconstruction, J. Comput. Biol. 6 (3/4) (1999) 369–386.

28. T. Jiang, P. Kearney, and M. Li, Orchestrating quartets: approximation and data correction, FOCS'8 Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 416–425.

29. T. Jiang, P. Kearney, and M. Li, A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application, SIAM J. Comput. 30 (2000) 1942–1961.

30. P.E. Kearney, The ordinal quartet method (extended abstract), In: RECOMB'8, New York, 1998, pp. 125–133.

31. J. Kim, large-scale phylogenies and measuring the performance of phylogenetic estimators, Syst. Biol. 47 (1998) 43–60.

32. J. Lagergren, Combining polynomial running time and fast convergence for the diskcovering method, J. Comput. System Sci. 65 (2002) 481–493.

33. L. Nakhleh, U. Roshan, K.St. John, J. Sun, and T.Warnow, Designing fast converging phylogenetic methods, In: Bioinformatics, Oxford University Press, ISMB'1 17 (90001), 2001, S190–S198.

34. V. Ranwez and O. Gascuel, Quartet based phylogenetic inference: improvements and limits, Mol. Biol. Evol. 18 (6) (2001) 1103–1116.

35. K. Strimmer and A. von Haeseler, Quartet puzzling: a quartet maximum likelihood method for reconstructing tree topologies, Mol. Biol. Evol. 13 (1996) 964–969.

36. K. Strimmer, N. Goldman, and A. von Haeseler, Bayesian probabilities and quartet puzzling, Mol. Biol. Evol. 14 (1997) 210–211.

37. M.A. Steel, L.A. Székely, and P.L. Erdős, The number of nucleotide sites needed to accurately reconstruct large evolutionary trees, DIMACS Technical Report 1996–19.

38. G.D. Vedova and H.T.Wareham, Optimal algorithms for local vertex quartet cleaning, Bioinformatics 18 (2002) 1297–1304.

39. T. Warnow, B.M.E. Moret, and K.St. John, Absolute convergence: true trees from short sequences, In: ACM Symp. on Discrete Algorithms SODA'01, 2001, pp. 186–195.

40. J. Weyer-Menkhoff, Phylogenetic Combinatorics, Ph.D. Thesis, Bielefeld, 2003.