## DIMACS TR: 98-12

## Tagged Probe Interval Graphs

### Authors: Li Sheng, Chi Wang and Peisen Zhang

**
ABSTRACT
**

A generalization of interval graph is introduced for cosmid contig
mapping of DNA. A graph is a tagged probe interval graph if its vertex
set can be partitioned into two subsets of probes and nonprobes, and a
closed interval can be assigned to each vertex such that two vertices
are adjacent if and only if at least one of them is a probe and one
end of its corresponding interval is contained in the interval
corresponding to the other vertex. We show that tagged probe interval
graphs are weakly triangulated graphs, hence are perfect graphs. For a
tagged probe interval graph with a given partition, we give a chordal
completion that is consistent to any tagged interval completions with
respect to the same vertex partition. Forbidden induced subgraph lists
are given for trees with or without a given vertex partition. A
heuristic that construct map candidates is given for cosmid contig
mapping.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-12.ps.gz

DIMACS Home Page