Variation of substitution rates across sites is widespread among biological sequences. A gamma distribution, defined by a shape parameter, is generally used to model this phenomenon. We propose here a new method to estimate an efficient value of the gamma shape parameter, i.e., the value that is best suited for tree topology estimation. We show that (1) efficient values lead to underestimate the rate variability and (2) the tree topologies that are obtained are more accurate than those deduced from the true (unknown) values of the parameter. Exploring the tree space is another important issue in phylogenetic inference. We propose a new approach for building maximum likelihood phylogenies. The core of this method is a simple hill climbing algorithm that adjusts tree topology and branch lengths simultaneously. We show that this approach reconstructs very accurate tree topologies from data sets containing hundreds of taxa. The speed of this method also greatly facilitates bootstrap analysis.
