Please use this identifier to cite or link to this item: https://doi.org/10.1093/bioinformatics/bty594
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
Technology
Physical Sciences
Biochemical Research Methods
Biotechnology & Applied Microbiology
Computer Science, Interdisciplinary Applications
Mathematical & Computational Biology
Statistics & Probability
Biochemistry & Molecular Biology
Computer Science
Mathematics
INFERENCE
TREE
Issue Date: 1-Sep-2018
Publisher: OXFORD UNIV PRESS
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. https://doi.org/10.1093/bioinformatics/bty594
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.
Source Title: 17th European Conference on Computational Biology (ECCB)
URI: https://scholarbank.nus.edu.sg/handle/10635/156494
ISSN: 1367-4803
1460-2059
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

CLOSED

Published

SCOPUSTM   
Citations

4
checked on Apr 15, 2021

Page view(s)

171
checked on Apr 16, 2021

Download(s)

1
checked on Apr 16, 2021

Google ScholarTM

Check

Altmetric


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