title: Ballast: a ball-based algorithm for structural motifs.
abstract: Structural motifs encapsulate local sequence-structure-function relationships characteristic of related proteins, enabling the prediction of functional characteristics of new proteins, providing molecular-level insights into how those functions are performed, and supporting the development of variants specifically maintaining or perturbing function in concert with other properties. Numerous computational methods have been developed to search through databases of structures for instances of specified motifs. However, it remains an open problem how best to leverage the local geometric and chemical constraints underlying structural motifs in order to develop motif-finding algorithms that are both theoretically and practically efficient. We present a simple, general, efficient approach, called Ballast (ball-based algorithm for structural motifs), to match given structural motifs to given structures. Ballast combines the best properties of previously developed methods, exploiting the composition and local geometry of a structural motif and its possible instances in order to effectively filter candidate matches. We show that on a wide range of motif-matching problems, Ballast efficiently and effectively finds good matches, and we provide theoretical insights into why it works well. By supporting generic measures of compositional and geometric similarity, Ballast provides a powerful substrate for the development of motif-matching algorithms.
authors: Department of Computer Science, Dartmouth College, Hanover, NH 03755, USA.
authors: Lu
authors: L
authors: He
authors: Fabio
authors: F
authors: Vandin
authors: Gopal
authors: G
authors: Pandurangan
authors: Chris
authors: C
authors: Bailey-Kellogg
mesh_terms: D000465:Algorithms; D020816:Amino Acid Motifs; D001426:Bacterial Proteins / Q000737:chemistry* / Q000235:genetics / Q000378:metabolism; D001665:Binding Sites; D020134:Catalytic Domain; D003198:Computer Simulation; D004926:Escherichia coli / Q000201:enzymology / Q000235:genetics*; D008958:Models, Molecular; D010751:Phosphopyruvate Hydratase / Q000737:chemistry* / Q000235:genetics / Q000378:metabolism; D017434:Protein Structure, Tertiary; D040681:Structural Homology, Protein
chemical_list: D001426:Bacterial Proteins; D010751:Phosphopyruvate Hydratase
references: J Mol Biol. 1994 Oct 21;243(2):327-44
references: 7932758
references: J Mol Biol. 2004 Jun 4;339(3):607-33
references: 15147845
references: Proc Natl Acad Sci U S A. 1991 Dec 1;88(23):10495-9
references: 1961713
references: Bioinformatics. 2003 Sep 1;19(13):1644-9
references: 12967960
references: J Comput Biol. 2007 Jul-Aug;14(6):791-816
references: 17691895
references: Biochemistry. 1996 Dec 24;35(51):16489-501
references: 8987982
references: Genome Biol. 2009 Feb 02;10(2):207
references: 19226439
references: J Mol Biol. 1977 May 25;112(3):535-42
references: 875032
references: IEEE Trans Pattern Anal Mach Intell. 1987 May;9(5):698-700
references: 21869429
references: J Comput Aided Mol Des. 2009 Nov;23(11):773-84
references: 19543979
references: Proc Natl Acad Sci U S A. 2008 Apr 8;105(14):5441-6
references: 18385384
references: Nucleic Acids Res. 2004 Jan 1;32(Database issue):D129-33
references: 14681376
references: Biochemistry. 2006 Feb 28;45(8):2545-55
references: 16489747
references: J Mol Biol. 1999 Apr 23;288(1):147-64
references: 10329133
references: Proteins. 2004 Jun 1;55(4):962-76
references: 15146493
references: J Mol Biol. 1999 Jan 29;285(4):1887-97
references: 9917419
references: J Mol Biol. 2003 Feb 21;326(3):955-78
references: 12581652
references: Protein Sci. 1997 Nov;6(11):2308-23
references: 9385633
references: Bioinformatics. 2008 Aug 15;24(16):i105-11
references: 18689810
references: Protein Eng. 2003 Aug;16(8):543-52
references: 12968072
references: BMC Bioinformatics. 2010 Nov 11;11:555
references: 21070651
references: J Mol Graph Model. 1997 Aug;15(4):245-53
references: 9524934