On The Number Of Realizations Of Certain Henneberg Graphs Arising In Protein Conformation

dc.creatorLiberti L.
dc.creatorMasson B.
dc.creatorLee J.
dc.creatorLavor C.
dc.creatorMucherino A.
dc.date2014
dc.date2015-06-25T17:56:34Z
dc.date2015-11-26T14:46:05Z
dc.date2015-06-25T17:56:34Z
dc.date2015-11-26T14:46:05Z
dc.date.accessioned2018-03-28T21:55:34Z
dc.date.available2018-03-28T21:55:34Z
dc.identifier
dc.identifierDiscrete Applied Mathematics. , v. 165, n. , p. 213 - 232, 2014.
dc.identifier0166218X
dc.identifier10.1016/j.dam.2013.01.020
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-84893779235&partnerID=40&md5=f616244709fbd085f9a1a14287d88419
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/87066
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/87066
dc.identifier2-s2.0-84893779235
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1252694
dc.descriptionSeveral 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. © 2013 Elsevier B.V. All rights reserved.
dc.description165
dc.description
dc.description213
dc.description232
dc.descriptionBarvinok, A., Problems of distance geometry and convex properties of quadratic maps (1995) Discrete and Computational Geometry, 13, pp. 189-202
dc.descriptionBerger, B., Kleinberg, J., Leighton, T., Reconstructing a three-dimensional model with arbitrary errors (1999) Journal of the ACM, 46 (2), pp. 212-235
dc.descriptionBiswas, P., Lian, T., Wang, T., Ye, Y., Semidefinite programming based algorithms for sensor network localization (2006) ACM Transactions on Sensor Networks, 2, pp. 188-220
dc.descriptionBlumenthal, L., (1953) Theory and Applications of Distance Geometry, , Oxford University Press Oxford
dc.descriptionBrady, T., Watt, C., On products of Euclidean reflections (2006) American Mathematical Monthly, 113, pp. 826-829
dc.descriptionConnelly, R., Generic global rigidity (2005) Discrete & Computational Geometry, 33, pp. 549-563
dc.descriptionCoope, I., Reliable computation of the points of intersection of n spheres in Rn (2000) The Australian and New Zealand Industrial and Applied Mathematics Journal, 42, pp. 461-C477
dc.descriptionCremona, L., (1872) Le Figure Reciproche Nella Statica Grafica, , G. Bernardoni Milano
dc.descriptionCrippen, G., Havel, T., (1988) Distance Geometry and Molecular Conformation, , Wiley New York
dc.descriptionDattorro, J., (2005) Convex Optimization and Euclidean Distance Geometry, , Meboo Palo Alto
dc.descriptionDong, Q., Wu, Z., A geometric build-up algorithm for solving the molecular distance geometry problem with sparse distance data (2003) Journal of Global Optimization, 26, pp. 321-333
dc.descriptionEren, T., Goldenberg, D., Whiteley, W., Yang, Y., Morse, A., Anderson, B., Belhumeur, P., Rigidity, computation, and randomization in network localization (2004) IEEE Infocom Proceedings, pp. 2673-2684
dc.descriptionGraver, J., Rigidity matroids (1991) SIAM Journal on Discrete Mathematics, 4, pp. 355-368
dc.descriptionGraver, J., Servatius, B., Servatius, H., (1993) Combinatorial Rigidity, , American Mathematical Society
dc.descriptionGunther, H., (1995) NMR Spectroscopy: Basic Principles, Concepts, and Applications in Chemistry, , Wiley New York
dc.descriptionHendrickson, B., Conditions for unique graph realizations (1992) SIAM Journal on Computing, 21 (1), pp. 65-84
dc.descriptionHenneberg, L., (1911) Die Graphische Statik der Starren Systeme, , Teubner Leipzig
dc.descriptionJohn, A.L.-S., (2008) Geometric Constraint Systems with Applications in Cad and Biology, , Ph.D. Thesis, University of Massachusetts at Amherst
dc.descriptionKang, R., Müller, T., Sphere and dot product representations of graphs (2011) Proceedings of SCG11, pp. 308-314. , ACM
dc.descriptionLavor, C., Lee, J., John, A.L.-S., Liberti, L., Mucherino, A., Sviridenko, M., Discretization orders for distance geometry problems (2012) Optimization Letters, 6, pp. 783-796
dc.descriptionLavor, C., Liberti, L., Maculan, N., (2006) The Discretizable Molecular Distance Geometry Problem, , Tech. Rep. q-bio/0608012, arXiv
dc.descriptionLavor, C., Liberti, L., Maculan, N., Mucherino, A., The discretizable molecular distance geometry problem (2012) Computational Optimization and Applications, 52, pp. 115-146
dc.descriptionLavor, C., Liberti, L., Mucherino, A., The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances (2011) Journal of Global Optimization, , http://dx.doi.org/10.1007/s10898-011-9799-6
dc.descriptionLavor, C., Mucherino, A., Liberti, L., Maculan, N., An artificial backbone of hydrogens for finding the conformation of protein molecules (2009) Proceedings of the Computational Structural Bioinformatics Workshop, pp. 152-155. , IEEE Washington, DC, USA
dc.descriptionLavor, C., Mucherino, A., Liberti, L., Maculan, N., Computing artificial backbones of hydrogen atoms in order to discover protein backbones (2009) Proceedings of the International Multiconference on Computer Science and Information Technology, pp. 751-756. , IEEE Mragowo, Poland
dc.descriptionLavor, C., Mucherino, A., Liberti, L., Maculan, N., Discrete approaches for solving molecular distance geometry problems using NMR data (2010) International Journal of Computational Bioscience, 1, pp. 88-94
dc.descriptionLavor, C., Mucherino, A., Liberti, L., Maculan, N., On the computation of protein backbones by using artificial backbones of hydrogens (2011) Journal of Global Optimization, 50, pp. 329-344
dc.descriptionLiberti, L., Lavor, C., Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem (2008) International Transactions in Operational Research, 15, pp. 1-17
dc.descriptionLiberti, L., Lavor, C., Mucherino, A., Maculan, N., Molecular distance geometry methods: From continuous to discrete (2010) International Transactions in Operational Research, 18, pp. 33-51
dc.descriptionLiberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A., On the number of solutions of the discretizable molecular distance geometry problem (2011) Combinatorial Optimization, Constraints and Applications, 6831 VOL., pp. 322-342. , COCOA11 LNCS Springer New York
dc.descriptionMenger, K., Untersuchungen über allgemeine Metrik (1928) Mathematische Annalen, 100, pp. 75-163
dc.descriptionMucherino, A., Lavor, C., The branch and prune algorithm for the molecular distance geometry problem with inexact distances (2009) Proceedings of the International Conference on Computational Biology, 58 VOL., pp. 349-353. , World Academy of Science, Engineering and Technology
dc.descriptionMucherino, A., Lavor, C., Liberti, L., Exploiting symmetry properties of the discretizable molecular distance geometry problem (2012) Journal of Bioinformatics and Computational Biology, 10, p. 1242009. , (1-15)
dc.descriptionMucherino, A., Lavor, C., Liberti, L., The discretizable distance geometry problem (2012) Optimization Letters, 6, pp. 1671-1686
dc.descriptionMucherino, A., Lavor, C., Liberti, L., Maculan, N., On the definition of artificial backbones for the discretizable molecular distance geometry problem (2009) Mathematica Balkanica, 23, pp. 289-302
dc.descriptionMucherino, A., Lavor, C., Liberti, L., Talbi, E.-G., A parallel version of the branch & prune algorithm for the molecular distance geometry problem (2010) ACS/IEEE International Conference on Computer Systems and Applications, pp. 1-6. , AICCSA10 IEEE Hammamet, Tunisia
dc.descriptionMucherino, A., Lavor, C., Liberti, L., Talbi, E.-G., On suitable parallel implementations of the branch & prune algorithm for distance geometry (2010) Proceedings of the Grid5000, , Spring School Lille, France
dc.descriptionMucherino, A., Liberti, L., Lavor, C., MD-jeep: An implementation of a branch-and-prune algorithm for distance geometry problems (2010) Mathematical Software, 6327 VOL., pp. 186-197. , K. Fukuda, J. van der Hoeven, M. Joswig, N. Takayama, LNCS Springer New York
dc.descriptionNilges, M., Macias, M., O'Donoghue, S., Oschkinat, H., Automated NOESY interpretation with ambiguous distance restraints: The refined NMR solution structure of the Pleckstrin homology domain from β-spectrin (1997) Journal of Molecular Biology, 269, pp. 408-422
dc.descriptionSaviotti, C., Nouvelles méthodes pour le calcul des travures réticulaires (1885) Appendix to L. Cremona, les Figures Réciproques en Statique Graphique, pp. 37-100. , Gauthier-Villars Paris
dc.descriptionSaviotti, C., (1888) La Statica Grafica: Lezioni, , U. Hoepli Milano
dc.descriptionSaxe, J., Embeddability of weighted graphs in k-space is strongly NP-hard (1979) Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480-489
dc.descriptionSchlick, T., (2002) Molecular Modelling and Simulation: An Interdisciplinary Guide, , Springer New York
dc.descriptionSchoenberg, I., Remarks to Maurice Fréchet's article sur la définition axiomatique d'une classe d'espaces distanciés vectoriellement applicable sur l'espace de Hilbert (1935) Annals of Mathematics, 36 (3), pp. 724-732
dc.descriptionSo, A.M.-C., Ye, Y., Theory of semidefinite programming for sensor network localization (2007) Mathematical Programming, Series B, 109, pp. 367-384
dc.descriptionTay, T.-S., Whiteley, W., Generating isostatic frameworks (1985) Structural Topology, 11, pp. 21-69
dc.descriptionWhiteley, W., Infinitesimally rigid polyhedra. I. Statics of frameworks (1984) Transactions of the American Mathematical Society, 285 (2), pp. 431-465
dc.descriptionWhiteley, W., Infinitesimally rigid polyhedra. II: Modified spherical frameworks (1988) Transactions of the American Mathematical Society, 306 (1), pp. 115-139
dc.descriptionZhu, Z., So, A.M.-C., Ye, Y., Universal rigidity and edge sparsification for sensor network localization (2010) SIAM Journal on Optimization, 20 (6), pp. 3059-3081
dc.languageen
dc.publisher
dc.relationDiscrete Applied Mathematics
dc.rightsfechado
dc.sourceScopus
dc.titleOn The Number Of Realizations Of Certain Henneberg Graphs Arising In Protein Conformation
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución