Search

Defining and computing distances between tree structures is a classical area of study in theoretical computer science, with practical applications in the areas of computational biology, information retrieval, text analysis, and many others. In this paper, we focus on rooted, unordered, uniquely-labelled trees such as taxonomies and other hierarchies. For trees as these, we introduce the intuitive concept of a ‘local move’ operation as an atomic edit of a tree. We then introduce SuMoTED, a new edit distance measure between such trees, defined as the minimal number of local moves required to convert one tree into another. We show how SuMoTED can be computed using a scalable algorithm with quadratic time complexity. Finally, we demonstrate its use on a collection of music genre taxonomies.

Automation of chromosome analysis has long been considered as a difficult task However the advent of Multiplex Fluorescence In Situ Hybridization (M-FISH) made the analysis of chromosomes much easier. Nevertheless, the chromosomes in an M-FISH image do very often partially occlude each other: hence, their segmentation is not trivial and requires the application of a dedicated procedure. In this paper a method is presented for the segmentation of touching and overlapping groups of chromosomes in M-FISH images. Initially, the watershed transform is applied and the image is decomposed into watershed regions. Next, gradient paths starting from points of high concavity are computed for each produced region. Finally, adjacent regions are merged producing the final chromosome areas. To validate our method a benchmark database of 183 M-FISH images has been used. The proposed algorithm resulted in a 90.6% success rate for touching chromosomes and 80.4% for overlapping groups of chromosomes. (C) 2010 Elsevier B.V. All rights reserved. Pattern Recognition Letters

In this paper, we propose a signature verification system based on Dynamic Time Warping (DTW). The method works by extracting the vertical projection feature from signature images and by comparing reference and probe feature templates using elastic matching. Modifications are made to the basic DTW algorithm to account for the stability of the various components of a signature. The basic DTW and the modified DTW methods are tested on a signature database of 100 people. The modified DTW algorithm, which incorporates stability, has an equal-error-rate of only 2% in comparison to 29% for the basic DTW method. � 2007 Elsevier B.V. All rights reserved.

In this paper, an evolutionary programming-based clustering algorithm is proposed. The algorithm effectively groups a given set of data into an optimum number of clusters. The proposed method is applicable for clustering tasks where clusters are crisp and spherical. This algorithm determines the number of clusters and the cluster centers in such a way that locally optimal solutions are avoided. The result of the algorithm does not depend critically on the choice of the initial cluster centers. ? 1997 Published by Elsevier Science B.V.