Information Technology Reference
In-Depth Information
this step as follows: randomly choose a value
m
[1
,n
[
,
and split the
n
sequences
into two groups: 1
st
group from 1 to
m
sequences, and 2
nd
group from (
m
+1)
to
n
; randomly choose two integer values
x
and
y,
in such way that
k
adjacent
gaps are insterted beginning from column
x
for the first group, and from column
y
for the second group; randomly choose a subsequence shift direction
D,
either
left or right; finally, to insert the
k
adjacent gaps in the relative positions for
each sequence, and shift the subsequence to the
D
direction. During the shifting
phase, it is possible to miss
n
∈
0 bits with value 1; in this case, InsGap will
select
n
bits with value 0, different from the
k
gaps inserted, and they will be
flipped to 1, rebuilding the correct sequence. Figure 1, plot (a), shows an example
of how the InsGap procedure works, with
k
=3
,m
= 2 and right shift direction.
≥
Fig. 1.
GAP operator has the purpose to insert, by
InsGap
procedure (a), or remove,
by
RemGap
procedure (b), adjacent gaps into the proposed alignment
RemGap procedure,simply,remove
k
adjacent gaps, and move the sub-
sequences towards a randomly chosen direction, either left or right. Plot (b) of
figure 1 shows an example of such an operator.
C
BlockShuing Operator
The second perturbation operator is the BlockShuffling operator,which
is based on the block definition. This operator moves aligned blocks left or right:
a block is selected in each alignment starting from a random point in a se-
quence.Three different approaches where developed: BlockMove moves whole
blocks either to the left or to the right; BlockSplitHor divides the blocks in
two levels, upper and lower, and shifting only one level, randomly chosen; and
BlockSplitVer, which randomly choose a column in the block which divides
it into two sides (left and right), and shifting only one side, randomly chosen as
well. Figure 2 summarizes the three operators.
Finally, the function Strip Gaps(
P
(
∗
)
) moves matched gap columns to the
right end side of the matrix. This function is always applied before the fitness
function is evaluated.
