Minimizing phylogenetic number to find good evolutionary trees

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Elizabeth Sweedyk, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

Inferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems.

Original languageEnglish (US)
Pages (from-to)111-136
Number of pages26
JournalDiscrete Applied Mathematics
Volume71
Issue number1-3
DOIs
StatePublished - Dec 5 1996
Externally publishedYes

Fingerprint

Evolutionary Tree
Phylogenetics
Topology
Polynomials
Parsimony
Phylogeny
Phylogenetic Tree
Computational Biology
Polynomial time
Leaves

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this

Minimizing phylogenetic number to find good evolutionary trees. / Goldberg, Leslie Ann; Goldberg, Paul W.; Phillips, Cynthia A.; Sweedyk, Elizabeth; Warnow, Tandy.

In: Discrete Applied Mathematics, Vol. 71, No. 1-3, 05.12.1996, p. 111-136.

Research output: Contribution to journalArticle

Goldberg, Leslie Ann ; Goldberg, Paul W. ; Phillips, Cynthia A. ; Sweedyk, Elizabeth ; Warnow, Tandy. / Minimizing phylogenetic number to find good evolutionary trees. In: Discrete Applied Mathematics. 1996 ; Vol. 71, No. 1-3. pp. 111-136.
@article{f710deb6d6164947b38300b7461b133a,
title = "Minimizing phylogenetic number to find good evolutionary trees",
abstract = "Inferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems.",
author = "Goldberg, {Leslie Ann} and Goldberg, {Paul W.} and Phillips, {Cynthia A.} and Elizabeth Sweedyk and Tandy Warnow",
year = "1996",
month = "12",
day = "5",
doi = "10.1016/S0166-218X(96)00060-1",
language = "English (US)",
volume = "71",
pages = "111--136",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "1-3",

}

TY - JOUR

T1 - Minimizing phylogenetic number to find good evolutionary trees

AU - Goldberg, Leslie Ann

AU - Goldberg, Paul W.

AU - Phillips, Cynthia A.

AU - Sweedyk, Elizabeth

AU - Warnow, Tandy

PY - 1996/12/5

Y1 - 1996/12/5

N2 - Inferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems.

AB - Inferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems.

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

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

U2 - 10.1016/S0166-218X(96)00060-1

DO - 10.1016/S0166-218X(96)00060-1

M3 - Article

AN - SCOPUS:0004464938

VL - 71

SP - 111

EP - 136

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -