Rapid Evaluation of Least-Squares and Minimum-Evolution Criteria on Phylogenetic Trees

We present fast new algorithms for evaluating trees with respectto least squares and minimum evolution (ME), the most commonlyused criteria for inferring phylogenetic trees from distancedata. The new algorithms include an optimal O(N2) time algorithmfor calculating the edge (branch or internode) lengths on atree according to ordinary or unweighted least squares (OLS);an O(N3) time algorithm for edge lengths under weighted leastsquares (WLS) including the Fitch-Margoliash method; and anoptimal O(N4) time algorithm for generalized least-squares (GLS)edge lengths (where N is the number of taxa in the tree). TheME criterion is based on the sum of edge lengths. Consequently,the edge lengths algorithms presented here lead directly toO(N2), O(N3), and O(N4) time algorithms for ME under OLS, WLS,and GLS, respectively. All of these algorithms are as fast asor faster than any of those previously published, and the algorithmsfor OLS and GLS are the fastest possible (with respect to orderof computational complexity). A major advantage of our new methodsis that they are as well adapted to multifurcating trees asthey are to binary trees. An optimal algorithm for determiningpath lengths from a tree with given edge lengths is also developed.This leads to an optimal O(N2) algorithm for OLS sums of squaresevaluation and corresponding O(N3) and O(N4) time algorithmsfor WLS and GLS sums of squares, respectively. The GLS algorithmis time-optimal if the covariance matrix is already inverted.The speed of each algorithm is assessed analytically—thespeed increases we calculate are confirmed by the dramatic speedincreases resulting from their implementation in PAUP* 4.0.The new algorithms enable far more extensive tree searches andstatistical evaluations (e.g., bootstrap, parametric bootstrap,or jackknife) in the same amount of time. Hopefully, the fastalgorithms for WLS and GLS will encourage the use of these criteriafor evaluating trees and their edge lengths (e.g., for approximatedivergence time estimates), since they should be more statisticallyefficient than OLS.     

Statistical properties of the ordinary least-squares,generalized least-squares,and minimum-evolution methods of phylogenetic inference

Summary Statistical properties of the ordinary least-squares (OLS), generalized least-squares (GLS), and minimum-evolution (ME) methods of phylogenetic inference were studied by considering the case of four DNA sequences. Analytical study has shown that all three methods are statistically consistent in the sense that as the number of nucleotides examined (m) increases they tend to choose the true tree as long as the evolutionary distances used are unbiased. When evolutionary distances (d_ij's) are large and sequences under study are not very long, however, the OLS criterion is often biased and may choose an incorrect tree more often than expected under random choice. It is also shown that the variance-covariance matrix of d_ij's becomes singular as d_ij's approach zero and thus the GLS may not be applicable when d_ij's are small. The ME method suffers from neither of these problems, and the ME criterion is statistically unbiased. Computer simulation has shown that the ME method is more efficient in obtaining the true tree than the OLS and GLS methods and that the OLS is more efficient than the GLS when d_ij's are small, but otherwise the GLS is more efficient.Offprint requests to: M. Nei     

Molecular evolution and structure--function relationships of the superoxide dismutase gene families in angiosperms and their relationship to other eukaryotic and prokaryotic superoxide dismutases

This study assesses whether the phylogenetic relationships between SODs from different organisms could assist in elucidating the functional relationships among these enzymes from evolutionarily distinct species. Phylogenetic trees and intron positions were compared to determine the relationships among these enzymes. Alignment of Cu/ZnSOD amino acid sequences indicates high homology among plant sequences, with some features that distinguish chloroplastic from cytosolic Cu/ZnSODs. Among eukaryotes, the plant SODs group together. Alignment of the Mn and FeSOD amino acid sequences indicates a higher degree of homology within the group of MnSODs (>70%) than within FeSODs (approximately 60%). Tree topologies are similar and reflect the taxonomic classification of the corresponding species. Intron number and position in the Cu/Zn Sod genes are highly conserved in plants. Genes encoding cytosolic SODs have seven introns and genes encoding chloroplastic SODs have eight introns, except the chloroplastic maize Sod1, which has seven. In Mn Sod genes the number and position of introns are highly conserved among plant species, but not among nonplant species. The link between the phylogenetic relationships and SOD functions remains unclear. Our findings suggest that the 5' region of these genes played a pivotal role in the evolution of function of these enzymes. Nevertheless, the system of SODs is highly structured and it is critical to understand the physiological differences between the SODs in response to different stresses in order to compare their functions and evolutionary history.