Assignment round twoProblemA 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 makes the length of the global cycle no longer than the given limit. AssignmentCreate a Java program that encodes the decision problem instance as a boolean constraint satisfaction problem which is then solved using the boolean circuits solver bczchaff taking as input boolean circuit satisfiability problems given in the described here. Test your solution with two sets of instances (optimal length is in the file name): set 1 set 2. For each set, test how many can be solved in 10 minutes with bczchaff and what is the average and median time. InputThe program will be run with command java DNA length <graph>where <graph> is the file name of a graph with each node representing a DNA string and length is the maximum allowed length of the cycle. An 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. Name your class containing the main()-method DNA.java. Output
Assignments for boolean variables e1,e2.. DeliverableReturn the commented source code and a small report describing your approach and results to airusane(at)tcs.hut.fi.GradingCorrect solution on first try with sufficient report earns 3 points, each failed attempt decreasing points by 1. Submitted solutions are compared with each other and a reference solution. Good solutions are granted 1-2 extra points. Example Instances
Instance with minimum length of 160 [TCS main] [Current] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [Links] |