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

N1 - Funding Information:
i” Full version of a paper presented at the 6th (1995) Annual Symposium on Combinatorial Pattern Matching. * Corresponding author. E-mail: tandy@central.as.npenn.edn. ’ This work was performed at Sandia National Laboratories supported by the US Department of Energy under contract DE-AC04-76AL85000. *Part of this work was supported by the ESPRIT Haslc Research ActIon Programme of the K under contract 7141 (project ALCOM-IT). 3 This work was supported in part by NSF grants CCR-9457800 and SBR-95120Y2, by an AR0 grant DAAL0389-C0031, by the Institute for Research in Cognitive Science at the University of Pennsylvania, by the US Department of Energy under contract DE-AC04-76AL85000, and by generous financial support from Paul Angello.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

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

T2 - 6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995

Y2 - 5 July 1995 through 7 July 1995

ER -