Information Technology Reference
In-Depth Information
2
Previous Work with Evolutionary Algorithms
As we commented, many authors have been working on several evolutionary
algorithms, especially genetic algorithms (GA), to determine the final folded
conformations using the HP model [22]. One of the main decisions is the en-
coding of the problem which has to be optimized, in this case, the genotypic
encoding of the protein conformation in the lattice. Three basic possibilities
can be considered to the representation of the folded sequence in the lattice:
Cartesian coordinates and two alternatives with internal coordinates.
In the first case, the location of each amino acid is specified independently with
its Cartesian coordinates. With the internal coordinates the embedding of the
protein is specified as a sequence of moves taken on the lattice from one amino
acid to the next. The first alternative with internal coordinates uses an absolute
representation [23] and moves are specified with respect to it. For example, in
the case of the square lattice: North, South, East and West. A conformation
is expressed as a sequence
1
, which is the genetic material in
the individuals when this representation is used. In the relative representation,
relative moves are considered. The reference system is not fixed and the next
move depends on the previous move. Now, in the same case as before, three
moves are allowed: Forward, Turn Left and Turn Right. The conformations are
expressed now as sequences
n−
{
N, S, E, W
}
n−
1
. This representation has the advantage
of guaranteeing that all solutions are 1-step self-avoiding (because there is no
back move).
{
F, L, R
}
2.1
Initial Population, Space of Feasible Conformations and Fitness
Alternatives
Unger and Moult [23] only considered feasible conformations in the genetic popu-
lation, that is, embeddings that are self-avoiding paths on the considered lattice.
In their work, when operators such as mutation and crossover were applied, the
GA iterated until a “nonlethal” (in authors' words) conformation was generated.
Similarly, Rylance [17] obtained the initial population using a recoil growth al-
gorithm. Song et al. [19] applied the genetic operators used in [3], with 6 types
of mutations; according to the authors, one of them (cornerchange, which mu-
tates one shape to another shape) makes the conformation has more biological
significance.
Patton et al. [15] used the relative representation. In addition, unlike the pre-
vious authors, they allowed illegal conformations, but using a penalty in the
fitness to avoid self-avoiding constraints. This essentially allows the search to
proceed through illegal states. With these modifications the results were a bit
better in terms of minimization of energy and required computational steps.
Krasnogor et al. [12] analyzed the impact of different factors when evolutionary
algorithms are used to the problem: the conformational representation, the en-
ergy formulation and the way in which infeasible conformations are penalized.
Their results supported the use of the relative encoding.
Search WWH ::
Custom Search