09:00 to 10:00 Advances and limitations of maximum likelihood phylogenetics I'll present recent developments in inferring phylogenies from sequences by maximum likelihood (ML). In fact, this approach involves two main components: probabilistic modelling of substitution events, and algorithmics to infer near-optimal trees. I'll show that algorithmics has considerably progressed during the last few years, allowing now for fast ML inference from large datasets. On the other hand, I'll underline the difficulties encountered with modelling, especially of protein evolution, and show that elaborating more realistic and improved substitution models is a major challenge. INI 1 10:00 to 10:20 Restrictions on meaningful phylogenetic networks INI 1 10:20 to 10:40 Inference rules for super-network construction A fundamental aspect of understanding molecular evolution is species phylogeny reconstruction. A commonly used approach in this context is to infer it from a collection of gene tress using, for example, a supertree or supermatrix method. Although popular, one of the main drawbacks of such a method is that it can suppress conflict within the gene trees arising from, for example, lateral gene transfer or recombination. Until now, the only known approaches capable of accommodating such conflict have been Z-closure super-networks and Q-imputation super-networks. In this talk, we introduce the novel Y-inference rule and show that under certain circumstances this inference rule on its own or in combination with one Meacham's inference rules constitute an attractive alternative approach that complements the above list of super-network approaches. This is joint work with Stefan Gruenewald (AS-MPG Partner Institute for Computational Biology, China) and Qiong Wu (University of East Anglia, UK). INI 1 10:40 to 11:00 Maximum parsimony on phylogenetic networks: some rigorous results Phylogenies, the evolutionary histories of groups of organisms, play a major role in representing the interrelationships among biological entities. Although many biological processes can be effectively modeled and summarized as a binary tree, others cannot: recombination, hybrid speciation, and horizontal gene transfer result in networks of relationships rather than trees of relationships. Maximum parsimony (MP) is one of the most popular methods used for phylogenetic tree reconstruction. Roughly, this method is based on the assumption that "evolution is parsimonious", that is, the best evolutionary trees are the ones that minimize the number of changes along the edges of the tree. In previous works, we formulated a maximum parsimony (MP) criterion for reconstructing and evaluating phylogenetic networks, and demonstrated its quality on biological as well as synthetic datasets. In this work, we show further theoretical insights and results regarding various aspects of the MP criterion of phylogenetic networks. INI 1 11:00 to 11:30 Coffee 11:30 to 11:50 Integer programming for phylogenetic computations We consider the following three related problems: 1) Given complete data (taxon by character data) remove the minimum number of characters so that the remaining data is pairwise compatible (contains a perfect phylogeny); 2) Given data with missing entries, impute the missing data in order to minimize, in the completed data, the number of pairs of characters that are incompatible; 3) Given data with missing entries, impute the missing data to minimize, in the completed data, the number of characters that must be removed so that the remaining sites are pairwise compatible. We consider in detail the cases of two, three and four states allowed per character and describe compact integer programming formulations that solve these problems (the approach extends in principle to any fixed number of states). We discuss empirical tests on problem instances of size of interest in phylogenetics, and establish that these instances can be solved very efficiently in practice, even though the problems are all NP-hard. Related Links http://wwwcsif.cs.ucdavis.edu/~gusfield/ - powerpoint, papers and software for the 2-state case INI 1 11:50 to 12:10 Quartet compatability: new results and surprising counterexamples Many methods in phylogenetic tree reconstruction are not feasible for a large number of taxa. Hence, it is a natural approach to construct trees on small taxa sets first and then to look for a big tree (supertree) on the union of the taxa sets that contains all information of the small trees. However, even if all input trees are quartets, i.e. binary trees with four leaves, it is an NP-complete problem to decide whether they are compatible. I will present a sufficient condition for a set of binary phylogenetic trees to be compatible. That result can be used to give a much shorter proof of the known characterization of quartet sets of minimal size which are defining, i.e. compatible with a unique supertree. Further, I will show some quartet sets with surprising properties which are counterintuitive and explain the hardness of the compatibility problem. One example is an incompatible collection of quartets for which every two quartets overlap in at most one taxon. It has been known for fifteen years that such quartet sets exist but the example is the first one that has been constructed. INI 1 12:10 to 12:30 On k-leaf powers In 2002, Nishimura, Ragde and Thilikos introduced the notion of k-leaf power and k-leaf root, motivated by the following: ... a fundamental problem in computational biology is the reconstruction of the phylogeny, or evolutionary history, of a set of species or genes, typically represented as a phylogenetic tree ...''. The species occur as leaves of the phylogenetic tree. Let G=(V_G,E_G) be a finite undirected graph. For k at least 2, a tree T is a $k$-leaf root of G if V_G is the leaf set of T and two vertices x,y in V_G are adjacent in G if and only if their distance d_T(x,y) in T is at most k. The graph G is a $k$-leaf power if it has a k-leaf root. Obviously, a graph is a 2-leaf power if and only if it is the disjoint union of cliques, i.e., it contains no induced path of three vertices. Recent work on leaf powers contains characterisations of 3- and 4-leaf powers and their variants. It is well known that every k-leaf power is a strongly chordal graph. For k at least 6, no characterisation of $k$-leaf powers and no efficient recognition is known. We discuss some open problems and new results on leaf powers. INI 1 12:30 to 13:30 Lunch at Wolfson Court 14:00 to 15:00 Tripartitions in phylogenetic networks Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of reticulate evolution events, like recombination, hybridization, and lateral gene transfer. In a recent series of papers devoted to the study of reconstructibility of phylogenetic networks, the well-known bipartition metric for phylogenetic trees was generalized to the so-called tripartition metric for phylogenetic networks. In this talk, we show that, in fact, this tripartition metric does not satisfy the separation axiom of distances (zero distance means isomorphism, or, in a more relaxed version, zero distance means indistinguishability in some specific sense) in any of the classes of phylogenetic networks where it is claimed to do so. We also present a class of phylogenetic networks whose members can be singled out by means of their sets of tripartitions, and hence, where the latter can be used to define a meaningful metric. Related Links http://www.lsi.upc.edu/~valiente/ - home page INI 1 15:00 to 15:30 Tea 15:30 to 15:50 Branch and bound construction of balanced minimum evolution optimal trees The Balanced Minimum Evolution (BME) score has been recently proposed as a criterion for reconstructing phylogenetic trees based on a distance matrix. It is based on Pauplin's formula, which provides a natural estimate of the total length of a tree, based on its topology and a matrix of estimated pairwise distances. The objective is to find the tree topology that minimizes this length estimate, as short trees are usually the ones that best reflect the data. Recently, it has been shown that Neighbor Joining can be viewed as a greedy algorithm trying to minimise BME. Together with other theoretical reasons, there are strong experimental reasons supporting BME-guided tree reconstruction. However, the published methods are heuristic and do not attempt to construct BME-optimal trees. The main aim of this talk will be to present a Branch and Bound approach for finding BME-optimal trees. We derived a simple bound on the BME score of a tree based on the score of a partially constructed tree. This allows us to eliminate the need to explore large parts of the space of all possible trees, but still guarantees that all optimal trees will be found. The efficiency of this approach compares well with that of other Branch and Bound approaches such as the ones for Maximum Parsimony. Finally the topological accuracy of the reconstructed trees will also be discussed. INI 1 15:50 to 16:10 New analytical results for the speciation times in neutral models Did a reconstructed phylogeny evolve under a neutral model? We provide an analytical way  opposed to the common simulation approach  for comparing the speciation times of a reconstructed tree with the dates proposed by the neutral models, e.g. via lineages-through-time plots. Further, if dates are missing in a reconstructed tree which evolved under a neutral model, we provide the time of the speciation events. These methods, which make use of the rank function on a phylogenetic tree, can also be applied for calculating analytically the loss in biodiversity when some species become extinct. The neutral models considered in this work are the Yule model and a generalization which includes extinction as well, the critical branching process (CBP) model, recently introduced by D. Aldous and L. Popovic. Trees under these neutral models are conditioned on having $n$ extant species today which is crucial for data analysis. INI 1 16:10 to 16:30 Partitioning the sample space on five taxa for the neighbour joining algorithm In this talk, we will analyze the behavior of the Neighbor Joining algorithm on five taxa and we will show that the partition of the sample (data) space for estimation of a tree topology with five taxa into subspaces, within each of which the Neighbor Joining algorithm returns the same tree topology. A key of our method to partition the sample space is the action of the symmetric group $S_5$ on the set of distance matrices by changing the labels of leaves. The method described in this paper can be generalized to trees with more than five taxa. This is joint work with Kord Eickmeyer and a preprint is available at http://arxiv.org/abs/math.CO/0703081. Related Links http://arxiv.org/abs/math.CO/0703081 - arxiv INI 1 18:45 to 19:30 Dinner at Wolfson Court (Residents only)