Tuesday Afternoon, October 24

Discrete Algorithms in Computational Biology

Computational molecular biology is a rich source of combinatorial problems with potentially profound impact. The speakers in this minisymposium will discuss four diverse problem areas. Multiple sequence alignment seeks to align a set of sequences to reveal their common structure. Genome rearrangements seeks to explain the differences between two organisms by the fewest chromosomal events. Phylogenetic tree construction seeks the tree that best explains the evolution of a set of species. Protein folding seeks the conformation of an amino-acid molecule of lowest free energy. The speakers will present new algorithms that employ discrete methods to find optimal or provably near-optimal solutions to these problems.

Organizer: John Kececioglu,
University of Georgia

12:30 Computing Optimal Multiple-Sequence-Alignments by Branch and Bound
John Kececioglu, Organizer

1:00 Transforming Men Into Mice (A Polynomial-Time Algorithm for Genomic Distance)
Sridhar Hannenhalli and Pavel Pevzner, The Pennsylvania State University

1:30 Computing the Local Consensus of Trees
Sampath K. Kannan, Tandy Warnow, and Shibu Yooseph, University of Pennsylvania

2:00 Fast Protein Folding in the Hydrophobic-Hydrophilic Model Within Three-Eighths of Optimal
Sorin Istrail, Sandia National Laboratories

Transportation | Registration | Hotel Information | Speaker Index | Program Overview