A fast random cost algorithm for physical mapping.

Abstract

Ordering clones from a genomic library into physical maps of whole chromosomes presents a central computational/statistical problem in genetics. Here we present a physical mapping algorithm for creating ordered genomic libraries or contig maps by using a random cost approach [Berg, A. (1993) Nature (London) 361, 708-710]. This random cost algorithm is 5-10 times faster than existing physical mapping algorithms and has optimization performance comparable to existing procedures. The speedup in the algorithm makes practical the widespread use of bootstrap resampling to assess the statistical reliability of links in the physical map as well as the use of more elaborate physical mapping criteria to improve map quality. The random cost algorithm is illustrated by its application in assembling a physical map of chromosome IV from the filamentous fungus Aspergillus nidulans.