# DIMACS Seminar on Math and CS in Biology

## Title:

On Constructing Radiation Hybrid Maps

## Speaker:

- Amir Ben-Dor
- Technion

## Place:

- Seminar Room 431, CoRE Building
- Rutgers University.

## Time:

- 11:00 a.m.
- Thursday, May 1, 1997

Abstract:
Radiation hybrid (RH) mapping is a somatic cell method for obtaining ordering
information of markers on a chromosome, using relatively few experiments.
Given the results of a typical RH experiment, finding the true order
of the markers is a challenging algorithmic problem.

In this work we present several simple algorithms for
ordering and mapping the markers, where the input is the genomic data
obtained from RH experiments. We provide a rigorous analysis of these
algorithms. In particular, we show that under the standard statistical
model for RH, our algorithms are ``statistically consistent''. That
is, given enough hybrids, the algorithms do reconstruct the true
markers order (with high probability). We also prove a simple lower bound
for the number of hybrids required (by any algorithm) to correctly
reconstruct the order.

We have implemented these algorithms, and tested them on synthetic and real
data. These simulations show that for practical input sizes (number of markers
and hybrids) our algorithms produce outputs that are very close to the true
ordering.

Document last modified on April 24, 1997