As the amount of sequencing efforts and genomic data volume continue to increase at an accelerated rate, phylogenetic analysis provides an evolutionary context for understanding and interpreting this growing set of complex data. We introduce a novel quartet based method for inferring molecular based phylogeny called hypercleaning* (HC*). The HC* method is based on the hypercleaning (HC) technique, which possesses an interesting property of recovering edges (of a phylogenetic tree) that are best supported by the witness quartet set. HC* extends HC in two regards: i) whereas HC constrains the input quartet set to be unweighted (binary valued), HC* allows any positive valued quartet scores, enabling more informative quartets to be defined. ii) HC* employs a novel collapsing technique which significantly speeds up the inference stage, making it empirically on par with quartet puzzling in terms of speed, while still guaranteeing optimal edge recovery as in HC. This paper is primarily aimed at presenting the algorithmic construction of HC*. We also report some preliminary studies on an implementation of HC* as a potentially powerful approximation scheme for maximum likelihood based inference.

MOTIVATION: Traditional sequence distances require an alignment and therefore are not directly applicable to the problem of whole genome phylogeny where events such as rearrangements make full length alignments impossible. We present a sequence distance that works on unaligned sequences using the information theoretical concept of Kolmogorov complexity and a program to estimate this distance. RESULTS: We establish the mathematical foundations of our distance and illustrate its use by constructing a phylogeny of the Eutherian orders using complete unaligned mitochondrial genomes. This phylogeny is consistent with the commonly accepted one for the Eutherians. A second, larger mammalian dataset is also analyzed, yielding a phylogeny generally consistent with the commonly accepted one for the mammals. AVAILABILITY: The program to estimate our sequence distance, is available at http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenCompress1.htm. The distance matrices used to generate our phylogenies are available at http://www.math.uwaterloo.ca/~mli/distance.html.

Holland's Adaptation in Natural and Artificial Systems largely dealt with how systems, comprised of many self-interested entities, can and should adapt as a whole. This seminal book led to the last 25 years of work in genetic algorithms (GAs) and related forms of evolutionary computation (EC). In recent years, the expansion of the Internet, other telecommunications technologies, and other large scale networks have led to a world where large numbers of semi-autonomous software entities (i.e., agents) will be interacting in an open, universal system. This development cast the importance of Holland's legacy in a new light. This paper argues that Holland's fundamental arguments, and the years of developments that have followed, have a direct impact on systems of general network agents, regardless of whether they explicitly exploit EC. However, it also argues that the techniques and theories of EC cannot be directly transferred to the world of general agents (rather than EC-specific) without examination of effects that are embodied in general software agents. This paper introduces a framework for EC interchanges between general-purpose software agents. Preliminary results are shown that illustrate the EC effects of asynchronous actions of agents within this framework. Building on this framework, coevolutionary agents that interact in a simulated producer/consumer economy are introduced. Using these preliminary results as illustrations, areas for future investigation of embodied EC software agents are discussed.

Inferring evolutionary trees has long been a challenging problem for both biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.

Inferring evolutionary trees has long been a challenging problem both for biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quarter topologies) and then recombining these inferred quarter topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. In fact, this is the first known PTAS for inferring evolutionary trees under any paradigm. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result has particular significance since quartet methods are usually very sensitive to errors in the data. It is shown how quartet cleaning can dramatically increase the accuracy of quartet methods.

The utility of ordinal assertions for infer&g evolutionary trees from sequence data is examined.If M is a difference matrix derived from a set of sequences then "M(s,z) 5 M(s, y)" is an ordinal assertion supported by .&lwhere s, x and g( are sequences.Ordinal assertions are shown to be an accurate and robust source of evolutionary information.The following results are presentedz A method for inf&g @et topology, the Ordinal Quartet iVethod, is introduced Siulations are reported which demonstrate that the Ordkal Quartet Method is signiEcs&ly more accurate and robust than the popular We& Pour-Point Condition Method.This improvement drastically increases the accuracy of quartet recomb&&on methods, such as the Short Quartet Method [lo] and the Q' Method [S] whose accuracy is critidy dependent upon the ability to infer quartet topology accurately.It is also demonstrated that, unlike other quartet inference methods sudh as the Weak FoePoint Condition Method, the Or-wet Method does not require data correction.The first convergence rate analysis for methods utili&g ordinal assertions is presented.The results obtained are notable in that they apply to any method that utilize ordid assertions.