Testing consistency of quartet topologies: A parameterized approach
Property testing considers the following task: given a function psi over a domain D, a property P and a parameter 0 < epsilon < 1, by querying function values of f over o(vertical bar D vertical bar) elements in D, determine if psi satisfies P or differs from any one which satisfies P in at least epsilon vertical bar D vertical bar elements. We focus on consistency of quartet topologies. Given a set Q of quartet topologies over an n-taxon set and an upper bound k on the number of quartets whose topologies are missing, we present a non-adaptive property tester with one-sided error, which runs in O(1.7321(k)kn(3)/epsilon) time and uses O(kn(3)/epsilon) queries, to test if Q is consistent with an evolutionary tree. (C) 2013 Elsevier B.V. All rights reserved.
property testing evolutionary tree randomized algorithm quartet method