Testing consistency of quartet topologies: A parameterized approach

• A study on property testing for consistency of a set of quartet topologies.
• Extension of our previous work in 2011.
• We propose testers which deal with incomplete inputs with missing quartets.
• Applying the bounded-depth search tree approach to improve the testing complexity.

Property testing considers the following task: given a function ψ over a domain D  , a property PP and a parameter 0<ϵ<10<ϵ<1, by querying function values of f   over o(|D|)o(|D|) elements in D, determine if ψ   satisfies PP or differs from any one which satisfies PP in at least ϵ|D|ϵ|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 O(1.7321kkn3/ϵ)O(1.7321kkn3/ϵ) time and uses O(kn3/ϵ)O(kn3/ϵ) queries, to test if Q is consistent with an evolutionary tree.