A greedy algorithm for optimal recombination(2)

denote the collection of all sequences of length n over \Sigma. For any s1 = a1a2 \Delta \Delta \Delta a j a j+1 \Delta \Delta \Delta an, s2 = b1b2 \Delta \Delta \Delta b j b j+1 \Delta \Delta \Delta bn 2 \Sigma

is minimized among all such possible recombination processes.

s= b b bj bj bn 2 n; a recombination for s and s at position j (1 j n? 1) is de ned as the following operation: an From s=a a aj aj s=b b bj bj bn bn to t=a a aj bj t=b b bj aj an . It is denoted by R(s; s; j; t; t ); or R(s; s; j ): Both s and s are called parents and both t and t are called children. n: S is called a recombination ancestor of A if De nition 2. Let A; S A can be generated from S by a series of recombinations, i.e., there exist a series of recombinations Ri(s i; s i; j i; t i; t i ) (i= 1; 2;; p) such that (1)s i; s i

2 S ft k; t k j 1 k i? 1g; (2)A S ft i; t i j 1 i pg: Ri(s i; s i; j i; t i; t i ) (i= 1; 2;; p) is called a recombination process generating A from S . It is called optimal if the number p of recombination steps2 1 2+1 1 2 1 1 2+1 2 1 2+1 1 1 2+1 2 1 2+1 1 2 1 2 1 2 1 2 1 2 ( ) 1 ( ) 2 ( ) 1 ( ) 2 ( ) ( ) 1 ( ) 1 ( ) 2 ( ) 2 ( ) 1 ( ) 2 ( ) ( ) 1 ( ) 2 ( ) 1 ( ) 2

Recombination Problem 1 Let A n and S a recombination ancestor of A. Find the optimal recombination process generating A from S . Denote n(S; A) the number of optimal recombination steps generating A from S . Example 1. Let A= fa= 01010; a= 10001; a= 10110; a= 11001g and S= fs= 00101; s= 11010g: We have n(S; A)= 4 and the following is an optimal recombination process generating A from S . R (s; s; 1; a; b ): From 0 0101=b=s 1 1010=b=s To 0 1010=b=a 1 0101=b R (b; s; 2; b; b ): From 10 101=b 11 010=b To 10 010=b 11 101=b R (b; s; 3; a; a ): From 101 01=b 110 10=b To 101 10=b=a 110 01=b=a R (s; b; 3; a; b ): From 001 01=b 100 10=b To 001 10=b 100 01=b=a If S consists of only two sequences, then Problem 1 can be regarded as one with j j= 2: For binary case, S= f00 0; 11 1g always generates an arbitrary binary sequence by recombinations. So it is a recombination ancestor for any A1 2 3 4 1 2 1 1 2 1 4 1 1 2 2 3 1 4 2 4 2 5 6 4 2 5 6 3 4 2 3 4 4 2 7 3 8 4 4 1 5 2 9 1 5 9 10 2