DNA Polyhedra Verifier

The verifier is split into two pieces. The first takes your output file, which is a few strings of ACGT's, and figures out which matches will occur, giving longer matches priority. It will spew if there are any ambiguous matches, but it will also be kind enough to explain how the ambiguity occurred. The second piece takes the output from the first, a simplified set of strings, and runs the graph-checking algorithm explained in class.

The program is now finished -- it does indeed give you a solid YES or NO answer to the correctness of your solution.

The program can be downloaded here. You will also need to download the matcher program, which is used to check graph isomorphism. Run it as follows:
./poly graphfile dnafile
(matcher is invoked internally by poly) Here is a sample graph file for a tetrahedron.

Here are some short examples to illustrate the first half of the verifier. These are all actual outputs of the program based on the command line:
./poly graph1 dnaXX > outputXX
where graph1 is the tetrahedron given above.
input dna1 dna2 dna3 dna4 dna5 dna6 dna7 dna8 dna9 dna10 dna11
output output1 output2 output3 output4 output5 output6 output7 output8 output9 output10 output11

fatal error when running ./matcher
If you get the following error message:
ld.so.1: ./matcher: fatal: libgcc_s.so.1: open failed: No such file or directory

you can fix it by adding an environment variable. In csh or tcsh you can type
setenv LD_LIBRARY_PATH /usr/local/lib
In other shells, use export. Then run the program again, and this time it should work.

Example 1
This file is an example of the output your program might generate (if your program works correctly) for a tetrahedron. Here is the output generated by poly.

Example 2
This one is a little simpler.

  • Graph file
  • DNA file
  • Output from poly

    This is an illustration of how the resulting graph in this example is derived from the string-letter strands. Note that in general the node numbers of the resulting graph have nothing to do with the string-letters (which are numbers in poly) of the string-letter strands. In other words, the 0,1,2 on the left of this picture don't in any way "turn into" the 0,1,2 on the right side.