Abstract
Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0<ε<1, by examining function values of f over o(|D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε|D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f Q , which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f Q satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f Q . In this paper, we prove the existence of a set of quartet topologies of error number at least \(c{n\choose 4}\) for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n 3/ε) queries, and is of one-sided error and non-adaptive.
Similar content being viewed by others
References
Alon, N., Shapira, A.: Homomorphisms in graph property testing—A survey. Electronic Colloquium on Computational Complexity (ECCC). Report No. 85 (2005)
Brooks, R.L.: On coloring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194–197 (1941)
Bandelt, H.J., Dress, A.: Reconstructing the shape of a tree from observed dissimilarity data. Adv. Appl. Math. 7, 309–343 (1986)
Ben-Dor, A., Chor, B., Graur, D., Ophir, R., Pelleg, D.: From four-taxon trees to phylogenies: the case of mammalian evolution. In: Proceedings of the RECOMB, 1998, pp. 9–19. Also see: constructing phylogenies from quartets: elucidation of eutherian superordinal relationships. J. Comput. Biol. 5, 377–390 (1998)
Berry, V., Gascuel, O.: Inferring evolutionary trees with strong combinatorial evidence. Theor. Comput. Sci. 240, 271–298 (2000)
Berry, V., Jiang, T., Kearney, P.E., Li, M., Wareham, H.T.: Quartet cleaning: improved algorithms and simulations. In: Proceedings of the 7th Annual European Symposium on Algorithms (ESA 99). Lecture Notes in Comput. Sci., vol. 1643, pp. 313–324. Springer, Berlin (1999)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 549–595 (1993)
Bryant, D., Steel, M.: Constructing optimal trees from quartets. J. Algorithms 38, 237–259 (2001)
Chor, B.: From quartets to phylogenetic trees. In: Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM). Lecture Notes in Comput. Sci., vol. 1521, pp. 36–53. Springer, Berlin (1998)
Chang, M.-S., Lin, C.-C., Rossmanith, P.: New fixed-parameter algorithms for the minimum quartet inconsistency problem. Theory Comput. Syst. 47, 342–368 (2010)
Colonius, H., Schulze, H.H.: Tree structures for proximity data. Br. J. Math. Stat. Psychol. 34, 167–180 (1981)
Erdős, P., Steel, M., Székely, L., Warnow, T.: A few logs suffice to build (almost) all trees (Part 1). Random Struct. Algorithms 14, 153–184 (1999)
Fischer, E.: The art of uninformed decisions: A primer to property testing. Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS) 75, 97–126 (2001)
Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Inc., Sunderland
Goldreich, O.: Combinatorial property testing—a survey. In: Pardalos, P., Rajaseekaran, S., Rolin, J. (eds.) Randomization Methods in Algorithm Design. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 43, pp. 45–59. AMS, Providence (1998)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45, 653–750 (1998)
Gramm, J., Niedermeier, R.: A fixed-parameter algorithm for minimum quartet inconsistency. J. Comput. Syst. Sci. 67, 723–741 (2003)
Jiang, T., Kearney, P.E., Li, M.: Some open problems in computational molecular biology. J. Algorithms 34, 194–201 (2000)
Jiang, T., Kearney, P.E., Li, M.: A polynomial time approximation scheme for inferring evolutionary tree from quartet topologies and its application. SIAM J. Comput. 30, 1942–1961 (2001)
Ron, D.: Property testing. In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, vol. II, pp. 597–649. Kluwer Academic, Dordrecht (2001)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 252–271 (1996)
Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. J. Classif. 9, 91–116 (1992)
Verwer, R.W.H., Pelt, J.V.: Analysis of binary trees when occasional multifurcations can be considered as aggregates of bifurcations. Bull. Math. Biol. 52, 629–641 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Science Council of Taiwan under grant no. NSC 96-2221-E-194-045-MY3, and partially supported by NSC-DAAD Sandwich Program.
Rights and permissions
About this article
Cite this article
Chang, MS., Lin, CC. & Rossmanith, P. A Property Tester for Tree-Likeness of Quartet Topologies. Theory Comput Syst 49, 576–587 (2011). https://doi.org/10.1007/s00224-010-9276-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9276-5