Physical Mapping of Chromosomes Using Unique Probes

TitlePhysical Mapping of Chromosomes Using Unique Probes
Publication TypeTechnical Report
Year of Publication1995
AuthorsAlizadeh, F., Karp R. M., Weisser D. K., & Zweig G.
Other Numbers955

The goal of physical mapping of the genome is to reconstruct a strand of DNA given a collection of overlapping fragments, or clones, from the strand. We present several algorithms to infer how the clones overlap, given data about each clone. We focus on data used to map human chromosomes 21 and Y, in which relatively short substrings, or probes, are extracted from the ends of clones. The substrings are long enough to be unique with high probability. The data we are given is an incidence matrix of clones and probes.In the absence of error, the correct placement can be found easily using a PQ-tree. The data is never free from error, however, and algorithms are differentiated by their performance in the presence of errors. We approach errors from two angles: by detecting and removing them, and by using algorithms which are robust in the presence of errors.We have also developed a strategy to recover noiseless data through an interactive process which detects anomalies in the data and retests questionable entries in the incidence matrix of clones and probes.We evaluate the effectiveness of our algorithms empirically, using simulated data as well as real data from human chromosome 21.

Bibliographic Notes

ICSI Technical Report TR-95-015

Abbreviated Authors

F. Alizadeh, R. M. Karp, D. K. Weisser, and G. Zweig

ICSI Publication Type

Technical Report