Document details

Constraint-based modeling of minimum set covering: application to species differentation

Author(s): Buezas, David

Date: 2011

Persistent ID:

Origin: Repositório Institucional da UNL

Subject(s): Minimum set covering; Enzymes; Species differentiation; Constraints


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.

Work presented in the context of the European Master in Computational Logics, as partial requisit for the graduation as Master in Computational Logics

Document Type Master thesis
Language English
Advisor(s) Barahona, Pedro
Contributor(s) Buezas, David
facebook logo  linkedin logo  twitter logo 
mendeley logo

Related documents

No related documents