A fast heuristic algorithm for a probe mapping problem.
A new heuristic algorithm is presented for mapping probes to locations along the genome, given noisy pairwise distance data as input. The model considered is quite general: The input consists of a collection of probe pairs and a confidence interval for the genomic distance separating each pair. Because the distance intervals are only known with some confidence level, some may be erroneous and must be removed in order to find a consistent map. A novel randomized technique for detecting and removing bad distance intervals is described. The technique could be useful in other contexts where partially erroneous data is inconsistent with the remaining data. These algorithms were motivated by the goal of making probe maps with inter-probe distance confidence intervals estimated from fluorescence in-situ hybridization (FISH) experiments. Experimentation was done on synthetic data sets (with and without errors) and FISH data from a region of human chromosome 4. Problems with up to 100 probes could be solved in several minutes on a fast workstation. In addition to FISH mapping, we describe some other possible applications that fall within the problem model. These include: mapping a backbone structure in folded DNA, finding consensus maps between independent maps covering the same genomic region, and ordering clones in a clone library.
Mumey
B
B
Department of Computer Science, University of Washington, Seattle 98195-2350, USA. brendan@cs.washington.edu
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods* / Q000706:statistics & numerical data; D002894:Chromosomes, Human, Pair 4 / Q000235:genetics; D003001:Cloning, Molecular; D016384:Consensus Sequence; D004247:DNA / Q000737:chemistry / Q000235:genetics; D016208:Databases, Factual; D005069:Evaluation Studies as Topic; D015723:Gene Library; D015894:Genome, Human; D006801:Humans; D017404:In Situ Hybridization, Fluorescence; D008957:Models, Genetic; D015336:Molecular Probe Techniques / Q000706:statistics & numerical data; D009690:Nucleic Acid Conformation
D004247:DNA