Set Covering Problem

The Set Covering Decision Problem:

Given a universe of elements U and a family of sets S whose union covers U, is there a subset of S of size k that covers U?

For a more detailed description, read this: http://en.wikipedia.org/wiki/Set_cover_problem

This is an NP complete problem, and we will describe a potential biological method to find a solution below. A similar problem is the optimization problem which asks to find the smallest possible number of sets in S that will cover U. The optimization problem is NP-hard and may be worth considering as well.

Our idea:

Every element of the universe U is represented by its own reporter gene. We can then build the sets in S, potentially using Golden Gate Assembly. Then we use the column method, with each column containing every set in S. The number of columns will be determined by k. If all genes report, then a solution has been found.