Minimizing phylogenetic number to find good evolutionary trees

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 parsimonycriterion 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. We can also compute a fixed-topology 2-phylogeny (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)
Title of host publicationCombinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
EditorsZvi Galil, Esko Ukkonen
PublisherSpringer-Verlag
Pages102-127
Number of pages26
ISBN (Print)3540600442, 9783540600442
DOIs
StatePublished - Jan 1 1995
Event6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland
Duration: Jul 5 1995Jul 7 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume937
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995
CountryFinland
CityEspoo
Period7/5/957/7/95

Fingerprint

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Goldberg, L. A., Goldberg, P. W., Phillips, C. A., Sweedyk, E., & Warnow, T. (1995). Minimizing phylogenetic number to find good evolutionary trees. In Z. Galil, & E. Ukkonen (Eds.), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings (pp. 102-127). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937). Springer-Verlag. https://doi.org/10.1007/3-540-60044-2_38

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

Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. ed. / Zvi Galil; Esko Ukkonen. Springer-Verlag, 1995. p. 102-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 937).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Goldberg, LA, Goldberg, PW, Phillips, CA, Sweedyk, E & Warnow, T 1995, Minimizing phylogenetic number to find good evolutionary trees. in Z Galil & E Ukkonen (eds), Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 937, Springer-Verlag, pp. 102-127, 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995, Espoo, Finland, 7/5/95. https://doi.org/10.1007/3-540-60044-2_38
Goldberg LA, Goldberg PW, Phillips CA, Sweedyk E, Warnow T. Minimizing phylogenetic number to find good evolutionary trees. In Galil Z, Ukkonen E, editors, Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. Springer-Verlag. 1995. p. 102-127. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-60044-2_38
Goldberg, Leslie Ann ; Goldberg, Paul W. ; Phillips, Cynthia A. ; Sweedyk, Elizabeth ; Warnow, Tandy. / Minimizing phylogenetic number to find good evolutionary trees. Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings. editor / Zvi Galil ; Esko Ukkonen. Springer-Verlag, 1995. pp. 102-127 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f68089495bc94630850234899319863b,
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 parsimonycriterion 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. We can also compute a fixed-topology 2-phylogeny (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 = "1995",
month = "1",
day = "1",
doi = "10.1007/3-540-60044-2_38",
language = "English (US)",
isbn = "3540600442",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "102--127",
editor = "Zvi Galil and Esko Ukkonen",
booktitle = "Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings",

}

TY - GEN

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 - 1995/1/1

Y1 - 1995/1/1

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 parsimonycriterion 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. We can also compute a fixed-topology 2-phylogeny (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 parsimonycriterion 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. We can also compute a fixed-topology 2-phylogeny (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=84957868373&partnerID=8YFLogxK

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

U2 - 10.1007/3-540-60044-2_38

DO - 10.1007/3-540-60044-2_38

M3 - Conference contribution

AN - SCOPUS:84957868373

SN - 3540600442

SN - 9783540600442

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 102

EP - 127

BT - Combinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings

A2 - Galil, Zvi

A2 - Ukkonen, Esko

PB - Springer-Verlag

ER -