Tree enumeration modulo a consensus
Tóm tắt
The number of trees withn labeled terminal vertices grows too rapidly withn to permit exhaustive searches for Steiner trees or other kinds of optima in cladistics and related areas Often, however, structured constraints are known and may be imposed on the set of trees to be scanned These constraints may be formulated in terms of a consensus among the trees to be searched We calculate the reduction in the number of trees to be enumerated as a function of properties of the imposed consensus
Tài liệu tham khảo
AHO, A V, SAGIV, Y , SZYMANSKI, T G , and ULLMAN, J D (1981), “Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions,”SIAM Journal on Computing, 10, 405–421
BUNEMAN, P (1971), “The Recovery of Trees from Measures of Similarity,” inMathematics in the Archaeological and Historical Sciences, eds F R Hodson, D G Kendall, and P Tautu, Edinburgh: Edinburgh University Press, 387–395
CAMIN, J H, and SOKAL, R R (1965), “A Method for Deducing Branching Sequences in Phylogeny,”Evolution, 19, 311–326
FARRIS, J S (1970), “Methods for Computing Wagner Trees,”Systematic Zoology, 19, 83–92
FARRIS, J S (1977), “Phylogenetic Analysis under Dollo's Law,”Systematic Zoology, 26, 77–88
FELSENSTEIN, J (1978), “The Number of Evolutionary Trees,”Systematic Zoology, 27, 27–33
GORDON, A D (1986), “Consensus Supertrees: The Synthesis of Rooted Trees Containing Overlapping Sets of Labeled Leaves,”Journal of Classification, 3, xx-xx
GRAHAM, R L, and FOULDS, L R (1982), “Unlikelihood that Minimal Phylogenies for a Realistic Biological Study can be Constructed in Reasonable Computational Time,”Mathematical Biosciences, 60, 133–142
GRAY, M W, SANKOFF, D, and CEDERGREN, R J (1984), “On the Evolutionary Descent of Organisma and Organelles: A Global Phylogeny Based on a Highly Conserved Structural Core in Small Subunit Ribosomal RNA,”Nucleic Acids Research, 12, 5837–5852
LANCE, G N, and WILLIAMS, W T (1967), “A General Theory of Classificatory Sorting Strategies I Hierarchical Systems,”Computer Journal, 9, 231–239
LE QUESNE, W J (1974), “The Uniquely Evolved Character Concept and its Cladistic Application,”Systematic Zoology, 23, 513–517
ROHLF, F J (1982), “Consensus Indices for Comparing Classifications,”Mathematical Biosciences, 59, 131–144
SANKOFF, D, CEDERGREN, R J , and MCKAY, W (1982), “A Strategy for Sequence Phylogeny Research,”Nucleic Acids Research, 10, 421–431
WATERMAN, M S, and SMITH, T F (1978), “On the Similarity of Dendrograms,”Journal of Theoretical Biology, 73, 789–800