Please use this identifier to cite or link to this item:
Title: S-Cluster plus plus : a fast program for solving the cluster containment problem for phylogenetic networks
Authors: Yan, Hongwei 
Gunawan, Andreas DM 
Zhang, Louxin 
Keywords: Science & Technology
Life Sciences & Biomedicine
Physical Sciences
Biochemical Research Methods
Biotechnology & Applied Microbiology
Computer Science, Interdisciplinary Applications
Mathematical & Computational Biology
Statistics & Probability
Biochemistry & Molecular Biology
Computer Science
Issue Date: 1-Sep-2018
Citation: Yan, Hongwei, Gunawan, Andreas DM, Zhang, Louxin (2018-09-01). S-Cluster plus plus : a fast program for solving the cluster containment problem for phylogenetic networks. 17th European Conference on Computational Biology (ECCB) 34 (17) : 680-686. ScholarBank@NUS Repository.
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∼matzlx/ccp.
Source Title: 17th European Conference on Computational Biology (ECCB)
ISSN: 1367-4803
DOI: 10.1093/bioinformatics/bty594
Appears in Collections:Elements
Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
bty594.pdf458.61 kBAdobe PDF




checked on Apr 15, 2021

Page view(s)

checked on Apr 16, 2021


checked on Apr 16, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.