Property testing considers the following task: given a function ψ over a domain D, a property P and a parameter 0 < \epsilon < 1, by querying function values of f over o(|D|) elements in D, determine if ψ satisfies P or differs from any one which satisfies P in at least \epsilon |D| 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 time O(1.7321^k kn^3/\epsilon) and uses queries, to test if Q is consistent with an evolutionary tree.
Relation:
Information Processing Letters 113(22-24), pp. 852-857
