The MAP test for multimodality

We introduce a test for detecting multimodality in distributions based on minimal constrained spanning trees. We define a Minimal Ascending Path Spanning Tree (MAPST) on a set of points as a spanning tree that has the minimal possible sum of lengths of links with the constraint that starting from any link, the lengths of the links are non-increasing towards a root node. We define similarly MAPSTs with more than one root. We present some algorithms for finding such trees. Based on these trees, we devise a test for multimodality, called the MAP Test (for Minimal Ascending Path). Using simulations, we estimate percentage points of the MAP statistic and assess the power of the test. Finally, we illustrate the use of MAPSTs for determining the number of modes in a distribution of positions of galaxies on photographic plates from a rich galaxy cluster.     

Minimum Tree Cost Quartet Puzzling

We present a new distance based quartet method for phylogenetic tree reconstruction, called Minimum Tree Cost Quartet Puzzling. Starting from a distance matrix computed from natural data, the algorithm incrementally constructs a tree by adding one taxon at a time to the intermediary tree using a cost function based on the relaxed 4-point condition for weighting quartets. Different input orders of taxa lead to trees having distinct topologies which can be evaluated using a maximum likelihood or weighted least squares optimality criterion. Using reduced sets of quartets and a simple heuristic tree search strategy we obtain an overall complexity of O(n ⁵ log₂ n) for the algorithm. We evaluate the performances of the method through comparative tests and show that our method outperforms NJ when a weighted least squares optimality criterion is employed. We also discuss the theoretical boundaries of the algorithm.     

中国古代牡丹谱录研究

牡丹在中国传统名花中独领群芳,在中华民族的心目中占有很高的地位。在中国悠久的花文化历史长河中产生了众多的牡丹谱录。本文在总结前人对中国古代牡丹谱录研究状况的基础上,通过查阅古籍文献进一步考证了中国古代牡丹谱录的数量和存世状况。结果表明,中国历史上有记载的牡丹谱录共计41部,现尚存世16部,按内容可以将其分为品种谱和综合谱两大类。中国古代牡丹谱录的体例历代各不相同,主要包含序、正文、附记和跋四个部分。现尚存于世的16部古代牡丹谱录的内容和形式丰富多样,对中国古代牡丹文化的研究以及现代牡丹的育种与栽培技术研究具有重要参考价值。     

Minimum spanning trees for tree metrics: abridgements and adjustments

Two properties of tree metrics are already known in the literature: tree metrics on a setX withn elements have 2n?3 degrees of freedom; a tree metric has Robinson form with regard to its minimum spanning tree (MST), or to any such MST if several of them exist. Starting from these results, we prove that a tree metrict is entirely defined by its restriction to some setB of 2n?3 entries. This set is easily determined from the table oft and includes then?1 entries of an MST. A fast method for the adjustment of a tree metric to any given metricd is then obtained. This method extends to dissimilarities.     

Statistical theory in clustering

A number of statistical models for forming and evaluating clusters are reviewed. Hierarchical algorithms are evaluated by their ability to discover high density regions in a population, and complete linkage hopelessly fails; the others don't do too well either. Single linkage is at least of mathematical interest because it is related to the minimum spanning tree and percolation. Mixture methods are examined, related to k-means, and the failure of likelihood tests for the number of components is noted. The DIP test for estimating the number of modes in a univariate population measures the distance between the empirical distribution function and the closest unimodal distribution function (or k-modal distribution function when testing for k modes). Its properties are examined and multivariate extensions are proposed. Ultrametric and evolutionary distances on trees are considered briefly.Research supported by the National Science Foundation Grant No. MCS-8102280.     

宋代牡丹谱考释

中国宋代涌现了众多谱录类著作,其中牡丹谱共计17种,几乎占花卉谱录总数的一半,它们也是其他花卉谱录出现的前导性著作。目前,仅7部牡丹谱存世,而其他因失传已经难以确切知其具体内容。文章对包括已佚在内的17种牡丹谱进行了详细考释,包括作者经历、成书时间、书中记述的内容和结构。新颖之处在于:(1)通过对作者经历的调查,不仅明确了作者的社会地位、官位和著书环境等问题,还探明了一些作者之间的人际关系。(2)更精确推定成书年代,并按时间顺序将牡丹谱进行排序,从而解析出牡丹的品种以及栽培地域的变化。其结果显示,牡丹谱所载牡丹的品种和数量并不是单纯按照时间的推移而递增的,但考察各种谱录所载的品种名称时,可以了解到各种谱录总载有新的品种。宋代人不断地追求新品牡丹的同时,遗弃旧的品种,因此,各种谱录所载的品数并没有明显的增加。(3)通过研究现存7部牡丹谱的结构及内容,可以大致了解到各种谱录除了大多记载当时的名品之外,还记录了花圃、风俗、栽培技术等内容,以便传于后代。另外,谱录作者主要为宋代士大夫,他们对于出现新品种等问题怀有个人的哲学性思考。这种思考往往涉及到掌管自然现象的"造物"和"造化",并相信它影响了牡丹的变异。文章还从文献学角度介绍了现存7部牡丹谱的早期版本,并指出最可靠的善本。     

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 reduction algorithm for approximating a (nonmetric) dissimilarity by a tree distance

