Master Thesis Defense by David Buezas
Mr David Buezas defended his master thesis on 'Constraint-based modeling of Minimum Set Covering: Application to Species Differentiation'.
Mr David Buezas defended his master thesis on 'Constraint-based modeling of Minimum Set Covering: Application to Species Differentiation' at UNL on Friday, 15 October 2010.
Abstract: A large number of species cannot be distinguished via standard non genetic analysis in the lab. In this dissertation I address the problem of finding all minimum sets of restriction enzymes that can be used to unequivocally identify the species of a yeast specimen by analyzing the size of digested DNA fragments in gel electrophoresis experiments. The problem is first mapped into set covering and then solved using various Constraint Programming techniques. One of the models for solving minimum set covering proved to be very efficient in finding the size of a minimum cover but was inapplicable to find all solutions due to the existence of symmetries. Many symmetry breaking algorithms were developed and tested for it. Hoping to get an efficient model suitable for both tasks also the global constraint involved on it was partially implemented in the CaSPER Constraint Solver, together with the most promising symmetry breaking algorithm. Eventually the best solution was obtained by combining two different constraint-based models, one to find the size of a minimum solution and the other to find all minimal solutions.