Minimum-flip supertrees: Complexity and algorithms

Duhong Chen; Oliver Eulenstein; David Fernández-Baca; Michael Sanderson

doi:10.1109/TCBB.2006.26

Minimum-flip supertrees: Complexity and algorithms

Duhong Chen, Oliver Eulenstein, David Fernández-Baca, Michael Sanderson

Research output: Contribution to journal › Article › peer-review

32 Scopus citations

Abstract

The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

Original language	English (US)
Pages (from-to)	165-173
Number of pages	9
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	3
Issue number	2
DOIs	https://doi.org/10.1109/TCBB.2006.26
State	Published - Apr 2006
Externally published	Yes

Keywords

NP-completeness
Phylogenetic tree
Supertree
Tree assembly

ASJC Scopus subject areas

Biotechnology
Genetics
Applied Mathematics

Access to Document

10.1109/TCBB.2006.26

Cite this

@article{21b4a02bb4754f808a28498a822e5df4,

title = "Minimum-flip supertrees: Complexity and algorithms",

abstract = "The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.",

keywords = "NP-completeness, Phylogenetic tree, Supertree, Tree assembly",

author = "Duhong Chen and Oliver Eulenstein and David Fern{\'a}ndez-Baca and Michael Sanderson",

note = "Funding Information: The authors want to thank the anonymous referees, who gave insightful comments that have helped to improve the presentation of this work. The research of authors D. Chen, O. Eulenstein, and M. Sanderson was supported by the US National Science Foundation (NSF) under grant award number 0334832. The research of D. Fern{\'a}ndez-Baca was supported in part by the NSF under grant award numbers CCR9988348 and 0334832.",

year = "2006",

month = apr,

doi = "10.1109/TCBB.2006.26",

language = "English (US)",

volume = "3",

pages = "165--173",

journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",

issn = "1545-5963",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Minimum-flip supertrees

T2 - Complexity and algorithms

AU - Chen, Duhong

AU - Eulenstein, Oliver

AU - Fernández-Baca, David

AU - Sanderson, Michael

N1 - Funding Information: The authors want to thank the anonymous referees, who gave insightful comments that have helped to improve the presentation of this work. The research of authors D. Chen, O. Eulenstein, and M. Sanderson was supported by the US National Science Foundation (NSF) under grant award number 0334832. The research of D. Fernández-Baca was supported in part by the NSF under grant award numbers CCR9988348 and 0334832.

PY - 2006/4

Y1 - 2006/4

N2 - The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

AB - The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

KW - NP-completeness

KW - Phylogenetic tree

KW - Supertree

KW - Tree assembly

UR - http://www.scopus.com/inward/record.url?scp=33646718005&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646718005&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2006.26

DO - 10.1109/TCBB.2006.26

M3 - Article

C2 - 17048402

AN - SCOPUS:33646718005

SN - 1545-5963

VL - 3

SP - 165

EP - 173

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

IS - 2

ER -

Minimum-flip supertrees: Complexity and algorithms

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this