### Probe Interval Graph and Its
Applications In Physical Mapping
of Human Chromosomes

**Peisen Zhang**
Department of Genetics and Development

Columbia University, New York

A new graph, so-called probe interval graph (PIG) has been
introduced. It is an extension of the interval graph. Given two sets
of vertices P-vertices P and T-vertices T, an undirected graph G(P,T)
is called a probe interval graph, if its vertices can be put into
one-to-one correspondence with two groups of intervals: P-vertices to
probe intervals and T-vertices to target (non-probe) intervals, of a
linearly ordered set (like the real line) such that two vertices are
connected by an edge of G if and only if their corresponding intervals
have non empty intersection and at least one vertex be P-vertex.

If we put T empty, we will get an interval graph. Probe interval graph
arises in the physical mapping contexts of human genome
project. Biologists make probes by labeling some fragments of
chromosome. They use those probes to scan the whole library of DNA
fragments to get overlapping data. That is a probe interval graph. In
addition to the fundamental properties (i.e. triangulated property) of
PIG, the following topics will be discussed. 1) Lexicographic
Breadth-First Search algorithm for PIG. 2) Modified P-Q tree algorithm
for PIG. 3) PIG Sandwich problem. 4) Applications in mapping of Human
Chromosome 13.

STS interval graph (STSIG) is a special case of PIG with all the
p-vertices are not overlapping. Some discuss about STSIG will be
given.

If we do not know the P set and the T set in advance, what will
happen? There are some open problems.

Program

DIMACS Homepage

Contacting the Center

Document last modified on March 28, 2000.