A novel algorithm reported August 2 in the PNAS could help uncover better methods to compare three-dimensional protein structures, say authors of the report. In addition, they say, it could help in the development of ways to determine whether proteins can assume more than one biologically active conformation.

There are two main techniques used to quantify similarity of the three-dimensional structures of a pair of proteins, Rachel Kolodny, of Stanford University, Calif., and Nathan Linial, of Hebrew University, Jerusalem, explain in their paper. The first—including the most commonly used three-dimensional protein structure comparison server, Dali—computes the distances between corresponding locations in each of the proteins and then compares these distances. The second in essence superimposes each protein on the other and measures how close they match.

The new approach aligns proteins for comparison via the second approach. It is not heuristic; instead, it exhaustively computes all the ways each protein can rotate and translate in space and finds optimal solutions. When the algorithm fails to find a good alignment, the researchers say it is certain none exist. The fact that each molecular bond in a protein exists in three-dimensional space helps limit the ways that it can align, shrinking the scope of the problem somewhat. Their method was successfully validated on several pairs of small, well studied proteins, comparing their structures in space and scoring the degree of matching.

"In the first method, imagine you're looking at distances between fingers in the right hand and then the left. These are internal distances. The other option is if you place two hands next to each other," Kolodny told The Scientist. "Internal distances will stay fixed no matter how each hand is placed. With the second method, if you move your left hand, distances will change." The second method therefore needs to first uncover the rigid transformation that optimally positions both proteins vis-a-vis each other.

A prevailing sentiment among researchers using either or both approaches is that comparisons of protein structures require computational resources that rapidly become great in size, Kolodny and Linial write in their PNAS paper. Researchers often therefore conclude that investigations should concentrate on heuristic approaches—that is, ones that do not aim for provably correct solutions, gaining computational performance at the potential cost of accuracy or precision.

Kolodny and Linial write that there is not much point in measuring the exact coordinates of atoms in proteins for structure comparisons, since proteins are flexible and structures fluctuate about a mean position. They contend structure comparisons close to exact can all prove equally interesting. In addition, the authors say their algorithm could also be used to tackle the open problem of detecting multiple three-dimensional conformations a protein can adopt that can prove equally viable from a biological point of view.

Before the study, Kolodny said it was rumored this approach was a non-deterministic polynomial-time complete, or NP-complete, problem. Such problems require time that grows exponentially with the size of the problem, which means "there is no sense developing an algorithm for, since there is no way they will be efficient," Kolodny explained. She and Linial instead proved it was a polynomial-time problem, one that is computationally feasible, a problem that computers could grow fast enough to solve within minutes 10 or so years from now, Kolodny said.

The researchers said their algorithm is too slow to be a useful everyday tool. To analyze even a single pair of relatively small proteins, the algorithm took a day on a multiple processor machine, while common protein structure analysis programs take at most a few minutes, Kolodny said. Still, "we feel it will help a lot in designing other structural alignment methods," she said. For example, she said, it could be used to evaluate other protein structure comparison algorithms, potentially to help improve them, research she recently submitted for publication.

Herbert Edelsbrunner of Duke University, Durham, NC, who did not participate in this work, called it "surprising and innovative." He said it is too early to say whether the new algorithm will lead to something practical, adding it could be made much faster. "Biologists would want to know how much they can push the algorithm—improve its performance—while still giving good guarantees on the result," he said. "Can it be fast enough so that people would make it their algorithm of choice?"

Eric Martz, with RasMol-derived Protein Explorer macromolecular visualization freeware project, refused to comment. A scientist at computational science company Accelrys could not be reached for comment.