1 - Co-evolution of Proteins with their Interaction Partners
Chern-Sing Goh, Andrew A. Bogan, Marcin J. Joachimiak, Dirk Walther, Fred E. Cohen, University of California, San Francisco
The divergent evolution of proteins requires ligands and their receptors to co-evolve, creating new pathways when a new receptor is activated by a new ligand. Based on this concept, we have developed a method for measuring the co-evolution of interaction proteins and applied this analysis to chemokines and their receptors.

2 - Incomplete Directed Perfect Phylogeny
Itsik Pe'er, Ron Shamir, Roded Sharan, Tel Aviv University
We investigate the following variant of the "Perfect Phylogeny" problem: Input: An n*m species-characters matrix. Characters are binary, and can only be gained, never lost. Some matrix entries are unknown. Goal: Complete the missing entries in a way admitting a perfect phylogeny. We solve this problem in O(m*n*polylog) time.

Poster 3 withdrawn by author.

Poster 4 withdrawn by author.

5 - Statistical Significance of Probabilistic Hybrid Alignment
Yi-Kuo Yu, Florida Atlantic University; Ralf Bundschuh, Terence Hwa, University of California, San Diego
We propose a sequence alignment algorithm that is a hybrid between the Smith-Waterman and HMM-based methods. In contrast to all existing algorithms, the statistics of the hybrid alignment can be accurately characterized without doing massive simulation, even for position-dependent substitution and gap costs, without losing sensitivity or specificity.

6 - Automated Sequence Function Prediction Based on Phylogenetic Inference
Christian M. Zmasek, Sean R. Eddy, Washington University School of Medicine
A method using phylogenetic inference for automated and robust sequence function prediction is described. At the core stands the automated comparison of gene trees with species trees, allowing detection of paralogs. A time-efficient algorithm to accomplish this is discussed. In addition, a Java framework for working with phylogenetic trees is shown.