Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/68731
Type: Artigo
Title: On the number of realizations of certain Henneberg graphs arising in protein conformation
Author: Liberti, Leo
Benoit, Masson
Lee, Jon
Lavor, Carlile
Mucherino, Antonio
Abstract: Several application fields require finding Euclidean coordinates consistent with a set of distances. More precisely, given a simple undirected edge-weighted graph, we wish to find a realization in a Euclidean space so that adjacent vertices are placed at a distance which is equal to the corresponding edge weight. Realizations of a graph can be either flexible or rigid. In certain cases, rigidity can be seen as a property of the graph rather than the realization. In the last decade, several advances have been made in graph rigidity, but most of these, for applicative reasons, focus on graphs having a unique realization. In this paper we consider a particular type of weighted Henneberg graphs that model protein backbones and show that almost all of them give rise to sets of incongruent realizations whose cardinality is a power of two. (C) 20113 Elsevier B.V. All rights reserved.
Several application fields require finding Euclidean coordinates consistent with a set of distances. More precisely, given a simple undirected edge-weighted graph, we wish to find a realization in a Euclidean space so that adjacent vertices are placed at a distance which is equal to the corresponding edge weight. Realizations of a graph can be either flexible or rigid. In certain cases, rigidity can be seen as a property of the graph rather than the realization. In the last decade, several advances have been made in graph rigidity, but most of these, for applicative reasons, focus on graphs having a unique realization. In this paper we consider a particular type of weighted Henneberg graphs that model protein backbones and show that almost all of them give rise to sets of incongruent realizations whose cardinality is a power of two.
Subject: Geometria de distâncias
Teoria dos grafos
Algoritmos branch-and-prune
Proteínas – Conformação
Country: Países Baixos
Editor: Elsevier
Citation: Discrete Applied Mathematics. Elsevier Science Bv, v. 165, n. 213, n. 232, 2014.
Rights: fechado
Identifier DOI: 10.1016/j.dam.2013.01.020
Address: https://www.sciencedirect.com/science/article/pii/S0166218X13000449
Date Issue: 2014
Appears in Collections:IMECC - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000332354200020.pdf1.02 MBAdobe PDFView/Open


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