We propose a development stemming from Roux (1988). The principle is progressively to modify the dissimilarities so that every quadruple satisfies not only the additive inequality, as in Roux's method, but also all triangle inequalities. Our method thus ensures that the results are tree distances even when the observed dissimilarities are nonmetric. The method relies on the analytic solution of the least-squares projection onto a tree distance of the dissimilarities attached to a single quadruple. This goal is achieved by using geometric reasoning which also enables an easy proof of algorithm's convergence. This proof is simpler and more complete than that of Roux (1988) and applies to other similar reduction methods based on local least-squares projection. The method is illustrated using Case's (1978) data. Finally, we provide a comparative study with simulated data and show that our method compares favorably with that of Studier and Keppler (1988) which follows in the ADDTREE tradition (Sattath and Tversky 1977). Moreover, this study seems to indicate that our method's results are generally close to the global optimum according to variance accounted for.We offer sincere thanks to Gilles Caraux, Bernard Fichet, Alain Guénoche, and Maurice Roux for helpful discussions, advice, and for reading the preliminary versions of this paper. We are grateful to three anonymous referees and to the editor for many insightful comments. This research was supported in part by the GREG and the IA² network.     

The Factorial Minimum Spanning Tree as a Reference for a Synthetic Index of Complex Phenomena

This paper is aimed at combining both the properties of factorial subspaces and those of the Minimum Spanning Tree Algorithm (MST) to obtain a reference structure (the Maximum Path) in which the statistical units are in reduced subordering. The coordinates (factor scores) of the statistical units in a multi-factorial subspace through Principal Component Analysis are the basis for the Minimum Spanning Tree. In the MST, we single out a path of maximum length. On the Maximum Path each graduation obtained for the unit can be used as a Synthetic Index of the phenomenon analyzed. Two distinct strategies lead to the choice of the subspace in which we have the best representation of the units in the Maximum Path. The validity of the method is confirmed by results achieved in various applications to real data.     

TreeOfTrees Method to Evaluate the Congruence Between Gene Trees

A new method, TreeOfTrees, is proposed to compare X-tree structures obtained from several sets of aligned gene sequences of the same taxa. Its aim is to detect genes or sets of genes having different evolutionary histories. The comparison between sets of trees is based on several tree metrics, leading to a unique tree labelled by the gene trees. The robustness values of its edges are estimated by bootstrapping and consensus procedures that allow detecting subsets of genes having differently evolved. Simulations are performed under various evolutionary conditions to test the efficiency of the method and an application on real data is described. Tests of arboricity and various consensus algorithms are also discussed. A corresponding software package is available.     

A graph-theoretic method for organizing overlapping clusters into trees,multiple trees,or extended trees

A clustering that consists of a nested set of clusters may be represented graphically by a tree. In contrast, a clustering that includes non-nested overlapping clusters (sometimes termed a “nonhierarchical” clustering) cannot be represented by a tree. Graphical representations of such non-nested overlapping clusterings are usually complex and difficult to interpret. Carroll and Pruzansky (1975, 1980) suggested representing non-nested clusterings with multiple ultrametric or additive trees. Corter and Tversky (1986) introduced the extended tree (EXTREE) model, which represents a non-nested structure as a tree plus overlapping clusters that are represented by marked segments in the tree. We show here that the problem of finding a nested (i.e., tree-structured) set of clusters in an overlapping clustering can be reformulated as the problem of finding a clique in a graph. Thus, clique-finding algorithms can be used to identify sets of clusters in the solution that can be represented by trees. This formulation provides a means of automatically constructing a multiple tree or extended tree representation of any non-nested clustering. The method, called “clustrees”, is applied to several non-nested overlapping clusterings derived using the MAPCLUS program (Arabie and Carroll 1980).     

On the Complexity of Ordinal Clustering

