dc.creator | Alcón, Liliana Graciela | |
dc.creator | Cerioli, Márcia R. | |
dc.creator | Figueiredo, Celina M. H. de | |
dc.creator | Gutiérrez, Marisa | |
dc.creator | Meidanis, João | |
dc.date | 2007 | |
dc.date | 2019-10-09T16:59:23Z | |
dc.identifier | http://sedici.unlp.edu.ar/handle/10915/82964 | |
dc.identifier | issn:0166-218X | |
dc.description | Many problems involving DNA can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a DNA molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and, in the affirmative case, produces a loop representation for the tree. | |
dc.description | Facultad de Ciencias Exactas | |
dc.format | application/pdf | |
dc.format | 686-694 | |
dc.language | en | |
dc.rights | http://creativecommons.org/licenses/by-nc-sa/4.0/ | |
dc.rights | Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) | |
dc.subject | Matemática | |
dc.subject | Computational molecular biology | |
dc.subject | DNA fragment assembly problem | |
dc.subject | DNA physical mapping | |
dc.subject | Interval graphs | |
dc.subject | Interval number | |
dc.title | Tree loop graphs | |
dc.type | Articulo | |
dc.type | Articulo | |