DNA String EmbeddingProblemA collection of DNA strings, each of length 20 are combined to form one global cycle which contains each string. A pair of strings can have overlap of 1 to 5 base-pairs. Your task is to find an overlapped concatenation that minimizes the length of the global cycle. InputA graph with each node representing a DNA string. Edge between two nodes means that the corresponding strings can be concatenated. Each edge has an integer attribute "overlap" that represents the amount of overlap the corresponding strings have. OutputLinear Program
Assignments for variables e1,e2.. SAT
Assignments for boolean variables e1,e2.. Example Instances
Instance with minimum length of 160 [TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links] Latest update: 24 March 2006. |