Information Technology Reference
In-Depth Information
Table 1.
Pseudo-code of the proposed hybrid immune algorithm for the MSA
Hybrid Immune Algorithm
(
d, dup, τ
B
,T
max
)
1.
t ←
0;
2.
FFE ←
0;
3.
N
c
← d × dup
;
P
(
t
)
d
4.
←
Initialize Population(
d
);
Strip Gaps(
P
(
t
d
);
5.
Evaluate(
P
(
t
)
d
6.
);
7.
FFE ← FFE
+
d
;
8.
while
(
FFE < T
max
)
do
P
(
clo
)
N
c
←
Cloning (
P
(
t
d
,dup
);
9.
P
(
gap
)
N
c
←
Gap operators (
P
(
clo
)
d
10.
);
Strip Gaps(
P
(
gap
)
N
c
11.
);
Evaluate(
P
(
gap
)
N
c
12.
);
13.
FFE ← FFE
+
N
c
;
P
(
block
)
N
c
←
BlockShuing operators (
P
(
clo
)
d
14.
);
15.
Compute Weights();
16.
Normalize Weights();
Strip Gaps(
P
(
block
)
N
c
17.
);
Evaluate(
P
(
block
)
N
c
18.
);
19.
FFE ← FFE
+
N
c
;
(
a
P
(
t
)
d
,
a
P
(
gap
)
N
c
,
a
P
(
block
)
N
c
) = Elitist-Aging(
P
(
t
)
d
,P
(
gap
)
N
c
,P
(
block
)
N
c
20.
,τ
B
);
P
(
t
+1)
d
←
(
μ
+
λ
)-Selection(
a
P
(
t
d
,
a
P
(
gap
)
,
a
P
(
block
)
N
c
21.
);
N
c
22.
t ← t
+1;
23.
end while
to frequent premature convergence to the local optimal during the convergence
process. Therefore, we have developed new hypermutation operators, specific to
the multiple sequence alignments, which insert or remove gaps in the sequences
— called
GAP operator
or
BlockShu
ing operator
.
BGAPOp tor
This operator acts on the cloned B cells generating a new population
P
(
gap
)
N
c
.
It is based on two procedures, one inserts (InsGap), and the other removes
(RemGap) adjacent sequences of gaps. Initially, the GAP operator chooses what
procedure to apply using a random uniform distribution, i.e. if a number of
adjacent gaps needs to be inserted into the sequences or removed. Then a number
k
, in the range [1
,θ
], of (adjacent) gaps is randomly choosen, where
θ
represents
a percentage of the alignments length. After several experiments setting
θ
=2%
was obtained.
The InsGap procedure can be summarize in the following steps: split the
n
sequences in
z
groups. During the experimental tests,
z
= 2 has been the best
setting for the performances of the proposed algorithm. Hence, we can rephrase
