Refining phylogenetic trees given additional data: An algorithm based on parsimony

Taoyang Wu; Vincent Moulton; Mike Steel

doi:10.1109/TCBB.2008.100

Refining phylogenetic trees given additional data: An algorithm based on parsimony

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

5 Citations (Scopus)

Abstract

Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.

Original language	English
Pages (from-to)	118-125
Number of pages	8
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	6
Issue number	1
DOIs	https://doi.org/10.1109/TCBB.2008.100
Publication status	Published - 2009

Access to Document

10.1109/TCBB.2008.100

Cite this

@article{b323431547b04b709721625febf16388,

title = "Refining phylogenetic trees given additional data: An algorithm based on parsimony",

abstract = "Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.",

author = "Taoyang Wu and Vincent Moulton and Mike Steel",

year = "2009",

doi = "10.1109/TCBB.2008.100",

language = "English",

volume = "6",

pages = "118--125",

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

issn = "1545-5963",

publisher = "The Institute of Electrical and Electronics Engineers (IEEE)",

number = "1",

}

TY - JOUR

T1 - Refining phylogenetic trees given additional data: An algorithm based on parsimony

AU - Wu, Taoyang

AU - Moulton, Vincent

AU - Steel, Mike

PY - 2009

Y1 - 2009

N2 - Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.

AB - Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.

U2 - 10.1109/TCBB.2008.100

DO - 10.1109/TCBB.2008.100

M3 - Article

SN - 1545-5963

VL - 6

SP - 118

EP - 125

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

IS - 1

ER -