TCS / Studies / T-79.4201 / Home Assignments / Thispage
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

DNA String Embedding

Problem

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

Input

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

Output

Linear Program

Assignments for variables e1,e2..
en = 1, if strings represented at edge's end nodes are neighbors in the global cycle
en = 0, otherwise

SAT

Assignments for boolean variables e1,e2..
en = true, if strings represented at edge's end nodes are neighbors in the global cycle
en = false, otherwise

Example Instances

Instance with minimum length of 160
Instance with minimum length of 194
Instance with minimum length of 175


[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 24 March 2006.