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.

DIMACS Homepage
Contacting the Center
Document last modified on March 28, 2000.