Answer set programming or hypercleaning: Where does the magic lie in solving maximum quartet consistency?

Abstract

Answer set programming (ASP) approach is an efficient approach for solving the maximum quartet consistency problem. We distinguish two factors that affect the efficiency of a recent ASP approach for solving maximum quartet consistency problem; answer set programming itself and a variety of preprocessing steps. In this paper, we propose a method for applying one of the preprocessing steps used in the ASP approach to an alternative algorithm. Our results show that the preprocessing step gives the main contribution to efficiency of the ASP approach for data sets with less than 20 taxa. We also identify an issue in the ASP approach for solving the maximum quartet consistency problem.