Minimizing sets of enzymes to differentiate between species

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


A large number of species cannot be distinguished via standard non genetic analysis in the lab. In this paper we address the problem of finding 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 Constraint Programming techniques. Although the data sets used are relatively small (23 yeast species and 331 enzymes), a similar approach might be applicable to larger ones and to a number of variants as it is dis- cussed in the conclusion. The subject of this paper has already raised the interest of our biologist partners and may become a benchmark for the application of Constraint Programming techniques to Bioinformatics.
Original languageUnknown
Title of host publicationConstraint Based Methods for Bioinformatics
EditorsAD Palu, A Dovier, S Will
Place of Publication
Publication statusPublished - 1 Jan 2010
EventWorkshop on Constraint Based Methods for Bioinformatics -
Duration: 1 Jan 2010 → …


ConferenceWorkshop on Constraint Based Methods for Bioinformatics
Period1/01/10 → …

Cite this