A Lookahead Branch-and-Bound Algorithm for the Maximum Quartet Consistency Problem

  • Author(s) / Creator(s)
  • Technical report TR05-05. A lookahead branch-and-bound algorithm is proposed for solving the Maximum Quartet Consistency Problem where the input is a complete set of quartets on the taxa and the goal is to construct a phylogeny which satisfies the maximum number of given quartets. Such a phylogeny constructed from quartets has many advantages over phylogenies constructed through other ways, one of which is that it is able to overcome the data disparity problem. Nonetheless, the MQC problem has been proven to be NP-hard. The branch-and-bound algorithm integrates a number of previous efforts on exact algorithms, heuristics, and approximation algorithms for the MQC problem, and a few improved search techniques, especially a lookahead scheme, to solve the problem optimally. The theoretical running time analysis of the algorithm is provided, and an extensive simulation study has been well designed to compare the algorithm to previous existing exact algorithms and a best heuristics Hypercleaning. The experimental results on both synthetic and real datasets show that the proposed algorithm outperformed other exact algorithms, and it was competitive to Hypercleaning on many datasets. | TRID-ID TR05-05

  • Date created
  • Subjects / Keywords
  • Type of Item
  • DOI
  • License
    Attribution 3.0 International