Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Tree loop graphs
Author: Alcon, L
Cerioli, MR
de Figueiredo, CMH
Gutierrez, M
Meidanis, J
Abstract: 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 it loop representation for the tree. (c) 2006 Elsevier B.V. All rights reserved.
Subject: interval graphs
interval number
computational molecular biology
DNA fragment assembly problem
DNA physical mapping
Country: Holanda
Editor: Elsevier Science Bv
Citation: Discrete Applied Mathematics. Elsevier Science Bv, v. 155, n. 41826, n. 686, n. 694, 2007.
Rights: fechado
Identifier DOI: 10.1016/j.dam.2005.01.001
Date Issue: 2007
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000245794600003.pdf187.24 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.