An efficient algorithm for supertrees

Givenk rooted binary treesA ₁, A₂, ..., A_k, with labeled leaves, we generateC, a unique system of lineage constraints on common ancestors. We then present an algorithm for constructing the set of rooted binary treesB, compatible with all ofA ₁, A₂, ..., A_k. The running time to obtain one such supertree isO(k ² n²), wheren is the number of distinct leaves in all of the treesA ₁, A₂, ..., A_k.     

Tree enumeration modulo a consensus

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 consensusThis work was supported in part by the Natural Sciences and Engineering Research Council of Canada through operating grant A8867 to D Sankoff and infrastructure grant A3092 to D Sankoff, R J Cedergren and G Lapalme We are grateful to William H E Day for much encouragement and many helpful suggestions     

A tree · a window · a hill; generalization of nearest-neighbor interchange in phylogenetic optimization

The method of nearest-neighbor interchange effects local improvements in a binary tree by replacing a 4-subtree by one of its two alternatives if this improves the objective function. We extend this to k-subtrees to reduce the number of local optima. Possible sequences of k-subtrees to be examined are produced by moving a window over the tree, incorporating one edge at a time while deactivating another. The direction of this movement is chosen according to a hill-climbing strategy. The algorithm includes a backtracking component. Series of simulations of molecular evolution data/parsimony analysis are carried out, fork=4, ..., 8, contrasting the hill-climbing strategy to one based on a random choice of next window, and comparing two stopping rules. Increasing window sizek is found to be the most effective way of improving the local optimum, followed by the choice of hill-climbing over the random strategy. A suggestion for achieving higher values ofk is based on a recursive use of the hill-climbing strategy.Acknowledgments: This work was supported in part by grants to the first author from the Natural Sciences and Engineering Research Council (Canada) and theFonds pour la formation de chercheurs et l'aide à la recherche (Québec), and to the third author from the Danish Research Council. The first author is a fellow of the Canadian Institute for Advanced Research. Much of the research was carried out in the spring of 1991 while the first author was visiting the University of Geneva; warmest thanks are due Professor Claude Weber for this opportunity.     

The inference of hierarchical schemes for multinomial data

Data in an experimental array where a nominal dependent variable hasm>2 outcomes may be accounted for by one of a number of possible schemes consisting ofJ successive and/or parallel independentm _i-nomial experiments where m _i =m +J – 1. Each such scheme can be represented by a tree diagram which is presumed to be valid everywhere in the array. A criterion based on likelihood is defined to assess the different schemes. The set of outcome probabilities of a scheme is shown to differ from that of all other schemes almost everywhere in the space of parameters. As sample size increases, the probability of correctly inferring the true tree tends to 1. Using Monte-Carlo simulation of the four-outcome case, we illustrate, for small sample sizes, how this probability depends on the parameters.

---

Résumé Une famille de modèles est proposée pour analyser un ensemble de données dont les observations sont faites sur une variable réponse discrète et sur un vecteur explicatif. Chaque modèle est constitué d'une série d'expériences multinomiales dont les résultats sont des regroupements de modalités de la variable réponse. Les probabilités d'observer ces regroupements dépendent du vecteur explicatif selon des équations logistique-lin éaires. On prouve facilement que chaque modèle de cette famille contient le même nombre de paramètres. De plus chaque modèle correspond à une structure d'arbres qui classifie hiérarchiquement les modalités de la variable réponse: un noeud non terminal de l'arbre représente une de ces expériences multinomiales et un noeud terminal représente une modalité.

---

Ainsi la probabilité d'observer une de ces modalités est calculée en parcourant le chemin reliant la racine au noeud terminal représentant cette modalité et le choix du modèle est basé sur un critère de vraisemblance calculée comme le produit des vraisemblances évaluées à partir de l'ensemble de données pour chaque noeud non terminal de l'arbre. On démontre que la capacité de prédiction des modalités diffère pour chaque arbre et seul le vrai arbre peut exhiber les vraies probabilités sur presque tout l'espace paramétrique. On y démontre aussi des propriétés asymptotiques du critère qui assurent que le vrai modèle est choisi par ce critère avec probabilité 1. Une étude par simulation Monte-Carlo illustre, dans le cas de petits échantillons, la dépendance de la probabilité que le vrai modèle soit choisi sur les valeurs des paramètres.