Abstract
Phylogenetics is a science of determining connections between groups of organisms in terms of ancestor/descendent relationships, usually expressed by phylogenetic trees, also called “trees of life”, cladograms, or dendograms. In parsimony approach to reconstruct the phylogenetic trees, the goal is to find the most parsimonious tree, i.e., the tree requiring the smallest number/score of evolutionary steps. For all reasonable measures this problem is NP-hard. Assuming the structure of the tree is given, we are left with, in some cases tractable, problem of “small phylogeny”: how to assign characters to the internal nodes representing extinct species. We propose a new approach together with the corresponding parsimony criteria for working with nonlinear transformation series of states of a character: a character evolution trees. We use tools of structural graph theory to reconcile a character tree with a phylogenetic tree. For this purpose, we introduce two new scoring metrics: the bag cost, analogous to unweighted parsimony, and the arc cost, analogous to weighted parsimony. We will provide several linear time algorithms solving small phylogeny problem while minimizing the above scoring functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Camin, J.H., Sokal, R.R.: A method for deducing branching sequences in phylogeny. Evolution 19, 311–326 (1965)
Doyle, J.J.: Gene trees and species trees: Molecular systematics as onecharacter taxonomy. Systematic Botany 17, 144–163 (1992)
Day, W.I.E., Sankoff, D.: Computational complexity of inferring phylogenies by compatibility. Systematic Zoology 35, 224–229 (1986)
Farris, J.S.: Methods for computing Wagner trees. Systematic Zoology 19, 83–92 (1970)
Farris, J.S.: Outgroups and parsimony. Zoology 31, 314–320 (1982)
Felsenstein, J.: Evolutionary trees from DNA sequences: a maximum likelihood approach. Journal of Molecular Evolution 17, 368–376 (1981)
Foulds, L.R., Graham, R.L.: The Steiner problem in phylogeny is NPcomplete. Advances In Applied mathematics 3, 43–49 (1982)
Fitch, W.M.: Toward defining the course of evolution: Minimum change for a specific tree topology. Systematic Zoology 20, 406–416 (1971)
Fitch, W.M., Margoliash, E.: Construction of phylogenetic trees. Science 155, 279–284 (1967)
Hennig, W.: Phylogenetic Systematics. University of Illinois Press (1966)
Hawkins, J.A., Hughes, C.E., Scotland, R.W.: Primary homology assessment, characters and character states. Cladistics 13, 275–283 (1997)
Harel, D., Tarjan, R.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13, 338–355 (1984)
Lipscomb, D.L.: Parsimony, homology and the analysis of multistate characters. Cladistics 8, 45–65 (1992)
Mickevich, M.F.: Transformation series analysis. Systematic Zoology 31, 461–478 (1982)
Mickevich, M.F., Lipscomb, D.L.: Parsimony and the choice between different transformations for the same character set. Cladistics 7, 111–139 (1991)
Matousek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial k-trees. Journal of Algorithms 108, 343–364 (1992)
Mickevich, M.F., Weller, S.: Evolutionary character analysis: Tracing character change on a cladogram. Cladistics 6, 137–170 (1990)
O’Grady, R.T., Deets, G.B.: Coding mulitistate characters, with special reference to the use of parasites as characters of their hosts. Systematic Zoology 36, 268–279 (1987)
Pogue, M., Michevich, M.F.: Character definitons and character state delineations: the bete noire of phylogenetics. Cladistics 6, 365–369 (1990)
Pamilo, P., Nei, M.: Relationships between gene trees and species trees. Mo. Biol. Evol. 5, 568–583 (1988)
Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree-width. Journal of Algorithms 7, 309–322 (1986)
Sankoff, D.D.: Minimal mutation trees of sequences. SIAM Journal on Applied Mathematics 28, 35–42 (1975)
Sankoff, D., Cedergren, R.: Simultaneous comparisons of three or more sequences related by a tree. In: Sankoff, D., Kruskal, J. (eds.) Time Warp, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, pp. 253–264. Addison Wesley, Reading (1983)
Saitou, N., Imanishi, T.: Relative efficiencies of the Fitch-Margoliash, maximum parsimony, maximum likelihood, minimum-evolution, and neighborjoining methods of phylogenetic tree construction in obtaining the correct tree. Journal of Molecular Evolution 6, 514–525 (1989)
Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution 4, 406–425 (1987)
Tateno, Y., Takezaki, N., Nei, M.: Relative efficiencies of the maximumlikelihood, neighbor-joining and maximum-parsimony methods when substitution rate varies with site. Journal of Molecular Evolution 11, 261–277 (1994)
Wu, C.-I.: Inferences of species phylogeny in relation to segregation of acient polymorphisms. Genetics 127, 429–435 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gupta, A., Maňuch, J., Stacho, L., Zhu, C. (2004). Small Phylogeny Problem: Character Evolution Trees. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds) Combinatorial Pattern Matching. CPM 2004. Lecture Notes in Computer Science, vol 3109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27801-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-27801-6_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22341-2
Online ISBN: 978-3-540-27801-6
eBook Packages: Springer Book Archive