title: A note on scoring clones given a probe ordering.
abstract: We present an efficient algorithm for scoring clones given an ordering of probes under a schema proposed by Alizadeh et al. (1994) in the context of physical mapping with unique probes. The algorithm runs in time linear in the number of blocks of ones in the underlying sparse incidence matrix. A sparse and efficient algorithm for this task is important as it appears to be a central task in most algorithms for physical mapping.
mesh_terms: D000465:Algorithms; D002678:Chimera; D003001:Cloning, Molecular; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D016172:DNA Fingerprinting; D015342:DNA Probes; D005188:False Negative Reactions; D005189:False Positive Reactions; D015345:Oligonucleotide Probes; D011336:Probability; D016324:Sequence Tagged Sites
chemical_list: D015342:DNA Probes; D015345:Oligonucleotide Probes; D004247:DNA