Tuesday, June 18
10:00 AM-12:00 PM
Room 301

Combinatorial Optimization in Physics and Biology

The speakers in this minisymposium will present four applications, in biology and Physics, of combinatorial optimization. The first two deal with multiple-sequence alignment problems. For a new formulation called maximum weight trace, the speakers present branch and bound algorithms that compute optimal alignments for real-world instances whose scale has been unapproachable by previous methods. The third deals with radiation hybrid mapping of genes in chromosomes and leads to the betweenness problem. Again, optimal solutions for instances in the biology literature can be computed via a branch and cut code. The fourth deals with the determination and analysis of exact ground states of Ising spin glasses including rigidity.

Organizer: Michael Junger
Universitat zu Koln, Germany

10:00 Computing Optimal Multiple-Sequence Alignments
John D. Kececioglu, University of Georgia
10:30 A Branch and Cut Algorithm for a Sequence Alignment Problem
Knut Reinert, Max-Planck-Institute fr Informatik, Germany
11:00 Exact Solutions for the Betweenness Problem for Mapping Genes
Petra Mutzel, Max-Planck-Institute fr Informatik, Germany
11:30 Analysis of Ground State Properties of Ising Spin Glasses
Giovanni Rinaldi, Instituto di Analisi dei Sistemi ed Informatica del CNR, Italy

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index

MEM, 3/21/96