title: An algorithm to enumerate all possible protein conformations verifying a set of distance constraints.
abstract: BACKGROUND
  The determination of protein structures satisfying distance constraints is an important problem in structural biology. Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature. Most of them, however, are designed to find one solution only.
  
  
  RESULTS
  In order to explore exhaustively the feasible conformational space, we propose here an interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to protein structure determination. This algorithm is based on a discretization of the problem obtained by recursively constructing a search space having the structure of a tree, and by verifying whether the generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used here are directly related to features of protein conformations.
  
  
  CONCLUSIONS
  We described the new algorithm iBP to generate protein conformations satisfying distance constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm iBP has been applied on three α-helical peptides.
authors: LIX, Ecole Polytechnique, Palaiseau, 91128, France. cassioliandre@gmail.com.
authors: Andrea
authors: A
authors: Cassioli
authors: Institut Pasteur, Structural Bioinformatics Unit, 25, rue du Dr Roux, Paris, 75015, France. benjamin.bardiaux@pasteur.fr.|CNRS UMR3528, 25, rue du Dr Roux, Paris, 75015, France. benjamin.bardiaux@pasteur.fr.
authors: Benjamin
authors: B
authors: Bardiaux
authors: Institut Pasteur, Structural Bioinformatics Unit, 25, rue du Dr Roux, Paris, 75015, France. guillaume.bouvier@pasteur.fr.|CNRS UMR3528, 25, rue du Dr Roux, Paris, 75015, France. guillaume.bouvier@pasteur.fr.
authors: Guillaume
authors: G
authors: Bouvier
authors: Université de Rennes-I, Rennes, France. antonio.mucherino@irisa.fr.
authors: Antonio
authors: A
authors: Mucherino
authors: LIX, Ecole Polytechnique, Palaiseau, 91128, France. rafaelsoalves@uol.com.br.
authors: Rafael
authors: R
authors: Alves
authors: LIX, Ecole Polytechnique, Palaiseau, 91128, France. liberti@lix.polytechnique.fr.|IBM TJ Watson Research Center, NY Yorktown Heights, 10598, USA. liberti@lix.polytechnique.fr.
authors: Leo
authors: L
authors: Liberti
authors: Institut Pasteur, Structural Bioinformatics Unit, 25, rue du Dr Roux, Paris, 75015, France. michael.nilges@pasteur.fr.|CNRS UMR3528, 25, rue du Dr Roux, Paris, 75015, France. michael.nilges@pasteur.fr.
authors: Michael
authors: M
authors: Nilges
authors: University of Campinas (IMECC-UNICAMP), Campinas-SP, 13083-859, Brasil. clavor@ime.unicamp.br.
authors: Carlile
authors: C
authors: Lavor
authors: Institut Pasteur, Structural Bioinformatics Unit, 25, rue du Dr Roux, Paris, 75015, France. therese.malliavin@pasteur.fr.|CNRS UMR3528, 25, rue du Dr Roux, Paris, 75015, France. therese.malliavin@pasteur.fr.
authors: Thérèse E
authors: TE
authors: Malliavin
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D006801:Humans; D008958:Models, Molecular; D010446:Peptide Fragments / Q000737:chemistry*; D011487:Protein Conformation; D011506:Proteins / Q000737:chemistry*
chemical_list: D010446:Peptide Fragments; D011506:Proteins
references: J Comput Biol. 2011 Nov;18(11):1507-23
references: 22035328
references: J Am Chem Soc. 2006 Oct 11;128(40):13112-22
references: 17017791
references: J Biol Chem. 2014 Jun 13;289(24):17203-14
references: 24742668
references: Biopolymers. 2013 Mar;99(3):218-22
references: 23023942
references: Methods Mol Biol. 2012;831:429-51
references: 22167686
references: Methods Mol Biol. 2004;278:353-78
references: 15318003
references: Proteins. 2003 Oct 1;53(1):111-20
references: 12945054
references: IUBMB Life. 2001 Dec;52(6):291-302
references: 11895078
references: J Biol Chem. 2003 Dec 26;278(52):52980-7
references: 14555647
references: Protein Sci. 2011 Jun;20(6):970-85
references: 21413097
references: J Chem Inf Model. 2014 Jan 27;54(1):289-301
references: 24397493
references: Protein Eng. 1988 Apr;2(1):27-38
references: 2855369
references: PLoS Comput Biol. 2006 Feb;2(2):e9
references: 16462939
references: J Mol Biol. 1985 Dec 5;186(3):611-26
references: 2419572
references: Protein Sci. 2007 Jan;16(1):69-81
references: 17192589
references: J Biomol NMR. 2009 Nov;45(3):265-81
references: 19711185
references: Annu Rev Biophys Biomol Struct. 2000;29:291-325
references: 10940251
references: J Biomol NMR. 2009 Aug;44(4):213-23
references: 19548092
references: Curr Opin Struct Biol. 2009 Apr;19(2):164-70
references: 19327983
references: Bioinformatics. 2015 May 1;31(9):1490-2
references: 25543048
references: J Mass Spectrom. 2003 Dec;38(12):1225-37
references: 14696200
references: J Bioinform Comput Biol. 2012 Jun;10(3):1242009
references: 22809385
references: J Mol Biol. 1997 Oct 17;273(1):283-98
references: 9367762
references: J Am Chem Soc. 2004 Jun 16;126(23):7281-92
references: 15186165
references: Bioinformatics. 2005 Apr 1;21(7):1028-36
references: 15546935
references: Proteins. 2010 Nov 15;78(15):3205-11
references: 20827723
references: Proc Natl Acad Sci U S A. 2014 Jan 28;111(4):1391-6
references: 24474763
references: J Comput Chem. 2003 Jan 30;24(2):232-43
references: 12497602
references: J Am Chem Soc. 2007 Apr 25;129(16):5228-34
references: 17397158
references: J Comput Biol. 2006 Sep;13(7):1267-88
references: 17037958
references: Biopolymers. 1983 Dec;22(12):2577-637
references: 6667333
references: Proteins. 2006 Oct 1;65(1):203-19
references: 16897780
references: Expert Opin Drug Discov. 2013 Jul;8(7):821-34
references: 23642085
references: Proteins. 2014 Mar;82(3):466-78
references: 24038133
references: Proc IEEE Comput Syst Bioinform Conf. 2005;:189-202
references: 16447976
references: Proc Natl Acad Sci U S A. 2010 Jun 22;107(25):11341-6
references: 20534508
references: Proteins. 2011 May;79(5):1525-37
references: 21365680
references: J Comput Biol. 2013 Apr;20(4):296-310
references: 23113706
references: Proteins. 1998 Jul 1;32(1):26-42
references: 9672040
references: Bioinformatics. 2007 Feb 1;23(3):381-2
references: 17121777
references: Science. 1995 May 26;268(5214):1144-9
references: 7761829