{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:02:47Z","timestamp":1648692167189},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,2,23]],"date-time":"2012-02-23T00:00:00Z","timestamp":1329955200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2012,2,23]],"date-time":"2012-02-23T00:00:00Z","timestamp":1329955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2012,6]]},"abstract":"Abstract<\/jats:title>\n There are various definitions of a gene cluster determined by two genomes and methods for finding these clusters. However, there is little work on characterizing configurations of genes that are eligible to be a cluster according to a given definition. For example, given a set of genes in a genome, is it always possible to find two genomes such that their intersection is exactly this cluster? In one version of this problem, we make use of the graph theory to reformulated it as follows: Given a graph G<\/jats:italic> with n<\/jats:italic> vertices, do there exist two \u03b8<\/jats:italic>-powers of paths G<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub>=(V<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub>,E<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub>) and G<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>=(V<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>,E<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>) such that G<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub>\u2229G<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub> contains G<\/jats:italic> as an induced subgraph? In this work, we divide the problem in two cases, depending on whether or not G<\/jats:italic> is an induced subgraph of G<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub> or G<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>. We show an \n $\\mathcal{O}(n^{2})$<\/jats:tex-math>\n <\/jats:inline-formula> time algorithm that generates the smallest \u03b8<\/jats:italic>-powers of paths G<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub> and G<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub> (with respect to and the number of vertices) that contains G<\/jats:italic> as an induced subgraph. Finally, we discuss the problem when G<\/jats:italic> is an induced subgraph neither of G<\/jats:italic>\n \n S<\/jats:italic>\n <\/jats:sub> nor of G<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub> and we present a method of finding the smallest power of a path when graph G<\/jats:italic> is a cycle C<\/jats:italic>\n \n n<\/jats:italic>\n <\/jats:sub>.<\/jats:p>","DOI":"10.1007\/s13173-012-0064-8","type":"journal-article","created":{"date-parts":[[2012,2,22]],"date-time":"2012-02-22T12:21:25Z","timestamp":1329913285000},"page":"129-136","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Gene clusters as intersections of powers of paths"],"prefix":"10.1007","volume":"18","author":[{"given":"V\u00edtor","family":"Costa","sequence":"first","affiliation":[]},{"given":"Simone","family":"Dantas","sequence":"additional","affiliation":[]},{"given":"David","family":"Sankoff","sequence":"additional","affiliation":[]},{"given":"Ximing","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,23]]},"reference":[{"key":"64_CR1","first-page":"134","volume-title":"Lecture Notes in Bioinformatics","author":"Z Adam","year":"2008","unstructured":"Adam Z, Choi V, Sankoff D, Zhu Q (2008) Generalized gene adjacencies, graph bandwidth and clusters in yeast evolution. In: Lecture Notes in Bioinformatics, vol 4983, pp 134\u2013145"},{"key":"64_CR2","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1016\/j.disc.2009.10.006","volume":"310","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt A, Hundt C, Mancini F, Wagner P (2010) Rooted directed path graphs are leaf powers. Discrete Math 310:897\u2013910","journal-title":"Discrete Math"},{"key":"64_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil DG, Kim H, Natarajan S, Olariu S, Sprague A (1995) Simple linear time recognition of unit interval graphs. Inf Process Lett 55:99\u2013104","journal-title":"Inf Process Lett"},{"key":"64_CR4","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(95)00133-W","volume":"56","author":"CMH Figueiredo","year":"1995","unstructured":"Figueiredo CMH, Meidanis J, Mello CP (1995) A linear-time algorithm for proper interval graph recognition. Inf Process Lett 56:179\u2013184","journal-title":"Inf Process Lett"},{"key":"64_CR5","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.dam.2010.03.012","volume":"159","author":"MC Lin","year":"2011","unstructured":"Lin MC, Rautenbach D, Soulignac FJ, Szwarcfiter JL (2011) Powers of cycles, powers of paths, and distance graph. Discrete Appl Math 159:621\u2013627","journal-title":"Discrete Appl Math"},{"key":"64_CR6","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.endm.2009.11.041","volume":"35","author":"MC Lin","year":"2009","unstructured":"Lin MC, Soulignac FJ, Szwarcfiter JL (2009) Short models for unit interval graphs. Electron Notes Discrete Math 35:247\u2013255","journal-title":"Electron Notes Discrete Math"},{"key":"64_CR7","volume-title":"Representations of indifference relations","author":"FS Roberts","year":"1968","unstructured":"Roberts FS (1968) Representations of indifference relations. Stanford University, Stanford"},{"key":"64_CR8","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-540-85557-6_14","volume":"5167","author":"D Sankoff","year":"2008","unstructured":"Sankoff D, Xu X (2008) Tests for gene clusters satisfying the generalized criterion. Lect Notes Comput Sci 5167:152\u2013160","journal-title":"Lect Notes Comput Sci"},{"key":"64_CR9","volume-title":"On proper and helly circular-arc graphs","author":"FJ Soulignac","year":"2010","unstructured":"Soulignac FJ (2010) On proper and helly circular-arc graphs. Universidad de Buenos Aires, Buenos Aires"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0064-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-012-0064-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0064-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0064-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:19:39Z","timestamp":1630520379000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-012-0064-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,23]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["64"],"URL":"http:\/\/dx.doi.org\/10.1007\/s13173-012-0064-8","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":["General Computer Science"],"published":{"date-parts":[[2012,2,23]]},"assertion":[{"value":"31 January 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}