Tuesday, June 18
10:00 AM-12:00 PM
Room 301
MS4
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
MEM, 3/21/96