A computationally efficient approximation to the nearest neighbor interchange metric

The nearest neighbor interchange (nni) metric is a distance measure providing a quantitative measure of dissimilarity between two unrooted binary trees with labeled leaves. The metric has a transparent definition in terms of a simple transformation of binary trees, but its use in nontrivial problems is usually prevented by the absence of a computationally efficient algorithm. Since recent attempts to discover such an algorithm continue to be unsuccessful, we address the complementary problem of designing an approximation to the nni metric. Such an approximation should be well-defined, efficient to compute, comprehensible to users, relevant to applications, and a close fit to the nni metric; the challenge, of course, is to compromise these objectives in such a way that the final design is acceptable to users with practical and theoretical orientations. We describe an approximation algorithm that appears to satisfy adequately these objectives. The algorithm requires O(n) space to compute dissimilarity between binary trees withn labeled leaves; it requires O(n logn) time for rooted trees and O(n ² logn) time for unrooted trees. To help the user interpret the dissimilarity measures based on this algorithm, we describe empirical distributions of dissimilarities between pairs of randomly selected trees for both rooted and unrooted cases.The Natural Sciences and Engineering Research Council of Canada partially supported this work with Grant A-4142.     

Unclassed matrix shading and optimal ordering in hierarchical cluster analysis

A method is presented for the graphic display of proximity matrices as a complement to the common data analysis techniques of hierarchical clustering. The procedure involves the use of computer generated shaded matrices based on unclassed choropleth mapping in conjunction with a strategy for matrix reorganization. The latter incorporates a combination of techniques for seriation and the ordering of binary trees.Partial support for this research was provided by NIJ Grant #82-IJ-CX-0019 and NSF Grant #SES82-06067. The authors wish to acknowledge the assistance of Professors L.J. Hubert, R.G. Golledge, and W.R. Tobler.     

In memoriam: William Wallace Newby (1902-1977)

W. W. Newby, professor of biology at the University of Utah from 1927 to 1971, was renowned as a great teacher and a clear and forceful writer and for his meticulous research in invertebrate embryology. Ancillary skills were counseling (especially of premedical students), illustrating, wood crafting, and paper preserving. Some of his writings pertained to the history of research in the biological sciences at the University of Utah. His specialty areas in teaching were embryology and genetics, and he served as chairman of the Department of Genetics and Cytology from the year of its creation in 1948 until 1962. The most outstanding example of his research pertained to the early embryology of the echiuroid worm Urechis caupo .         

Algal composition of microbiotic crusts from the Central Desert of Baja California, Mexico

A total of 66 algal species representing 32 genera were recovered from soils of 10 sites in the Catavi?a region of the Central Desert of Baja California, Mexico. The most common species encountered were the cyanophytes Nostoc commune and Schizothrix calcicola , the chlorophyte Myrmecia astigmatica , and the diatoms Hantzschia amphioxys, Hantzschia amphyoxys f. capitata, Luticola cohnii, Luticola mutica , and Pinnularia borealis var. scalarts . Nine species not found in any previous studies of North American desert soils were present in our study sites, including 3 taxa new to science: Cylindrocystis brebissonii var. deserti , var. nov.; Elakatothrix obtusata , sp. nov.; and Fasciculochloris mexicana , sp. nov. Attempts to correlate species composition with soil chemical and physical parameters were unsuccessful apart from a pH effect on cyanobacterial distribution. Overall composition of the soil algal community in the Catavi?a region is distinct from other desert sites we have studies, although some cosmopolitan desert soil taxa were present.     

Oreohelices of Utah, II. Extant status of the Brian Head mountainsnail, Oreohelix parawanensis Gregg, 1941 (Stylommatophora: Oreohelicidae)

The Brian Head mountainsnail, Oreohelix parawanensis , is reported for the 1st time as a living species, and for the 1st time its habitat is described. Preliminary determination of the very limited distribution of this species (≤ 2.3 ha inhabited in ～ 11 ha overall area) is presented. Morphometric data previously had been reported only for the holotype and for 1 topotype; measurements from 37 new specimens as well as 20 paratypes are provided here, and these data show that the lost holotype was not typical of the species. Sizes of reproductive snails and of embryos are also reported.     

Algae of Devils Hole, Nevada, Death Valley National Park

We examined algal flora in the aquatic system of Devils Hole, Nevada. The water is seasonally warm, near neutral in pH, and rich in dissolved carbonate, indicative of deeply circulating groundwater flowing through carbonate rock. Most algae were benthic, with only a few planktonic representatives. Eighty-four terminal identifications in 44 genera were recorded, with diatoms and blue-green algae the most speciose groups. Diatoms were major contributors to the grazing food web. Large, mat-forming filamentous algae have an important influence on the physicochemical and general structure of the benthic substrates in Devils Hole.     

A forecasting comparison of classical and Bayesian methods for modelling logistic diffusion

A Bayesian procedure for forecasting S‐shaped growth is introduced and compared to classical methods of estimation and prediction using three variants of the logistic functional form and annual times series of the diffusion of music compact discs in twelve countries. The Bayesian procedure was found not only to improve forecast accuracy, using the medians of the predictive densities as point forecasts, but also to produce intervals with a width and asymmetry more in accord with the outcomes than intervals from the classical alternative. While the analysis in this paper focuses on logistic growth, the problem is set up so that the methods are transportable to other characterizations of the growth process. Copyright © 2001 John Wiley & Sons, Ltd.     

代价敏感属性约简的自适应分治算法

代价敏感属性约简问题作为经典属性约简问题的自然扩展,将代价引入数据,使得属性约简问题更加具有现实意义。文章基于分治思想,先按列将数据集拆分为若干个互不相交的子数据集,然后对各子数据集进行约简,并把约简后的子数据集多路合并。依次继续执行约简和合并操作,最终得到最小测试代价约简。每个子数据集的大小及子数据集的总个数自适应于各个数据集的规模而非固定不变。为验证算法的有效性,选择四个UCI标准数据集进行实验,并与其他算法进行结果对比。实验结果表明,该算法能在较短时间内获得可接受的结果,更适应实际问题的需要。