Probe Interval Orders

A graph G is a

probe interval graph

if there is a partition of

V

(G) into

P

and

N

and a collection {

I

v

:

v

∊

V

(

G

)} of intervals of R in one-to-one correspondence with

V

(

G

) such that uv ∊

E

(

G

) if and only if

I

u

∩

I

v

≠ Ø and at least one of

u

,

v

belongs to

P

. The sets

P

and

N

are called the

probes

and

nonprobes

, respectively, and {

I

v

= [

l

(

v

),

r

(

v

)] :

v

∊

V

(

G

)} together with the partition will be referred to as a

representation

. An interval graph is a probe interval graph with

N

= Ø and this class of graphs has been studied extensively; see the texts Fishburn (1985), Golumbic (1980), and Roberts (1976) for introductions and other references.

The probe interval graph model was invented in connection with the task called

physical mapping

faced in connection with the human genome project (Zhang, 1994, 1997; Zhang et al., 1994). In DNA sequencing projects, a

contig

is a set of overlapping DNA segments derived from a single genetic source. In order for DNA to be more easily studied, small fragments of it, called clones, are taken from multiple copies of the same genome. Physical mapping is the process of determining how DNA contained in a group of clones overlap without having to sequence all the DNA in the clones. Once the map is determined, the clones can be used as a resource to efficiently contain stretches of genome. If we are interested in overlap information between each pair of clones, we can use an interval graph to model this problem: vertices are clones and adjacency represents overlap. Using the probe interval graph model, we can use any subset of clones, label them as probes, and test for overlap between a pair of clones if and only if at least one of them is a probe. This way there is flexibility, in contrast to the interval graph model, since all DNA fragments need not be known at time of construction of the probe interval graph model. Consequently, the size of the data set, which by nature can be quite large, is reduced.