A greedy algorithm for optimal recombination(3)

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

f0; 1gn: Moreover, given any recombination ancestor S= fsi si sin ji= 1; 2g of A= fai ai ain ji= 1; 2;; kg, for each 1 j n; we de ne a function fj on fs j; s j g(s j= s j ) such that fj (s j )= 0 and fj (s j )= 1: Then we get 6 S= ff (s )f (s ) fn (s n ); f (s )f (s ) fn (s n )g= f00 0; 11 1g and A= ff (ai )f (ai ) fn (ain)ji= 1; 2;; kg: And n(S; A)= n(S; A ): For j j= 2; Recombination Problem 1 is reduced to the following simple form.1 2 1 2 1 2 1 2 1 2 0 1 11 2 12 1 1 21 2 22 2 0 1 1 2 2 0 0

Recombination Problem 2 Let A f0; 1gn be an arbitrary collection of binary sequences and S= f00 0; 11 1g: Find the optimal recombination process generating A from S .In this paper, we discuss Problem 2 and nd algorithms for it.

1.2 Terminology and notation De nition 3. Let a= a a ap aq an 2 f0; 1gn: I= a p; q]= ap ap aq is called an alternative segment of a if ai 6= ai for all p i q? 1: An alternative block is a maximal alternative segment. Denote Ia= fI; I;; Ik g the collection of all alternative blocks of a: De ne the core of a as Ca= a s; t], which is the minimum segment of a containing all Ii (1 i k): P ne the De length of a p; q] as l(a p; q])= q? p and the length of Ia as l(Ia )= k l(Ij ): j Denote P (A)= fpj1 p n? 1; ap= ap for some a 2 Ag: For example, 6 if a= 111010111010000100; then I= a 3; 7]= 10101; I= 1010; I= 010: Ia= fI; I; I g: Ca= a 3; 17]= 101011101000010: l(I )= 4 and l(Ia )= 9: De nition 4. Let a; b 2 f0; 1gn with Ca= a p; q] and Cb= b u; v]: If u p q v and a p; q]= b p; q], we say that b cov

ers a, denoted by a b: b and a are called disjoint or independent if q u, or v p, denoted by a\ b=;. If q u, we say a< b: For any alternative segments ( or blocks) I and J; we similarly de ne I J; I\ J=;, and I< J: De nition 5. Denote C(A)= fCa ja 2 Ag. A is called a nest of sequences if a b; or b a for any a; b 2 A: It is called a tree of sequences if either a\ b=;; or a b; or b a for any a; b 2 A: For a; b 2 A; if b a and there exists no c 2 A such that b c a with c= a and c= b, then b is called 6 6 a branch of a: Denote Ba the collection of all branches of a in A. A branch is called a leaf (or youngest branch) if it has no branch in A. a 2 A is called a root (or oldest branch) if it is not a branch of any other sequences in A.1 2+1+1 1 2=1+1 1 2 3 1 2 3 1

1.3 Related WorkOur recombination problem is a generalization of the following problem(cf. 5]).

Recombination Distance Given a= a a am; b= b b bn, and c= c c ck; nd the minimum cost recombination to produce c from a and b.1 2 1 2 1 2