SODA Conference 2000 Conference Paper
Algorithmic strategies in combinatorial chemistry
- Deborah Goldman
- Sorin Istrail
- Giuseppe Lancia
- Antonio Piccolboni
- Brian Walenz
Author name cluster
Deborah Goldman
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
3 papers
1 author row
Possible papers
3FOCS Conference 1999 Conference Paper
Algorithmic Aspects of Protein Structure Similarity
- Deborah Goldman
- Sorin Istrail
- Christos H. Papadimitriou
We show that calculating contact map overlap (a measure of similarity of protein structures) is NP-hard, but can be solved in polynomial time for several interesting and relevant special cases. We identify an important special case of this problem corresponding to self-avoiding walks, and prove a decomposition theorem and a corollary approximation result for this special case. These are the first approximation algorithms with guaranteed error bounds, and NP-completeness results in the literature in the area of protein structure alignment/fold recognition for measures of structure similarity of practical interest.
STOC Conference 1998 Conference Paper
On the Complexity of Protein Folding (Extended Abstract)
- Pierluigi Crescenzi
- Deborah Goldman
- Christos H. Papadimitriou
- Antonio Piccolboni
- Mihalis Yannakakis