Conference Timetable

Here is the preliminary timetable, indicating who will be speaking when.

More details as they come to hand.

Details

Andreas Dress

1. Crypto-Isomorphisms in Combinatorial Phylogenetics

Like other combinatorial structures, the so-called X-trees much studied in phylogenetic analysis also have many rather distinct, yet perfectly equivalent descriptions. They can be described:

1. in graph-theoretical terms as leaf-labelled (and edge-weighted) trees,
2. in terms of 'certain' metrics defined on X,
3. in terms of 'certain' collections of (weighted) X-splits, and
4. in terms of 'certain' collections of (weighted) quartet trees whose leaves are drawn from X.

While proving the corresponding "crypto-isomorphism theorems" (i.e. the equivalence of those various descriptions) is not very hard, the point of keeping all those concepts in mind when dealing with phylogenetic analysis is that

1. each one has distinct --- and not any more equivalent --- relaxations derived by relaxing one or the other of the requirements necessary and sufficient for the existence of an associated X-tree, and
2. trying to relate these relaxations to each other as well as to real-world data can reveal
   • important aspects of those concepts themselves, as well as
   • intrinsic inconsistencies of any data set in question.

The lecture will provide a review of the various combinatorial concepts mentioned above and discuss how these concepts and, in particular, their various relaxations are related with each other.

• dvi slides
• postscript slides

2. Quartets and Ranks in Phylogenetic Combinatorics and Cluster Analysis

Based on the previous lecture, the evening lecture will deal specifically with recent progress regarding "quartet analysis" and "rank-based methods in biological data analysis".

Neil Robertson

Terry Speed

1. Pre-processing cDNA microarray data
2. Identifying differently expressed genes with microarray data

Terry suggests weeks 7 and 8 of http://www.stat.Berkeley.EDU/users/terry/Classes/s246.2002/index.html as background reading.

Richard Stanley

Richard Stanley's overall title is An introduction to generating functions. He intends to cover:

1. The idea of generating functions.
2. Rational generating functions.
3. Algebraic generating functions.
4. Exponential generating functions, trees and Lagrange inversion.

However, he is currently undecided as to how to allocate the topics over his two lectures.

He suggests that the closest paper to the topic is his own paper, "Generating Functions", in Studies in Combinatorics (G.-C. Rota, ed.), Mathematical Association of America, 1978, pp 100-141, or (for the very keen) his books, Enumerative Combinatorics, volumes 1 and 2.

Slides

Karl Broman

1. Meiosis, recombination and interference.
   
   • Slides
2. Gene mapping in mice.
   
   • Slides

Karl suggests the following background readings:

• McPeak, M S (1996), Introduction to recombination and linkage analysis. In: Speed T P, Waterman M S (eds) Genetic mapping and DNA sequencing, IMA volumes on Mathematics and its Applications, Volume 81, Springer-Verlag, or available here.
• Broman K W (2001), Review of statistical methods for QTL mapping in experimental crosses. Lab Animal 30(7):44-52, or here.

Lior Pachter

Mathematics of Gene Finding and Alignment

Lior Pachter plans to talk about hidden Markov models and their applications to gene finding and alignment.

His first talk (more introductory) will survey the basics of alignment and gene finding, highlighting interesting connections to combinatorics.

The second talk will go more in detail into comparative genomics and current research on probabilistic methods for alignment, gene finding, and phylogeny (time permitting) using HMMs.

• Slides
• Slides bz2

Martin Grohe

Logic, Graph Theory and Complexity

1. Algorithmic Meta Theorems through Logic and Graph Theory
   
   • Slides
2. Evaluating Tree-Structured Formulas
   
   • Slides
3. The Complexity of Finding and Counting Homomorphisms
   
   • Slides

Tandy Warnow

1. Fast Converging Phylogenetic Reconstruction Methods

In this talk we address a statistical aspect of the performance of phylogeny reconstruction methods -- namely, the number of sites (i.e. the sequence length) needed for the method to reconstruct the true tree with high probability. We present results showing that standard polynomial time methods will reconstruct the true tree given sequences of lengths that are exponential in the largest evolutionary distance in the tree. We then describe new methods (some developed in collaboration with Mike Steel) which reconstruct the true tree with high probability from polynomial length sequences. These methods are graph-theoretic, and exploit chordal graph theory to obtain their performance guarantees.

2. Open problems in phylogenetics

3. Historical Linguistics

A beautiful graph theory question, "triangulating colored graphs", turns out to be the foundation of the inference of evolutionary history of languages. Here we will present the theory, describe both combinatorial and graph theoretic algorithms to solve this problem, and describe our analysis of the Indo-European family of languages.

Mike Hallet

Paul Seymour