A greedy algorithm for optimal recombination(5)

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

Based on Theorem 5, we now design a greedy algorithm for nding the optimal recombination spanning evolutionary history generating a tree A from S .

Greedy Algorithm Input: A (nest/tree). Output: Optimal recombination process. Step 1 Find Ba for all a 2 A and set E=;: Step 2 While A? E=; f 6 Choose a leaf (youngest branch) a 2 A? E and denote Ba= fd< d<< dp g. Generate a by ext(d; d;; dp; a). E= E+ fag. g Theorem 6. Greedy Algorithm nds the optimal recombination process for a tree A and the run time is O(jAj n). Proof. For each pair a and b of sequences, the algorithm compares n positions to determine whether a b or not. There are O(jAj ) pairs of sequences. Therefore the run time is O(jAj n).1 2 1 2 2 2 2

3 ConclusionThe greedy algorithm is designed to generate a tree from two sequences. The most interesting part of the problem is to generate an arbitrary collection of sequences from a given recombination ancestor. Our discussion may be applied to some problems in human SNP(single nucleotide polymorphism) genome project.

References1. Durbin, R., Eddy, S. R., Krogh, A. and Mitchison, G., 1998. Biological sequence analysis: Probabilistic models of proteins and nucleic acids,. Cambridge University Press. 2. Gus eld, D., 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. 3. Hein, J., 1990. Reconstruct evolution of sequences subject to recombination, Mathematical biosciences 98:185-200. 4. Hein, J., 1993. A heuristic method to reconstruct the history of sequences subject to recombination, Journal of Molecular Evolution 36: 396-450. 5. Kececioglu, J. and Gus eld, D., 1994. Reconstructing a history of recombinations from a set of sequences, 5th Annual ACM-SIAM Symposium on Discrete Algorithm Arlington, Virginia, pp.471-480. Also in Discrete Applied Mathematics 88(1998)239-260. 6. Wang,L., B. Ma and M. Li, 2000, Fixed topology alignment with recombination, Discrete Applied Mathematics 104: 281-300