Date: February 8th 2017, 11h00
Place: ULB Bruxelles
Abstract: The Closest String Problem (CSP) calls for finding an n-string that minimizes its maximum Hamming distance from m given n-strings. This problem, originated in Code Theory, has recently be considered for applications in Bioinformatics. In the last years, integer linear programs have been successfully applied within heuristics to improve efficiency and effectiveness. We consider an ILP for the binary case (0-1 CSP) that updates the previous formulations and solve it by branch-and-cut. The method separates in polynomial time the first closure of {0,1/2}-Chvatal-Gomory cuts and can either be used stand-alone to find optimal solutions, or as a plug-in to improve heuristics based on the exact solution of reduced problems. Due to the parity structure of the right-hand side, the impressive performances obtained with this method in the binary case cannot be replicated in the general case. The problem is also formulated under different metrics, the Rank distance and the Levenshtein distance, that appear more suitable for genomic applications. Coauthored by Giovanni Felici, Mara Servilio and Paolo Ventura (IASI-CNR)
