ODS - ORDERING DNA-SEQUENCES - A PHYSICAL MAPPING ALGORITHM BASED ON SIMULATED ANNEALING

In the program ODS we provide a methodology for quickly ordering rando m clones into a physical map. The process of ordering individual clone s with respect to their position along a chromosome is based on the si milarity of binary signatures assigned to each clone. This binary sign ature is obtained by hybridizing each clone to a panel of oligonucleot ide probes. By using the fact that the amount of overlap between any t wo clones is reflected in the similarity of their binary signatures, i t is possible to reconstruct a chromosome by minimizing the sum of lin king distances between an ordered sequence of clones. Unlike other pro grams for physical mapping, ODS is very general in the types of data t hat can be utilized for chromosome reconstruction. Any trait that can be scored in a presence-absence manner, such as hybridized synthetic o ligonucleotides, restriction endonuclease recognition sites or single copy landmarks, can be used for analysis. Furthermore, the computation al requirements for the construction of large physical maps can be mea sured in a matter of hours on work-stations such as the VAX2000.