TY - CHAP
T1 - A symmetry-free subspace for Ab initio protein folding simulations
AU - Gan, X C
AU - Kapsokalivas, L
AU - Albrecht, A A
AU - Steinhofel, K
A2 - Elloumi, M
A2 - Kung, J
A2 - Linial, M
A2 - Murphy, R F
A2 - Schneider, K
A2 - Toma, C
PY - 2008
Y1 - 2008
N2 - Ab initio protein structure prediction usually tries to find a ground state in an extremely large phase space. Stochastic search algorithms are often employed by using a predefined energy function. However, for each valid conformation in the search phase space, there are usually several counterparts that are reflective, rotated or reflectively rotated forms of the current conformation, imprecisely called isometric conformations here. In protein folding, these isometric conformations correspond to the different rotation states caused by admissible protein structure transitions. In structure prediction, these isometric conformations, owning the same energy value, not only significantly increase the search complexity but also degrade the stability of some local search algorithms. In this paper, we will prove that there exists a subspace that is unique (no two conformations in the space are isometric) and complete (for any valid conformation, there exists a corresponding conformation in the subspace that is a reflective or rotated form of it). We demonstrate that this subspace, which is about 1/24 of the conventional search space in the 3D lattice model and 1/8 in the 2D model contains the lowest energy conformation, and all other isometric lowest energy forms can then be obtained by protein rotation. Our experiments show that the subspace can significantly speed up existing local search algorithms
AB - Ab initio protein structure prediction usually tries to find a ground state in an extremely large phase space. Stochastic search algorithms are often employed by using a predefined energy function. However, for each valid conformation in the search phase space, there are usually several counterparts that are reflective, rotated or reflectively rotated forms of the current conformation, imprecisely called isometric conformations here. In protein folding, these isometric conformations correspond to the different rotation states caused by admissible protein structure transitions. In structure prediction, these isometric conformations, owning the same energy value, not only significantly increase the search complexity but also degrade the stability of some local search algorithms. In this paper, we will prove that there exists a subspace that is unique (no two conformations in the space are isometric) and complete (for any valid conformation, there exists a corresponding conformation in the subspace that is a reflective or rotated form of it). We demonstrate that this subspace, which is about 1/24 of the conventional search space in the 3D lattice model and 1/8 in the 2D model contains the lowest energy conformation, and all other isometric lowest energy forms can then be obtained by protein rotation. Our experiments show that the subspace can significantly speed up existing local search algorithms
M3 - Conference paper
SN - 1865-0929
T3 - COMMUNICATIONS IN COMPUTER AND INFORMATION SCIENCE
SP - 128
EP - 139
BT - Bioinformatics Research and Development, Proceedings
PB - Springer
CY - BERLIN
T2 - 2nd International Conference on Bioinformatics Research and Development
Y2 - 1 January 2008
ER -