## Abstract

We describe the theoretical basis of an approach using microarrays of probes and libraries of BACs to construct maps of the probes, by assigning relative locations to the probes along the genome. The method depends on several hybridization experiments: in each experiment, we sample (with replacement) a large library of BACs to select a small collection of BACs for hybridization with the probe arrays. The resulting data can be used to assign a local distance metric relating the arrayed probes, and then to position the probes with respect to each other. The method is shown to be capable of achieving surprisingly high accuracy within individual contigs and with less than 100 microarray hybridization experiments even when the probes and clones number about 10^{5}, thus involving potentially around 10^{10} individual hybridizations. This approach is not dependent upon existing BAC contig information, and so should be particularly useful in the application to previously uncharacterized genomes. Nevertheless, the method may be used to independently validate a BAC contig map or a minimal tiling path obtained by intensive genomic sequence determination. We provide a detailed probabilistic analysis to characterize the outcome of a single hybridization experiment and what information can be garnered about the physical distance between any pair of probes. This analysis then leads to a formulation of a likelihood optimization problem whose solution leads to the relative probe locations. After reformulating the optimization problem in a graph-theoretic setting and by exploiting the underlying probabilistic structure, we develop an efficient approximation algorithm for our original problem. We have implemented the algorithm and conducted several experiments for varied sets of parameters. Our empirical results are highly promising and are reported here as well. We also explore how the probabilistic analysis and algorithmic efficiency issues affect the design of the underlying biochemical experiments.

Original language | English (US) |
---|---|

Title of host publication | Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings |

Editors | Bernard M. E. Moret, Olivier Gascuel |

Publisher | Springer Verlag |

Pages | 52-68 |

Number of pages | 17 |

ISBN (Print) | 3540425160 |

DOIs | |

State | Published - 2001 |

Event | 1st International Workshop on Algorithms in Bioinformatics, WABI 2001 - Arhus, Denmark Duration: Aug 28 2001 → Aug 31 2001 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2149 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 1st International Workshop on Algorithms in Bioinformatics, WABI 2001 |
---|---|

Country/Territory | Denmark |

City | Arhus |

Period | 8/28/01 → 8/31/01 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science