A polynomial time algorithm for the minimum quartet inconsistency problem with O(n) quartet errors

We present a polynomial time algorithm for the Minimum Quartet Inconsistency (MQI) problem when the number of quartet errors is O(n). This improves the previously best algorithmic result saying that if the number of quartet errors is at most (n−3)/2 then the MQI problem can be solved in polynomial time.