Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
A Constraint based formulation of the Minimum Set Covering Problem for the Species Differentiation Problem
October 2010
Buez10
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 en- zymes 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 sym- metries. 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.
M. Sc. dissertation
David Buezas
Pedro Barahona
Universidade Nova de Lisboa
-
-
Export formats
David Buezas, A Constraint based formulation of the Minimum Set Covering Problem for the Species Differentiation Problem, Pedro Barahona (superv.), Universidade Nova de Lisboa, October 2010.
<b>David Buezas</b>, <u>A Constraint based formulation of the Minimum Set Covering Problem for the Species Differentiation Problem</u>, <a href="/people/members/view.php?code=7e27bc13fad97e99cd21ea6914d55659" class="supervisor">Pedro Barahona</a> (superv.), Universidade Nova de Lisboa, October 2010.
@mastersthesis {Buez10, author = {David Buezas}, title = {A Constraint based formulation of the Minimum Set Covering Problem for the Species Differentiation Problem}, school = {Universidade Nova de Lisboa}, note = {Pedro Barahona (superv.); }, 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 en- zymes 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 sym- metries. 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.}, month = {October}, year = {2010}, }
Publication's urls
/publications/view.php?code=ed033a288684ef9238b4acd7f7c0054c
/publications/view.php?code=Buez10
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT