A GENETIC ALGORITHM FOR ASSEMBLING CHROMOSOME PHYSICAL MAPS

Physical map assembly typically begins with a number of pairwise relationships between clones, and from these produces an overall arrangement of the clones. When there are only a few clones, an investigator can keep in mind all of the relevant data, and can weigh the evidence to produce a map that fits all the experimental results reasonably well. Today, however, it is common to build maps with thousands of clones and millions of pairwise relationships. Computer aided map assembly is thus required. Current computer algorithms typically use only a small fraction of available experimental results, and sometimes fail to deal adequately with inconsistency in the data. The assembly problem is here framed as optimizing a map to fit all the experimental data, and a genetic algorithm to search for optimal maps is described (in genetic algorithms, possible solutions to a problem are treated as individuals in an evolving population). The method has been used to construct or improve ordered clone maps for large parts of human chromosome 16.