Title: Computing approximate solutions of the protein structure determination problem using global constraints on discrete crystal lattices

Authors: Alessandro Dal Palu, Agostino Dovier, Enrico Pontelli

Addresses: Dipartimento di Matematica, Universita di Parma, Viale G.P. Usberti, 53/A-43100 Parma, Italy. ' Dipartimento di Matematica e Informatica, Universita di Udine, Via delle Scienze, 206-33100 Udine, Italy. ' Department of Computer Science, New Mexico State University, P.O. Box 30001, MSC CS, Las Cruces, NM 88003, USA

Abstract: Crystal lattices are discrete models of the three-dimensional space that have been effectively employed to facilitate the task of determining proteins| natural conformation. This paper investigates alternative global constraints that can be introduced in a constraint solver over discrete crystal lattices. The objective is to enhance the efficiency of lattice solvers in dealing with the construction of approximate solutions of the protein structure determination problem. Some of them (e.g., self-avoiding-walk) have been explicitly or implicitly already used in previous approaches, while others (e.g., the density constraint) are new. The intrinsic complexities of all of them are studied and preliminary experimental results are discussed.

Keywords: protein structure determination; global constraints; constraint solving; discrete crystal lattices; bioinformatics.

DOI: 10.1504/IJDMB.2010.030964

International Journal of Data Mining and Bioinformatics, 2010 Vol.4 No.1, pp.1 - 20

Published online: 14 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article