Biomaterial Database

Exploiting symmetry properties of the discretizable molecular distance geometry problem. 2012

Antonio Mucherino, and Carlile Lavor, and Leo Liberti

IRISA, University of Rennes 1, Rennes, France. antonio.mucherino@irisa.fr

The Discretizable Molecular Distance Geometry Problem (DMDGP) involves a subset of instances of the distance geometry problem for which some assumptions allowing for discretization are satisfied. The search domain for the DMDGP is a binary tree that can be efficiently explored by employing a Branch & Prune (BP) algorithm. We showed in recent works that this binary tree may contain several symmetries, which are directly related to the total number of solutions of DMDGP instances. In this paper, we study the possibility of exploiting these symmetries for speeding up the solution of DMDGPs, and propose an extension of the BP algorithm that we named symmetry-driven BP (symBP). Computational experiments on artificial and protein instances are presented.

UI	MeSH Term	Description	Entries
D008958	Models, Molecular	Models used experimentally or theoretically to study molecular shape, electronic properties, or interactions; includes analogous molecules, computer-generated graphics, and mechanical structures.	Molecular Models,Model, Molecular,Molecular Model
D011506	Proteins	Linear POLYPEPTIDES that are synthesized on RIBOSOMES and may be further modified, crosslinked, cleaved, or assembled into complex proteins with several subunits. The specific sequence of AMINO ACIDS determines the shape the polypeptide will take, during PROTEIN FOLDING, and the function of the protein.	Gene Products, Protein,Gene Proteins,Protein,Protein Gene Products,Proteins, Gene
D000465	Algorithms	A procedure consisting of a sequence of algebraic formulas and/or logical steps to calculate or determine a given task.	Algorithm