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

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.

A program for verification of phylogenetic network models.

MOTIVATION: Genetic material is transferred in a non-reproductive manner across species more frequently than commonly thought, particularly in the bacteria kingdom. On one hand, extant genomes are thus more properly considered as a fusion product of both reproductive and non-reproductive genetic transfers. This has motivated researchers to adopt phylogenetic networks to study genome evolution. On the other hand, a gene's evolution is usually tree-like and has been studied for over half a century. Accordingly, the relationships between phylogenetic trees and networks are the basis for the reconstruction and verification of phylogenetic networks. One important problem in verifying a network model is determining whether or not certain existing phylogenetic trees are displayed in a phylogenetic network. This problem is formally called the tree containment problem. It is NP-complete even for binary phylogenetic networks. RESULTS: We design an exponential time but efficient method for determining whether or not a phylogenetic tree is displayed in an arbitrary phylogenetic network. It is developed on the basis of the so-called reticulation-visible property of phylogenetic networks. AVAILABILITY AND IMPLEMENTATION: A C-program is available for download on http://www.math.nus.edu.sg/∼matzlx/tcp_package CONTACT: matzlx@nus.edu.sg SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Compression of Phylogenetic Networks and Algorithm for the Tree Containment Problem.

Rooted phylogenetic networks are rooted acyclic digraphs. They are used to model complex evolution where hybridization, recombination, and other reticulation events play a role. A rigorous definition of network compression is introduced on the basis of recent studies of relationships between cluster, tree, and rooted phylogenetic networks. The concept reveals new connections between well-studied network classes, including tree-child networks and reticulation-visible networks. It also enables us to define a new class of networks for which the cluster containment problem is solvable in linear time.