title: Reduced-Size Integer Linear Programming Models for String Selection Problems: Application to the Farthest String Problem.
abstract: 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.
authors.affiliation: Department of Statistics, Institute of Exact Sciences, University of Brasília , Brasília, Brazil .
authors.forename: Peter
authors.initials: P
authors.lastname: Zörnig
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D008962:Models, Theoretical; D011382:Programming, Linear
keywords: computational biology; far from most strings problem; farthest string problem; mathematical programming; modeling