Set Covering Problem - Revision history

Dudeloache: /* Example: */

2011-06-09T20:12:32Z

‎Example:

Dudeloache: /* The Set Covering Decision Problem: */

2011-06-09T20:04:04Z

‎The Set Covering Decision Problem:

Dudeloache: /* The Idea: */

2011-06-09T20:03:48Z

‎The Idea:

Dudeloache: /* Example: */

2011-06-09T20:03:20Z

‎Example:

Dudeloache: /* Example: */

2011-06-09T20:02:36Z

‎Example:

Dudeloache at 20:02, 9 June 2011

2011-06-09T20:02:15Z

Dudeloache at 20:01, 9 June 2011

2011-06-09T20:01:36Z

Dudeloache: Created page with '== 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'…'

2011-06-09T19:45:44Z

Created page with '== 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'…'

New page

== 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.

@@ Line 16: / Line 16: @@
 '''U''' = {Cre,Bla,CAT,RFP,GFP}
 '''S''' = {{Cre, Bla, CAT},{Bla,RFP},{CAT,RFP},{RFP,GFP}}
 ''k'' = 2

← Older revision		Revision as of 20:04, 9 June 2011
Line 7:		Line 7:

	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 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: ==		== The Idea: ==

← Older revision		Revision as of 20:03, 9 June 2011
Line 13:		Line 13:


−	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.	+	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 ''yes'' answer has been found.
−
−

	== Example: ==		== Example: ==

← Older revision		Revision as of 20:03, 9 June 2011
Line 27:		Line 27:
	Column 2 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}}		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.	+	If the answer is ''yes'', 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''.

@@ Line 23: / Line 23: @@
 ''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 1 = {{Cre + Bla + CAT},{Bla + RFP},{CAT + RFP},{RFP + GFP}} each with same 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.

@@ Line 2: / Line 2: @@
-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'''?
+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, read this: http://en.wikipedia.org/wiki/Set_cover_problem
+For a more detailed description of the problem, 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.
+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.
-== Our idea: ==
+== 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 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.
+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.