We present integer programming models for some variants of the farthest string problem. The number of variables and constraints is substantially less than that of the integer linear programming models known in the literature. Moreover, the solution of the linear programming-relaxation contains only a small proportion of noninteger values, which considerably simplifies the rounding process. Numerical tests have shown excellent results, especially when a small set of long sequences is given.
Get full access to this article
View all access options for this article.
References
1.
BlazewiczJ., RormanowiczP., and KasprzakM.2005. Selected combinatorial problems of computational biology. Eur. J. Oper. Res., 161, 585–597.
2.
BoucherC.A.2010. Combinatorial and probabilistic approaches to motif recognition [PhD dissertation]. University of Waterloo, Waterloo, Ontario, Canada.
3.
BoucherC.A., LandauG.M., LevyA., and PritchardD.2012. On approximating string selection problems with outliers. http://arxiv.org/pdf/1202.2820.pdf
4.
ChengC.H., HuangC.C., HuS.Y., and ChaoK.M.2004. Efficient algorithms for some variants of the farthest string problem. In Proceedings of Workshop on Combinatorial Mathematics and Computation Theory, pp. 266–272.
5.
FeroneD., FestaP., and ResendeM.G.C.2013. Hybrid metaheuristics for the far from most string problem. In BlesaM.J., et al., eds. Proceedings of Hybrid Metaheuristics: Lecture Notes in Computer Science, pp. 174–188.
6.
FestaP.2007. On some optimization problems in molecular biology. Math. Biosci., 207, 219–234.
7.
FestaP., and PardalosP.M.2012. Efficient solution for the far from most string problem. Ann. Oper. Res. 196, 663–682.
8.
KotnyekB.2002. A generalization of totally unimodular and network matrices [PhD dissertation]. London School of Economics.
MenesesC.N., PardalosP.M., ResendeM.G.C., and VazacopoulosA.2005. Modeling and solving string selection problems. In Proceedings of the 2005 International Symposium on Mathematical and Computational Biology, Biomat 2005, Rio de Janeiro.
12.
PappalardoE., PardalosP.M., and StracquadanioG.2013. Optimization Approaches for Solving String Selection Problems. Springer, New York, NY.
13.
Soleimani-damanehM.2011. On some multiobjective optimization problems arising in biology. Int. J. Comput. Math., 88, 1103–1119.
14.
ZörnigP.2011. Improved optimization modelling for the closest string and related problems. Appl. Math. Model., 35, 5609–5617.
