S-Cluster plus plus : a fast program for solving the cluster containment problem for phylogenetic networks

Abstract

© The Author(s) 2018. Published by Oxford University Press. Motivation Comparative genomic studies indicate that extant genomes are more properly considered to be a fusion product of random mutations over generations (vertical evolution) and genomic material transfers between individuals of different lineages (reticulate transfer). This has motivated biologists to use phylogenetic networks and other general models to study genome evolution. Two fundamental algorithmic problems arising from verification of phylogenetic networks and from computing Robinson-Foulds distance in the space of phylogenetic networks are the tree and cluster containment problems. The former asks how to decide whether or not a phylogenetic tree is displayed in a phylogenetic network. The latter is to decide whether a subset of taxa appears as a cluster in some tree displayed in a phylogenetic network. The cluster containment problem (CCP) is also closely related to testing the infinite site model on a recombination network. Both the tree containment and CCP are NP-complete. Although the CCP was introduced a decade ago, there has been little progress in developing fast algorithms for it on arbitrary phylogenetic networks. Results In this work, we present a fast computer program for the CCP. This program is developed on the basis of a linear-time transformation from the small version of the CCP to the SAT problem. Availability and implementation The program package is available for download on http://www.math.nus.edu.sg/∼matzlx/ccp.