View source for 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'''? (a yes or no question)

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

The Set Covering Decision Problem 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.



== The 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 can 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 after Golden Gate Assembly, then a solution has been found.



== Example: ==

'''U''' = {Cre,Bla,CAT,RFP,GFP}
'''S''' = {{Cre, Bla, CAT},{Bla,RFP},{CAT,RFP},{RFP,GFP}}
''k'' = 2

Column 1 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}} each with sticky end that will attach to beginning of strands in 
             column 2
 
Column 2 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}}

If there is a solution, then using the Golden Gate Assembly method with these columns will produce a strand of genes expressing Cre, Bla, CAT, RFP, and GFP, formed using only one subset in each column. It is easy to see that there is indeed a solution to the simple problem above. Combining {Cre, Bla, CAT} and {RFP, GFP} in any order will signal that the answer is yes.