New formulations of the multiple sequence alignment problem

New formulations of the multiple sequence alignment problem

0.00 Avg rating0 Votes
Article ID: iaor20111465
Volume: 5
Issue: 1
Start Page Number: 27
End Page Number: 40
Publication Date: Feb 2011
Journal: Optimization Letters
Authors: ,
Keywords: programming: integer
Abstract:

A well known formulation of the multiple sequence alignment (MSA) problem is the maximum weight trace (MWT), a 0–1 linear programming problem. In this paper, we propose a new integer quadratic programming formulation of the MSA. The number of constraints and variables in the problem are only of the order of kL 2, where, k is the number of sequences and L is the total length of the sequences, that is, L = i = 1 k l i equ1 , where l i is the length of sequence i. Based on this formulation we introduce an equivalent linear constrained 0–1 quadratic programming problem. We also propose a 0–1 linear programming formulation of the MWT problem, with polynomially many constraints. Our formulation provides the first direct compact formulation that ensures that the critical circuit inequalities (which are exponentially many) are all met.

Reviews

Required fields are marked *. Your email address will not be published.