Probe Interval Orders

David E. Brown () and Larry J. Langley ()
Additional contact information
David E. Brown: Utah State University
Larry J. Langley: University of the Pacific

A chapter in The Mathematics of Preference, Choice and Order, 2009, pp 313-322 from Springer

Abstract: 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.

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:stcchp:978-3-540-79128-7_18

Ordering information: This item can be ordered from
http://www.springer.com/9783540791287

DOI: 10.1007/978-3-540-79128-7_18

Access Statistics for this chapter

More chapters in Studies in Choice and Welfare from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().