Inferring phylogenetic trees using pseudo-Boolean optimization

Article type: Research Article

Authors: Miranda, Miguel | Lynce, Inês | Manquinho, Vasco^;

Affiliations: IST/INESC-ID, University of Lisbon, Lisbon, Portugal. E-mails: {miguel, ines, vmm}@sat.inesc-id.pt

Note: [] Corresponding author. E-mail: [email protected]

Abstract: Phylogenetic inference concerns the construction of the most probable tree of evolution, taking into account the knowledge about organisms we have at our disposal. There are various inference methods for building a phylogenetic tree, each with its set of assumptions about what can happen in Nature. Assumptions limit the expressiveness of the methods, but are necessary for making them viable to use. More recently, computational methods are being used to validate results obtained from manual methods. Computational methods allow to address problems that require the analysis of larger sets of data in order to construct more complete phylogenies. In this paper we propose the use of Pseudo-Boolean Optimization (PBO), a well known extension of Propositional Satisfiability (SAT), in order to solve the Maximum Compatibility (MC) problem. Assuming that each organism is associated with a set of characteristics, the goal in the MC problem is to find a phylogenetic tree such that the maximum number of characteristics are compatible. Our contribution is a set of new PBO formulations that improve on the performance of the state of the art tool. Comparative results, using real and generated instances, show that the proposed implementations allow the resolution of problem instances with twice the size of the state of the art implementation.

Keywords: Phylogenetic inference, maximum compatibility, pseudo-Boolean optimization

DOI: 10.3233/AIC-140592

Journal: AI Communications, vol. 27, no. 3, pp. 229-243, 2014