Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem
Speaker:Stefan Canzar
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D3
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Wednesday, 8 August 2007
Duration:30 Minutes
Building:E1 4
The multiple sequence alignment problem (MSA) is one of the most important

problems in computational biology. A branch-and-bound (bb) algorithm will
be presented in which the upper bound at each bb node is based on a Lagrangian
relaxation of an integer linear programming formulation for MSA. Dualizing certain
inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which
can be solved efficiently by a dynamic programming approach. Due to a reformulation
w.r.t. additionally introduced variables prior to relaxation we improve the convergence
rate dramatically while at the same time being able to solve the Lagrangian problem efficiently.

Name(s):Stefan Canzar
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Deepak Ajwani, 08/03/2007 04:43 PM -- Created document.