In phylogenetics and other areas of classification, the Buneman graph is commonly used to represent a collection of bipartitions or splits of a (finite) set X in order to display evolutionary relationships. The set X usually corresponds to a set of taxa (or species), and the splits are usually derived from molecular sequence data associated to the taxa. One issue with this approach is that missing molecular data can lead to bipartitions of subsets of X or partial splits, instead of splits of the full set X. In this paper, we show that the definition of the Buneman graph can be naturally extended to collections of partial splits of a set X. Just as with splits, we show that the graph so obtained is an X-labeled median graph but, in contrast to the usual Buneman graph, the elements in X are represented by convex subsets of the vertex set of the graph instead of single vertices. We also show that the Buneman graph for a collection of partial splits is closely related to subtree distances. In particular, for a collection S of weighted partial splits that satisfies a certain pairwise compatibility condition, we show that the corresponding edge-weighted Buneman graph is the unique minimal tree that represents the subtree distance d corresponding to S. Moreover, we show that in this special situation the Buneman graph can also be considered as a type of configuration space for the set of all tree-metrics that minimally extend the subtree distance d.

Abstract The generalized circumradius of a set of points $$A\subseteq \mathbb {R}^d$$ A ⊆ R d with respect to a convex body K equals the minimum value of $$\lambda \ge 0$$ λ ≥ 0 such that a translate of $$\lambda K$$ λ K contains A. Each choice of K gives a different function on the set of bounded subsets of $$\mathbb {R}^d$$ R d ; we characterize which functions can arise in this way. Our characterization draws on the theory of diversities, a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalized circumradius to a finite subset of $$\mathbb {R}^d$$ R d . We obtain elegant characterizations in the case that K is a simplex or parallelotope.

Abstract The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.

Split networks are a popular tool for the analysis and visualization of complex evolutionary histories. Every collection of splits (bipartitions) of a finite set can be represented by a split network. Here we characterize which collection of splits can be represented using a planar split network. Our main theorem links these collections of splits with oriented matroids and arrangements of lines separating points in the plane. As a consequence of our main theorem, we establish a particularly simple characterization of maximal collections of these splits.

The Robinson-Foulds (RF) distance is by far the most widely used measure of dissimilarity between trees. Although the distribution of these distances has been investigated for 20 years, an algorithm that is explicitly polynomial time has yet to be described for computing the distribution for trees around a given tree. In this paper, we derive a polynomial-time algorithm for this distribution. We show how the distribution can be approximated by a Poisson distribution determined by the proportion of leaves that lie in "cherries" of the given tree. We also describe how our results can be used to derive normalization constants that are required in a recently proposed maximum likelihood approach to supertree construction.

BACKGROUND: We previously developed GoMiner, an application that organizes lists of 'interesting' genes (for example, under-and overexpressed genes from a microarray experiment) for biological interpretation in the context of the Gene Ontology. The original version of GoMiner was oriented toward visualization and interpretation of the results from a single microarray (or other high-throughput experimental platform), using a graphical user interface. Although that version can be used to examine the results from a number of microarrays one at a time, that is a rather tedious task, and original GoMiner includes no apparatus for obtaining a global picture of results from an experiment that consists of multiple microarrays. We wanted to provide a computational resource that automates the analysis of multiple microarrays and then integrates the results across all of them in useful exportable output files and visualizations. RESULTS: We now introduce a new tool, High-Throughput GoMiner, that has those capabilities and a number of others: It (i) efficiently performs the computationally-intensive task of automated batch processing of an arbitrary number of microarrays, (ii) produces a human-or computer-readable report that rank-orders the multiple microarray results according to the number of significant GO categories, (iii) integrates the multiple microarray results by providing organized, global clustered image map visualizations of the relationships of significant GO categories, (iv) provides a fast form of 'false discovery rate' multiple comparisons calculation, and (v) provides annotations and visualizations for relating transcription factor binding sites to genes and GO categories. CONCLUSION: High-Throughput GoMiner achieves the desired goal of providing a computational resource that automates the analysis of multiple microarrays and integrates results across all of the microarrays. For illustration, we show an application of this new tool to the interpretation of altered gene expression patterns in Common Variable Immune Deficiency (CVID). High-Throughput GoMiner will be useful in a wide range of applications, including the study of time-courses, evaluation of multiple drug treatments, comparison of multiple gene knock-outs or knock-downs, and screening of large numbers of chemical derivatives generated from a promising lead compound.

The comparison of the gene orders in a set of genomes can be used to infer their phylogenetic relationships and to reconstruct ancestral gene orders. For three genomes this is done by solving the "median problem for breakpoints"; this solution can then be incorporated into a routine for estimating optimal gene orders for all the ancestral genomes in a fixed phylogeny. For the difficult (and most prevalent) case where the genomes contain partially different sets of genes, we present a general heuristic for the median problem for induced breakpoints. A fixed-phylogeny optimization based on this is applied in a phylogenetic study of a set of completely sequenced protist mitochondrial genomes, confirming some of the recent sequence-based groupings which have been proposed and, conversely, confirming the usefulness of the breakpoint method as a phylogenetic tool even for small genomes.

We present fast new algorithms for phylogenetic reconstruction from distance data or weighted quartets. The methods are conservative-they will only return edges that are well supported by the input data. This approach is not only philosophically attractive; the conservative tree estimate can be used as a basis for further tree refinement or divide and conquer algorithms. The capability to process quartet data allows these algorithms to be used in tandem with ordinal or qualitative phylogenetic analysis methods. We provide algorithms for three standard conservative phylogenetic constructions: the Buneman tree, the Refined Buneman tree, and split decomposition. We introduce and exploit combinatorial formalisms involving trees, quartets, and splits, and make particular use of an attractive duality between unrooted trees, splits, and dissimilarities on one hand, and rooted trees, clusters, and similarity measures on the other. Using these techniques, we achieve O(n) improvements in the time complexity of the best previously published algorithms (where n is the number of studied species). Our algorithms will be included in the next edition of the popular Splitslkee software package.

Genome duplication is an important source of new gene functions and novel physiological pathways.In the course of evolution, the nucleotide sequences of duplicated genes tend to diverge through mutation, so that one copy loses function (and disappears from view) or develops a new function, encoding a distinct but similar product.Originally a duplicated genome contains two identical copies of each chromosome, but through reciprocal translocation, parallel linkage patterns between the two copies are disrupted.Eventually, all that can be detected are several chromosome segments of greater or lesser length (blocks), each of which appears twice in the genome, containing many paralogous genes in parallel orders.We present an exact algorithm for reconstructing the ancestral pm-doubling genome in polynomial time, minimizing in key cases the number of translocations required to derive the observed order and orientation of blocks along the present-day chromosomes.We apply this to the genome duplication which has been described for Saccharomyces cere- visiae.1 Genome duplication Perhaps the most spectacular cause of gene duplication is tetraploidization of the genome.Normally a lethal accident of meiosis or other reproductive step, if this doubling of the genome can be resolved in the organism and eventually fixed as a normalized diploid state in a population, it represents a simultaneous duplication of the entire genetic complement.It transcends other mechanisms for gene duplication in that not only is one copy of each gene free to evolve its own function, but it can evolve in concert with any 'DBpartement d'Informatique et de recherche op&ationnelle, Universitd de Montreal, CP 6128