{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:39:50Z","timestamp":1787323190897,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The interval graph for a set of intervals on a line consists of one vertex for each interval and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and nonprobes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and nonprobes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.<\/jats:p>","DOI":"10.1137\/130930091","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T14:47:37Z","timestamp":1445957257000},"page":"2006-2046","source":"Crossref","is-referenced-by-count":3,"title":["Linear-Time Recognition of Probe Interval Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Ross M.","family":"McConnell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yahav","family":"Nussbaum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,10,27]]},"reference":[{"key":"atypb1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,\n                      The Design and Analysis of Computer Algorithms\n                      , Addison-Wesley, Reading, MA, 1974."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.45.11.1607"},{"key":"atypb3","unstructured":"K. S. Booth,\n                      PQ-Tree Algorithms\n                      , Ph.D. thesis, Department of Computer Science, University of California, Berkeley, 1975."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"atypb5","first-page":"368","author":"Chandler D. B.","year":"2007","journal-title":"Heidelberg"},{"key":"atypb6","first-page":"521","author":"Chang G. J.","year":"2005","journal-title":"Heidelberg"},{"key":"atypb7","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , MIT Press, Cambridge, MA, 2009."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"C. Crespelle and I. Todinca,\n                      An $O(n^2)$-time algorithm for the minimal interval completion problem\n                      , in TAMC 2010, Lecture Notes in Comput. Sci. 6108, J. Kratochvil, ed., Springer, Heidelberg, 2010, pp. 175-186.","DOI":"10.1007\/978-3-642-13562-0_17"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1101\/gr.074906.107"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)10075-1"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic and A. N. Trenk,\n                      Tolerance Graphs\n                      , Cambridge Stud. Adv. Math. 89, Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511542985"},{"key":"atypb14","first-page":"477","author":"Johnson J. L.","year":"2001","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"atypb16","first-page":"761","author":"R.","year":"2004","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1032-7"},{"key":"atypb18","first-page":"421","author":"McConnell R. M.","year":"2005","journal-title":"Heidelberg"},{"key":"atypb19","first-page":"866","author":"McConnell R. M.","year":"2002","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"atypb21","first-page":"41","author":"McConnell R. M.","year":"2009","journal-title":"Proceedings of the European Symposium on Algorithms"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00077-8"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00078-X"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"P. Pevzner,\n                      Computational Molecular Biology: An Algorithmic Approach\n                      , MIT Press, Cambridge, MA, 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts716"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/0209001"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"R. Uehara,\n                      Canonical data structure for interval probe graphs\n                      , in ISAAC 2004, Lecture Notes in Comput. Sci. 3341, R. Fleischer and G. Trippen, eds., Springer, Heidelberg, 2004, pp. 859-870.","DOI":"10.1007\/978-3-540-30551-4_73"},{"key":"atypb29","unstructured":"P. Zhang,\n                      Probe Interval Graph and Its Applications to Physical Mapping of DNA\n                      , manuscript, 1994."},{"key":"atypb30","first-page":"309","volume":"10","author":"Zhang P.","year":"1994","journal-title":"Comput. Appl. Biosci."},{"key":"atypb31","unstructured":"P. Zhang,\n                      United States Patent $5667970\\!:$ Method of Mapping DNA Fragments\n                      , July 3, 2000."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130930091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:08Z","timestamp":1787320028000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130930091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130930091"],"URL":"https:\/\/doi.org\/10.1137\/130930091","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}