In order to study a genome, several copies of it are cut or broken down, and some of the resulting shorter segments (called clones) are preserved for further analysis. Depending on the technique used, the preserved clones may have variable length, or they may all have essentially the same length. In the process of producing the clones, all information on their relative position along the DNA chain is lost. The goal of physical mapping of DNA is to reconstruct that order, based on experimental data on the overlaps between pairs of clones.

From the commencement of the semester, I have managed to implement a Proper Interval Graph class using Java to mimic the DNA chain. The vertices of this graph represent the clones and edges correspond to the overlapping pairs of clones.

With the graph implemented, I went on to implementing the 3-sweep LexBFS algorithm which recognizes proper interval graphs and helps in the restoration of correct interval orders. From this ordering, I am able to locate any missing edges between two vertices and even suggest possible edges between vertices which were detected as being faulty.

Currently, Dr. Dragan and I are running multiple experiments on the algorithm to better understand its behavior when certain scenarios arise.