COMPUTATIONS FOR MAPPING GENOMES WITH CLONES

We discuss algorithms for ordered clone mapping via restriction fingerprinting. These algorithms accommodate multiple digestions and are applicable when the order of restriction fragments in each clone is not determined. The computer algorithm for clone pair overlap probability calculation generates the likely restriction fragment pair matchings. (As will be seen, this algorithm computes permanents.) Features of the data are characterized including experimental reproducibility. We also give details of the simulation of data for the purpose of computing clone pair overlap probabilities. Our algorithm is also applied to a simpler simulated fingerprint, consisting of a single restriction digest, to characterize the overlap detection afforded by the combination of experiment and data analysis. In addition, we discuss the applications of algorithms involving interval graphs to the positioning of clones. The pairwise overlap probabilities are refined by using the constraint that clones are derived by fragmenting a linear DNA molecule and that clones are typically subintervals. The interval graph algorithms can be applied to diverse mapping protocols. Furthermore, they address inconsistencies due to repeated DNA sequences or cloning artifacts. Finally, we describe an incremental technique for contig assembly.