Premium
Modified genetic algorithm resolves ambiguous NOE restraints and reduces unsightly NOE violations
Author(s) -
Adler Marc
Publication year - 2000
Publication title -
proteins: structure, function, and bioinformatics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.699
H-Index - 191
eISSN - 1097-0134
pISSN - 0887-3585
DOI - 10.1002/(sici)1097-0134(20000601)39:4<385::aid-prot110>3.0.co;2-j
Subject(s) - constraint (computer aided design) , consistency (knowledge bases) , interpretation (philosophy) , residual , algorithm , ideal (ethics) , computer science , local consistency , genetic algorithm , mathematics , mathematical optimization , artificial intelligence , constraint satisfaction , geometry , philosophy , epistemology , probabilistic logic , programming language
Abstract In an ideal world, every NOE cross peak would have a unique assignment. However, the interpretation of NOE peaks is frequently complicated by overlapping resonances. In theory, ambiguous assignments could be resolved by performing separate structure calculations with each possible interpretation. Unfortunately, this would require an astronomical amount of computing time. A modified genetic algorithm has been developed that efficiently resolves hundreds of ambiguous restraints in parallel. Each NOE assignment becomes a gene that can be passed on to a new generation. New individuals are constructed by making a constraint lists from a subset of the genes. The constraint lists are then tested for self‐consistency by using molecular dynamics to generate new structures for each list. To a first‐degree approximation, there is enough information retained in each list to determine the global fold of the protein. Self‐consistent constraint lists receive higher scores and their genes (or NOEs) stand a better chance of surviving into the next generation. The process selects NOEs that are consistent with the global fold. Under normal conditions, the program converges in 3 to 8 generations using 70 structures per generation. The final constraints are self‐consistent and contain almost no residual NOE violations. Proteins 2000;39:385–392. © 2000 Wiley‐Liss, Inc.