Application of bootstrap techniques to physical mapping

Ordering genetic markers or clones from a genomic library into a physical m ap is a central problem in genetics. In the presence of errors, there is no efficient algorithm known that solves this problem. Based on a standard he uristic algorithm for it, we present a method to construct a confidence nei ghborhood for a computed solution. We compute a confidence value for putati ve local solutions derived from bootstrap replicates of the original soluti on. In the reliable parts, the confidence neighborhood and the computed sol ution tend to coincide. In regions that are ill-defined by the data, the ne ighborhood contains additional, reasonable alternatives. This offers the po ssibility of designing further experiments for the badly defined regions to improve the quality of the physical map. We analyze our approach by a simu lation study and by application to a dataset of the genome of the bacterium Xylella fastidiosa. (C) 2000 Academic Press.