New formulations of the multiple sequence alignment problem

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...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2011-02, Vol.5 (1), p.27-40
Main Authors: Arthanari, Thiru S., Le Thi, Hoai An
Format: Article
Language:English
Subjects:
Computational Intelligence
Computer Science
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Original Paper
Simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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, , 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.
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-010-0188-8