Buy the Book

  GEP Biblio

  Visit Gepsoft


© C. FERREIRA, 2002 (Terms of Use) ISBN: 9729589054

Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence

Transposition of insertion sequence elements
Any sequence in the genome can become an IS element and, therefore, these elements are randomly selected throughout the chromosome. The transposon is copied and the copy is then inserted at a randomly chosen point in the head of a gene, except the first position. Typically, a transposition rate pis of 0.1 and a set of three IS elements of different length is used. The transposition operator randomly chooses the chromosome, the start of the IS element, the target site, and the length of the transposon.

Figure 3.14 shows two populations of two-genic individuals where variation was introduced by transposition alone. As an illustration and because only IS transposition is being used to introduce variation, a pis of 1.0 was chosen. Furthermore, a set of three IS elements with lengths 2, 3, and 5 was used. As shown in Figure 3.14, this operator alone can also make populations evolve and find solutions. Indeed, chromosome 8 of generation 13 is a perfect solution to the majority function problem. This chromosome is a descendant of chromosome 5 of generation 12. The event of transposition that led to the creation of this perfect solution is shown in Figure 3.15. The Boolean expressions encoded in both chromosomes are also shown.

Generation N: 0
AbOabcOAOOaacaccacbccANaObOAbNaabcbcccbcbb-[0] = 6
AaAOaOOaAAbbacabcabbcOAAcONaOAccabbbcabbbc-[1] = 6
OaAbcNbaNaabccbbbcaaaNbcbNbAANbacabacacbcb-[2] = 5
ObbbAONNNAccaccbabcbcAAcacObOAaabaaaacbaca-[3] = 7
ONNAbObbONabcabbcbbcbAObaNbOAcbcccbcbaaabb-[4] = 4
ANabONNNcabbcccabcbacAbObOcAaAbabacacaabcb-[5] = 6
AONNObONOOaaacbaaababOAOAANaObacbbcccbbcaa-[6] = 4
NNbabcNbNNcbaacaabcccAbNcANNbbObababbcabaa-[7] = 6
NONNAaAbAOcacaaababccObaabbOabababacaacbab-[8] = 6
NONbcANNONcabbacaccabAbaOcOAacNbbccbacacba-[9] = 6


Generation N: 12
ANabcaabbcbbcccabcbacAbOcAaAbaaabacacaabcb-[0] = 7
AaANbAaANcbbcccabcbacAbOOcAaAbaabacacaabcb-[1] = 7
AAaANcaabbbbcccabcbacAbcccOOcAaabacacaabcb-[2] = 6
ANababbcbObbcccabcbacAbOcAaAbaaabacacaabcb-[3] = 7
ANacaabbcbbbcccabcbacAbOcAaAbaaabacacaabcb-[4] = 6
AAbaaANcaabbcccabcbacAbOOcAaAbaabacacaabcb-[5] = 7
ANababbcbObbcccabcbacAAbaabbObcabacacaabcb-[6] = 6
ANababbcbObbcccabcbacAbOcaabcAaabacacaabcb-[7] = 7
ANcababbcbbbcccabcbacAbccabObOcabacacaabcb-[8] = 5
ANaabbcbObbbcccabcbacAbOcAaAbaaabacacaabcb-[9] = 7

Generation N: 13
ANaabbcbObbbcccabcbacAbOcAaAbaaabacacaabcb-[0] = 7
ANabcaabbcbbcccabcbacAbOcbcAaAbabacacaabcb-[1] = 6
ANacbabbcbbbcccabcbacAbOcaabcAaabacacaabcb-[2] = 6
ANababbcbObbcccabcbacAbObOccaababacacaabcb-[3] = 6
AaANbAaANcbbcccabcbacAbOAOcAaAbabacacaabcb-[4] = 6
ANacababbcbbcccabcbacAbOcAaAbaaabacacaabcb-[5] = 6
ANcababbcbbbcccabcbacAbcabObOcaabacacaabcb-[6] = 5
ANcababbcbbbcccabcbacAbccabObOcabacacaabcb-[7] = 5
AcabAbaaANbbcccabcbacAbOOcAaAbaabacacaabcb-[8] = 8
AccaAbaaANbbcccabcbacAbOOcAaAbaabacacaabcb-[9] = 7

Figure 3.14. An initial population and its later descendants created via IS transposition to solve the Majority (a, b, c) function problem. The chromosomes encode sub-ETs linked by OR. Note that none of the later descendants are identical to the ancestors of the initial population. Note also the appearance of repetitive sequences in the genome in later generations. The perfect solution found in generation 13 (chromosome 8) and its mother (chromosome 5 of generation 12) are shown in blue. The event of transposition that led to this perfect solution is shown in Figure 3.15.

As shown in Figure 3.15, during transposition, IS elements are copied into the head of the target gene. In this case, the sequence “cab” (positions 14-16 in gene 1) is activated and jumps to the insertion site, bond 1 in gene 1 (between positions 0 and 1). As a result, a copy of the transposon appears at the site of insertion. Note also that a sequence with as many symbols as the IS element is deleted at the end of the head (in this case, the sequence “caa” is deleted). Thus, despite this insertion, the structural organization of chromosomes is maintained and, therefore, all the new individuals created by IS transposition are syntactically correct programs.

Figure 3.15. Illustration of IS transposition and its effects. a) An event of IS transposition with the transposon shown in bold. Note that a sequence with three elements is deleted at the end of the head of the target gene. Note also that, in this case, the transposon ends up duplicated in the daughter chromosome. b) The sub-ETs encoded in the mother chromosome (before IS transposition). c) The sub-ETs encoded in the daughter chromosome (after IS transposition). The transposon nodes are shown in gray. Note that the insertion changed drastically the sub-ET1, creating a new sub-ET two nodes smaller than the mother.

Note that transposition is also a macromutator, causing very profound modifications in the ETs. Obviously, the more upstream the insertion site the more drastic the change. For example, the sub-ET1 shown in Figure 3.15 was shortened by two nodes due to transposition.

You have certainly noticed that the examples I have chosen in order to illustrate the mechanisms and effects of the genetic operators, have always resulted in fitter descendants. Remember, however, that in the vast majority of cases, their actions result in less fit or even defective individuals. But, as in nature, evolution happens because of these extremely rare, highly improbable events.

Home | Contents | Previous | Next