×

An optimization modelling for string selection in molecular biology using Pareto optimality. (English) Zbl 1221.90089

Summary: A known class of computational problems in molecular biology is the consensus string problem, to which belongs the problem of string selection via comparison. This paper deals with one of these problems called Closest String Problem (CSP). A novel definition of CSP is provided, based upon the Pareto optimality notion, to obtain most useful sequences. Also, a zero-one optimization model to solve the new defined CSP is introduced. Finally, a comparison between the new definition (model) and a current one is given.

MSC:

90C90 Applications of mathematical programming
92C40 Biochemistry, molecular biology
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cherruault, Y., Global optimization in biology and medicine, Math. Comput. Modell., 20, 119-132 (1994) · Zbl 0808.92001
[2] Ecker, J. G.; Kupferschmid, M.; Lawrence, C. E.; Reilly, A. A.; Scott, A. C.H., An application of nonlinear optimization in molecular biology, Eur. J. Oper. Res., 138, 452-458 (2002) · Zbl 1003.90043
[3] Festa, P., On some optimization problems in molecular biology, Math. Biosci., 207, 219-234 (2007) · Zbl 1117.92026
[4] Frances, M.; Litman, A., On covering problems of codes, Theory Comput. Syst., 30, 2, 113-119 (1997) · Zbl 0868.94056
[5] Greenberg, H. J.; Hart, W. E.; Lancia, G., Opportunities for combinatorial optimization in computational biology, Inform. J. Comput., 16, 3, 211-231 (2004) · Zbl 1239.90003
[6] T. Kelsey, L. Kotthoff, The exact closest string problem as a constraint satisfaction problem, arXiv:1005.0089; T. Kelsey, L. Kotthoff, The exact closest string problem as a constraint satisfaction problem, arXiv:1005.0089
[7] Meneses, C. N.; Lu, Z.; Oliveira, C. A.S.; Pardalos, P. M., Optimal solutions for the closest-string problem via integer programming, Inform. J. Comput., 16, 419-429 (2004) · Zbl 1239.90077
[8] Gomes, F. C.; Meneses, C. N.; Pardalos, P. M.; Viana, G. V.R., A parallel multistart algorithm for the closest string problem, Comput. Oper. Res., 35, 3636-3643 (2008) · Zbl 1209.92024
[9] Lanctot, J.; Li, M.; Ma, B.; Wang, S.; Zhang, L., Distinguishing string selection problems, Inform. Comput., 185, 41-55 (2003) · Zbl 1069.68116
[10] M. Li, B. Ma, L. Wang, Finding similar regions in many strings. in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1999, pp. 473-482.; M. Li, B. Ma, L. Wang, Finding similar regions in many strings. in: Proceedings of the Annual ACM Symposium on Theory of Computing, 1999, pp. 473-482. · Zbl 1346.68307
[11] J.S. Sim, K. Park, The consensus string problem for a metric is NP-complete. in: Proceedings of the Annual Australasian Workshop on Combinatorial Algorithms (AWOCA), 1999, pp. 107-113.; J.S. Sim, K. Park, The consensus string problem for a metric is NP-complete. in: Proceedings of the Annual Australasian Workshop on Combinatorial Algorithms (AWOCA), 1999, pp. 107-113.
[12] Ehrgott, M., Multicriteria Optimization (2005), Springer · Zbl 1132.90001
[13] Pourkarimi, L.; Zarepisheh, M., A dual-based algorithm for solving lexicographic multiple objective programs, Eur. J. Oper. Res., 176, 1348-1356 (2007) · Zbl 1102.90063
[14] Steuer, R. E., Multiple Criteria Optimization: Theory, Computation, and Application (1986), Wiley: Wiley New York · Zbl 0663.90085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.