Search

A variety of algorithms have been proposed for reconstructing trees that show the evolutionary relationships between species by comparing differences in genetic data across present-day taxa. If the leaf-to-leaf distances in a tree can be accurately estimated, then it is possible to reconstruct this tree from these estimated distances, using polynomial-time methods such as the popular `Neighbor-Joining' algorithm. There is a precise combinatorial condition under which distance-based methods are guaranteed to return a correct tree (in full or in part) based on the requirement that the input distances all lie within some `safety radius' of the true distances. Here, we explore a stochastic analogue of this condition, and mathematically establish upper and lower bounds on this `stochastic safety radius' for distance-based tree reconstruction methods. Using simulations, we show how this notion provides a new way to compare the performance of distance-based tree reconstruction methods. This may help explain why Neighbor-Joining performs so well, as its stochastic safety radius appears close to optimal (while its more classical safety radius is the same as many other less accurate methods)., 18 pages, 1 figure, 4 tables

In the last few decades, several techniques to randomly generate a deterministic finite automaton have been developed. These techniques have implications in the enumeration and random generation of automata of size n. One of the ways to generate a finite automaton is to generate a random tree and to complete it to a deterministic finite automaton, assuming that the tree will be the automaton's breadth-first spanning tree. In this paper we explore further this method, and the string representation of a tree, and use it to counting the number of automata having a tree as a breadth-first spanning subtrees. We introduce the notions of characteristic and difference sequence of a tree, and define the weight of a tree. We also present a recursive formula for this quantity in terms of the "derivative" of a tree. Finally, we analyze the implications of this formula in terms of exploring trees with the largest and smallest number of automata in the span of the tree and present simple applications for finding densities of subsets of DFAs.

An ordered labeled tree is a tree in which the nodes are labeled and the left-to-right order among siblings is relevant. The edit distance between two ordered labeled trees is the minimum cost of transforming one tree into the other through a sequence of edit operations. We present techniques for speeding up the tree edit distance computation which are applicable to a family of algorithms based on closely related recursion strategies. These techniques aim to reduce repetitious steps in the original algorithms by exploring certain structural features in the tree. When these features exist in a large portion of the tree, the speedup due to our techniques would be significant. Viable examples for application include RNA secondary structure comparison and structured text comparison.

Traditional normalized tree edit distances do not satisfy the triangle inequality. We present a metric normalization method for tree edit distance, which results in a new normalized tree edit distance fulfilling the triangle inequality, under the condition that the weight function is a metric over the set of elementary edit operations with all costs of insertions/deletions having the same weight. We prove that the new distance, in the range [0, 1], is a genuine metric as a simple function of the sizes of two ordered labeled trees and the tree edit distance between them, which can be directly computed through tree edit distance with the same complexity. Based on an efficient algorithm to represent digits as ordered labeled trees, we show that the normalized tree edit metric can provide slightly better results than other existing methods in handwritten digit recognition experiments using the approximating and eliminating search algorithm (AESA) algorithm.

The tree constraint partitions a directed graph into node-disjoint trees. In many practical applications that involve such a partition, there exist side constraints specifying requirements on tree count, node degrees, or precedences and incomparabilities within node subsets. We present a generalisation of the tree constraint that incorporates such side constraints. The key point of our approach is to take partially into account the strong interactions between the tree partitioning problem and all the side constraints, in order to avoid thrashing during search. We describe filtering rules for this extended tree constraint and evaluate its effectiveness on three applications: the Hamiltonian path problem, the ordered disjoint paths problem, and the phylogenetic supertree problem.

We present algorithms for finding the level set tree of a multivariate density estimate. That is, we find the separated components of level sets of the estimate for a series of levels, gather information on the separated components, such as volume and barycenter, and present the information together with the tree structure of the separated components. The algorithm proceeds by first building a binary tree which partitions the support of the density estimate, followed by bottom-up travels of this tree during which we join those parts of the level sets which touch each other. As a byproduct we present an algorithm for evaluating a kernel estimate on a large multidimensional grid. Since we find the barycenters of the separated components of the level sets also for high levels, our method finds the locations of local extremes of the estimate.

A phylogenetic tree represents historical evolutionary relationships between different species or organisms. The space of possible phylogenetic trees is both complex and exponentially large. Here we study combinatorial features of neighbourhoods within this space, with respect to four standard tree metrics. We focus on the splits of a tree: the bipartitions induced by removing a single edge from the tree. We characterize those splits appearing in trees that are within a given distance of the original tree, demonstrating close connections between these splits, the Whitney number of a tree, and the binary characters with a given parsimony length.

For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the $R^*$-tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation.

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.

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.

Given two ordered, labeled trees β and α, to find the distance from tree β to tree α is an important problem in many fields, for example, the pattern recognition field. In this paper, a VLSI algorithm for calculating the tree to tree distance is presented. The computation structure of the algorithm is a 2-D Mesh with the sizem*n and the time isO(m+n), wherem,n are the numbers of nodes of the tree β and tree α, respectively.

Given a tree each of whose terminal vertices is associated with a given point in a compact metric space, the problem is to optimally associate a point in this space to each nonterminal vertex of the tree. The optimality criterion is the minimization of the sum of the lengths, in the metric space, over all edges of the tree. This note shows how a dynamic programming solution to this problem generalizes a number of previously published algorithms in diverse metric spaces, each of which has direct and significant applications to biological systematics or evolutionary theory.

A method is developed which for a given objects by variables data matrix estimates weighted inter-object distances that are optimally suited for either an ultrametric or an additive tree representation. The effectiveness of the method is demonstrated on two synthetic data sets having a known tree structure and on one real data set. In the final section, some possible extensions of the present method are discussed.