A FAST RANDOM COST ALGORITHM FOR PHYSICAL MAPPING

Ordering clones from a genomic library into physical maps of whole chr omosomes presents a central computational/statistical problem in genet ics. Here we present a physical mapping algorithm for creating ordered genomic libraries or contig maps by using a random cost approach [Ber g, A. (1993) Nature (London) 361, 708-710]. This random cost algorithm is 5-10 times faster than existing physical mapping algorithms and ha s optimization performance comparable to existing procedures. The spee dup in the algorithm makes practical the widespread use of bootstrap r esampling to assess the statistical reliability of links in the physic al map as well as the use of more elaborate physical mapping criteria to improve map quality. The random cost algorithm is illustrated by it s application in assembling a physical map of chromosome IV from the f ilamentous fungus Aspergillus nidulans.