DIMACS TR: 98-12

Tagged Probe Interval Graphs

Authors: Li Sheng, Chi Wang and Peisen Zhang


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