dc.contributor.author |
Arthanari, Tirukkattuppalli |
en |
dc.contributor.author |
Le Thi, HA |
en |
dc.date.accessioned |
2012-03-15T19:53:57Z |
en |
dc.date.issued |
2011 |
en |
dc.identifier.citation |
Optimization Letters 5(1):27-40 2011 |
en |
dc.identifier.issn |
1862-4472 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/14453 |
en |
dc.description.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 k L 2 , where, k is the number of sequences and L is the total length of the sequences, that is, L = k i=1 l i , 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. |
en |
dc.publisher |
Springer |
en |
dc.relation.ispartofseries |
Optimization Letters |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Details obtained from http://www.sherpa.ac.uk/romeo/issn/1862-4472/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
New formulations of the multiple sequence alignment problem |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1007/s11590-010-0188-8 |
en |
pubs.issue |
1 |
en |
pubs.begin-page |
27 |
en |
pubs.volume |
5 |
en |
dc.rights.holder |
Copyright: Springer |
en |
pubs.end-page |
40 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/RestrictedAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
204868 |
en |
pubs.org-id |
Business and Economics |
en |
pubs.org-id |
Info Systems & Operations Mgmt |
en |
dc.identifier.eissn |
1862-4480 |
en |
pubs.record-created-at-source-date |
2012-03-16 |
en |