Given a set of pairwise distances on a set of n points, constructing an edgeweighted tree whose leaves are these n points such that the tree distances would mimic the original distances under some criteria is a fundamental problem. One such criterion is to preserve the ordinal relation between the pairwise distances. The ordinal relation can be of the form of total order on the distances or it can be some partial order specified on the pairwise distances. We show that the problem of finding a weighted tree, if it exists, which would preserve the total order on pairwise distances is NP-hard. We also show the NP-hardness of the problem of finding a weighted tree which would preserve a particular kind of partial order called a triangle order, one of the most fundamental partial orders considered in computational biology.     

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.     

Invariants of phylogenies in a simple case with discrete states

Under a simple model of transition between two states, we can work out the probabilities of different data outcomes in four species with any given phylogeny. For a given tree topology, if all characters are evolving under the same probabilistic model, there are two quadratic forms in the frequencies of outcomes that must be zero. It may be possible to test the null hypothesis that the tree is of a particular topology by testing whether these quadratic forms are zero. One of the tests is a test for independence in a simple 2×2 contingency table. If there are differences of evolutionary rate among characters, these quadratic forms will no longer necessarily be zero.     

拉姆齐测验:一个新的解释思路

拉姆齐测验描述了人们决定接受p后,是不是接受q,从而对他的其它信念作最小修正的问题。20世纪60年代后,学界对这种思想进行了不同的解释,从总体上看,主要有两种:简单的拉姆齐测验和精致的拉姆齐测验。在分析这两种观点的基础上,我们认为这两种解释都存在一定的问题,在本文中,我们提出了一个基于拉姆齐测验的新的逻辑解释思路。     

Quantitative properties of the evolution and classification of languages

Statistical analyses of a published phylogenetic classification of languages show some properties attributable to taxonomic methods and others that reflect the nature of linguistic evolution. The inferred phylogenetic tree is less well resolved and more asymmetric at the highest taxonomic ranks, where the tree is constructed mainly by phenetic methods. At lower ranks, where cladistic methods are more prevalent, the asymmetry of well resolved parts of the tree is consistent with a stochastic birth and death process in which languages originate and become extinct at constant rates, although poorly resolved parts of the tree are still more asymmetric than predicted. Other tests applied to a sample of historically recorded languages reveal substantial fluctuations in the rates of origination and extinction, with both rates temporarily reduced when languages enter the historical record. For languages in general, the average origination rate is estimated to be only slightly higher than the average extinction rate, which in turn corresponds to an average lifetime of about 500 years or less.This research was suported by a grant from the UCLA Academic Senate and by computer time from the UCLA Office of the Academic Computing. I thank Merritt Ruhlen, Joseph B. Slowinski, and Thomas D. Wickens for helpful information and suggestions.     

On Classification and Regression Trees for Multiple Responses and Its Application

In many application fields, multivariate approaches that simultaneously consider the correlation between responses are needed. The tree method can be extended to multivariate responses, such as repeated measure and longitudinal data, by modifying the split function so as to accommodate multiple responses. Recently, researchers have constructed some decision trees for multiple continuous longitudinal response and multiple binary responses using Mahalanobis distance and a generalized entropy index. However, these methods have limitations according to the type of response, that is, those that are only continuous or binary. In this paper, we will modify the tree for univariate response procedure and suggest a new tree-based method that can analyze any type of multiple responses by using GEE (generalized estimating equations) techniques. To compare the performance of trees, simulation studies on selection probability of true split variable will be shown. Finally, applications using epileptic seizure data and WWW data are introduced.     

Least squares algorithms for constructing constrained ultrametric and additive tree representations of symmetric proximity data

A mathematical programming algorithm is developed for fitting ultrametric or additive trees to proximity data where external constraints are imposed on the topology of the tree. The two procedures minimize a least squares loss function. The method is illustrated on both synthetic and real data. A constrained ultrametric tree analysis was performed on similarities between 32 subjects based on preferences for ten odors, while a constrained additive tree analysis was carried out on some proximity data between kinship terms. Finally, some extensions of the methodology to other tree fitting procedures are mentioned.The first author is supported as Bevoegdverklaard Navorser of the Belgian Nationaal Fonds voor Wetenschappelijk Onderzoek.     

Comments on a Paper on Alleged Misconceptions Regarding the History of Analysis: Who Has Misconceptions?

This comment is analysing the last section of a paper by Piotr Blaszczyk, Mikhail G. Katz, and David Sherry on alleged misconceptions committed by historians of mathematics regarding the history of analysis, published in this journal in the first issue of 2013. Since this section abounds of wrong attributions and denouncing statements regarding my research and a key publication, the comment serves to rectify them and to recall some minimal methodological requirements for historical research.