TY - GEN
T1 - An improved backtracking method for EDAs based protein folding
AU - Chen, Benhui
AU - Li, Long
AU - Hu, Jinglu
PY - 2009/12/1
Y1 - 2009/12/1
N2 - Many Evolutionary Algorithm (EA) based methods have been proposed to solve protein structure prediction (PSP) problem in HP-lattice model. One of common difficulties of those methods is the existence of invalid individuals produced by geometrical constraints in the conformation of protein (i.e. self-avoidance in the chain). A backtracking method is often used to repair the invalid individuals of genetic search in those methods. However, there is a disadvantage in basic backtracking method, the repairing computational cost is very heavy for long sequence instances. This paper proposes an improved backtracking-based repairing method for long sequence protein folding. A detection procedure is added in backtracking method to avoid entering invalid closed areas when selecting directions for the residues. Experimental results show that the proposed method can significantly reduce the number of backtracking searching operations and the computational cost for the long protein sequences.
AB - Many Evolutionary Algorithm (EA) based methods have been proposed to solve protein structure prediction (PSP) problem in HP-lattice model. One of common difficulties of those methods is the existence of invalid individuals produced by geometrical constraints in the conformation of protein (i.e. self-avoidance in the chain). A backtracking method is often used to repair the invalid individuals of genetic search in those methods. However, there is a disadvantage in basic backtracking method, the repairing computational cost is very heavy for long sequence instances. This paper proposes an improved backtracking-based repairing method for long sequence protein folding. A detection procedure is added in backtracking method to avoid entering invalid closed areas when selecting directions for the residues. Experimental results show that the proposed method can significantly reduce the number of backtracking searching operations and the computational cost for the long protein sequences.
KW - Backtracking
KW - Estimation of Distribution Algorithms (EDAs)
KW - HP model
KW - Protein structure prediction (PSP)
UR - http://www.scopus.com/inward/record.url?scp=77951119953&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951119953&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:77951119953
SN - 9784907764333
T3 - ICCAS-SICE 2009 - ICROS-SICE International Joint Conference 2009, Proceedings
SP - 4669
EP - 4674
BT - ICCAS-SICE 2009 - ICROS-SICE International Joint Conference 2009, Proceedings
T2 - ICROS-SICE International Joint Conference 2009, ICCAS-SICE 2009
Y2 - 18 August 2009 through 21 August 2009
ER -