Tree loop graphs

dc.creatorAlcón, Liliana Graciela
dc.creatorCerioli, Márcia R.
dc.creatorFigueiredo, Celina M. H. de
dc.creatorGutiérrez, Marisa
dc.creatorMeidanis, João
dc.date2007
dc.date2019-10-09T16:59:23Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/82964
dc.identifierissn:0166-218X
dc.descriptionMany 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.descriptionFacultad de Ciencias Exactas
dc.formatapplication/pdf
dc.format686-694
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rightsCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
dc.subjectMatemática
dc.subjectComputational molecular biology
dc.subjectDNA fragment assembly problem
dc.subjectDNA physical mapping
dc.subjectInterval graphs
dc.subjectInterval number
dc.titleTree loop graphs
dc.typeArticulo
dc.typeArticulo


Este ítem pertenece a la siguiente institución