Motivation: Maximum likelihood (ML) methods have become very popular for constructing phylogenetic trees from sequence data. However, despite noticeable recent progress, with large and difficult datasets (e.g. multiple genes with conflicting signals) current ML programs still require huge computing time and can become trapped in bad local optima of the likelihood function. When this occurs, the resulting trees may still show some of the defects (e.g. long branch attraction) of starting trees obtained using fast distance or parsimony programs. Methods: Subtree pruning and regrafting (SPR) topological rearrangements are usually sufficient to intensively search the tree space. Here, we propose two new methods to make SPR moves more efficient. The first method uses a fast distance-based approach to detect the least promising candidate SPR moves, which are then simply discarded. The second method locally estimates the change in likelihood for any remaining potential SPRs, as opposed to globally evaluating the entire tree for each possible move. These two methods are implemented in a new algorithm with a sophisticated filtering strategy, which efficiently selects potential SPRs and concentrates most of the likelihood computation on the promising moves. Results: Experiments with real datasets comprising 35–250 taxa show that, while indeed greatly reducing the amount of computation, our approach provides likelihood values at least as good as those of the best-known ML methods so far and is very robust to poor starting trees. Furthermore, combining our new SPR algorithm with local moves such as PHYML's nearest neighbor interchanges, the time needed to find good solutions can sometimes be reduced even more. Availability: Executables of our SPR program and the used datasets are available for download at Contact:gascuel@lirmm.fr; wim@santafe.edu

The formation of a self-sustaining autocatalytic chemical network is a necessary but not sufficient condition for the origin of life. The question of whether such a network could form “by chance” within a sufficiently complex suite of molecules and reactions is one that we have investigated for a simple chemical reaction model based on polymer ligation and cleavage. In this paper, we extend this work in several further directions. In particular, we investigate in more detail the levels of catalysis required for a self-sustaining autocatalytic network to form. We study the size of chemical networks within which we might expect to find such an autocatalytic subset, and we extend the theoretical and computational analyses to models in which catalysis requires template matching.

We present a new definition of the concept of representation for cognitive science that is based on a study of the origin of structures that are used to store memory in evolving systems. This study consists of novel computer experiments in the evolution of cellular automata to perform nontrivial tasks as well as evidence from biology concerning generic memory. Our key observation is that representations require inert structures to encode information used to construct appropriate dynamic configurations for the evolving system. We propose criteria to decide if a given structure is a representation by unpacking the idea of inert structures that can be used as memory for arbitrary dynamic configurations. Using a genetic algorithm, we evolved cellular automata rules that can perform nontrivial tasks related to the density task (or majority classification problem) commonly used in the literature. We present the particle catalogs of the new rules following the computational mechanics framework. We discuss if the evolved cellular automata particles may be seen as representations according to our criteria. We show that while they capture some of the essential characteristics of representations, they lack an essential one. Our goal is to show that artificial life can be used to shed new light on the computation-versus-dynamics debate in cognitive science, and indeed function as a constructive bridge between the two camps. Our definitions of representation and cellular automata experiments are proposed as a complementary approach, with both dynamics and informational modes of explanation.