A greedy algorithm for optimal recombination(4)

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

The goal is to generate a third sequence from a given pair by recombinations consisting of multiple crossovers and point mutations. In our problems, we dene a recombination consisting of a single crossover with no point mutations. We discuss a more general problem to construct the optimal recombination spanning history from one family of sequences to another one. Its general case with multiple crossovers and point mutations is NP-complete(cf. 5,6]).

2 Theorems and algorithmsIn this section, we show some theorems on optimal recombination processes and design a greedy algorithm for nding the optimal recombination process for a tree of binary sequences. We always assume S= f00 0; 11 1g: Theorem 1. Let a 2 f0; 1gn: Then n(S; fag)= l(Ia ). Proof. a is optimally generated by R(s1; s2; p; b1; c1), R(b1; c1; p+ 1; b2; c2), R(b2; c2; p+ 2; b3; c3 ),; R(bq?p?1; cq?p?1; q? 1; bq?p; cq?p ); over all positions in P (fag): Therefore, n(S; fag)= l(Ia ). The series of recombinations in the proof is called a recombination extension and denoted by ext(s1; a): Generally, if a b and a has been generated, then b can be generated by series of recombinations on the positions in P (fbg) but not P (fag); called an recombination extension from a to b and denoted by ext(a; b): Theorem 2. If A is a nest, then n(S; A)= jP (A)j. Proof. By Theorem 1 and recombination extensions. Theorem 3. Let A1; A2 f0; 1gn be independent nests, i.e., a\ b=; for any a 2 A1; b 2 A2. Then n(S; A1 A2 )= jP (A1 )j+ jP (A2)j: Proof. Apply Theorem 2 to A1 and A2; respectively. Theorem 4. Let A1; A2 f0; 1gn be independent nests and a 2 f0; 1gn. For any b1 2 A1 and b2 2 A2, (1)b1< b2 and (2)b1; b2 a: Then n(S; A1 A2 fag)= jP (fag)j+ 1: Proof. Choose a position p between A1 and A2; then Ca is partitioned into C1 and C2: Choose a1 and a2 with Ca1= C1 and Ca2= C2 . Then the theorem follows by applying Theorem 2 to both A1+ fa1 g and A2+ fa2g with one more rec

ombination R(a1; a2; p); i.e., jP (fa1g)j+ jP (fa2g)j+ 1= jP (fag)j+ 1 steps. Theorem 5. Let A be a tree. Then n(S; A)= jP (A)j+ Pa2A(jBa j? 1): Proof. By Theorem 4 and induction on jAj. Choose a root a 2 A and denote Ba= fd1< d2<< dpg. We de ne ext(d1; d2;; dp; a) as the following recombination process: (1)Choose a position pi between di and di+1 (1 i p? 1); (2)Partition Ca by all pi into Ci and choose bi with Cb= Ci(1 i p); (3)Make ext(di; bi) to get bi from di (1 i p); (4)Make the recombinations: R(b1; b2; p1; f1; g1) and R(fi?1; bi; pi; fi; gi) (2 i p? 1) with bj fi (1 j i? 1): Then fp?1= a. ext(d1; d2;; dp; a) generates a from d1; d2;; dp in optimal steps. A is then generated from branches to roots by induction.i