Tree loop graphs

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 definit...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Cerioli, Márcia R., Figueiredo, Celina M. H. de, Gutiérrez, Marisa, Meidanis, João
Formato: Articulo
Lenguaje:Inglés
Publicado: 2007
Materias:
Matemática
Computational molecular biology
DNA fragment assembly problem
DNA physical mapping
Interval graphs
Interval number
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/82964
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-82964
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
Computational molecular biology
DNA fragment assembly problem
DNA physical mapping
Interval graphs
Interval number
spellingShingle Matemática
Computational molecular biology
DNA fragment assembly problem
DNA physical mapping
Interval graphs
Interval number
Alcón, Liliana Graciela
Cerioli, Márcia R.
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
Meidanis, João
Tree loop graphs
topic_facet Matemática
Computational molecular biology
DNA fragment assembly problem
DNA physical mapping
Interval graphs
Interval number
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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Cerioli, Márcia R.
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
Meidanis, João
author_facet Alcón, Liliana Graciela
Cerioli, Márcia R.
Figueiredo, Celina M. H. de
Gutiérrez, Marisa
Meidanis, João
author_sort Alcón, Liliana Graciela
title Tree loop graphs
title_short Tree loop graphs
title_full Tree loop graphs
title_fullStr Tree loop graphs
title_full_unstemmed Tree loop graphs
title_sort tree loop graphs
publishDate 2007
url http://sedici.unlp.edu.ar/handle/10915/82964
work_keys_str_mv AT alconlilianagraciela treeloopgraphs
AT ceriolimarciar treeloopgraphs
AT figueiredocelinamhde treeloopgraphs
AT gutierrezmarisa treeloopgraphs
AT meidanisjoao treeloopgraphs
bdutipo_str Repositorios
_version_ 1764820488109948928

Ejemplares similares