Dotted interval graphs and high throughput genotyping

ABSTRACT

We introduce a generalization of interval graphs, which we call dotted interval graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (=dotted intervals). Coloring of dotted intervals graphs naturally arises in the context of high throughput genotyping. We study the properties of dotted interval graphs, with a focus on coloring. We show that any graph is a DIG but that DIGd graphs, i.e. DIGs in which the arithmetic progressions have a jump of at most d, form a strict hierarchy. We show that coloring DIGd, graphs is NP-complete even for d = 2. For any fixed d, we provide a 7/8d approximation for the coloring of DIGd graphs.

REFERENCES

• 1: Yonatan Aumann, Efrat Manisterski, and Zohar Yakhini. Designing optimally multiplexed SNP genotyping assays. In Proceedings of the Third International Workshop on Algorithms in Bioinformatics, WABI 2003, volume 2812 of Lecture Notes in Computer Science, pages 255--283, 2003.
• 2: Reuven Bar-Yehuda , Magnús M. Halldórsson , Joseph (Seffi) Naor , Hadas Shachnai , Irina Shapira, Scheduling split intervals, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.732-741, January 06-08, 2002, San Francisco, California
• 3: Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 4: M. R. Garey, D. S. Johnson, G. L. Miller, C. H. Papadimitriou. The Complexity of coloring circular arcs and chords. In SIAM Journal of Algebraic Discrete Methods, 1(2):216--227, 1980.
• 5: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 6: András Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs. Discrete Math., 55:161--166, 1985.
• 7: András Gyárfás and Douglas West. Multitrack interval graphs. Congr. Numer., 109:109--116, 1995.
• 8: Teemu Kivioja, Mikko Arvas, Kari Kataja. Merja Penttila, Hans Soberlund, and Esko Ukkonen. Assigning probes into a small number of pools separable by electrophoresis. Bioinformatics, 18(1):199--206, January 2002.
• 9: E. W. Knapik, A. Goodman, M. Ekker et al. A microsatellite genetic linkage map for zebrafish (Danio rerio). In Nature Genetics, 18:338--343, 1998.
• 10: N. Kumar and N. Deo. Multidimensional interval graphs. Congr. Numer., 102:45--56, 1994.
• 11: T. A. McKee, F. R. McMorris. Topics in intersection graph theory. SIAM, 1999.
• 12: W. S. Oetting, H. K. Lee, D. J. Flanders, G. L. Wiesner, T. A. Sellers, R. A. King. Linkage analysis with multiplexed short tandem repeat polymorphisms using infrared fluorescence and M13 tailed primers. In Genomics, 30:450--458, 1995.
• 13: T. Pastinen, J. Partanen, A. C. Syvnen. Multiplex, fluorescent, solid-phase minisequencing for efficient screening of DNA sequence variation. In Clin. Chem., 42:1391--1397, 1996.
• 14: G. D. Schuler, M. S. Boguski, E. A. Stewart et al. A gene map of the human genome. In Science, 274:540--546, 1996.
• 15: W. K. Shih and W. L. Hsu. An approximation algorithm for coloring circular-arc graphs. Technical report, Sinica, China, 1989.
• 16: Jr. W. T. Trotter and F. Harary. On double and multiple interval graphs. Journal of Graph Theory, 3:205--211, 1979.
• 17: D. B. West, D. B. Shmoys. Recognizing graphs with fixed interval number is NP-complete. In Discrete Applied Mathematics, 8:295--305, 1984.
• 18: Z. Yakhini, P. Webb, and R. Roth. Partitioning of polymorphic DNAs. US Patent 6,074,831, 2000.
• 19: L. Zane, L. Bargelloni, and T. Patarnello. Strategies for microsatellite isolation: a review. Molecular Ecology, 11:1--16, 2002.