A greedy algorithm for optimal recombination

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

A Greedy Algorithm for Optimal RecombinationShiquan Wu and Xun Gu?Center of Bioinformatics and Biological Statistics Iowa State University, Ames, IA 50011, USA

fsqwu,xgug@iastate.edu

Abstract. Let be an alphabet and n denote the collection of all sequences of length n over . For any s1= a1 a2 aj aj+1 an, s2= b1 b2 bj bj+1 bn 2 n; a recombination of s1 and s2 at position j is de ned as an operation that crosses s1 and s2 at position j and generates t1= a1 a2 aj bj+1 bn and t2= b1 b2 bj aj+1 an: Denote A and S two collections of sequences. In this paper, we discuss generating A from S by a series of recombinations in minimum number of steps. We present a greedy algorithm for nding the optimal recombination evolutionary history from S to any tree A of sequences when jSj= 2.

1 IntroductionVarious types of mutations on sequences play an important role in computational biology. Transformations using insertion, deletion, substitution, and reversal are widely studied by applying statistics and algorithms (cf. 1,2]). Recently, much attention has been paid to recombination of sequences. Hein developed some algorithms for recombination problems(cf. 3,4]). Kececioglu and Gus eld discussed a recombination distance problem on generating a third sequence from a given pair of sequences in optimal recombination cost (cf. 5]). Generally, an edit distance problem of genomes is widely studied and its aim is to nd the optimal evolutionary history from some ancestors to some descendents by using certain types of mutations such as insertion, deletion, substitution(point mutation),reversal, etc. Parsimony trees and phylogenetic trees are some intersting problems in the category. In 6], an alignment with recombination is discussed and it is an edit distance problem involved recombinations. In this paper, we discuss a similar distance problem involved recombinations. The purpose is to generate a collection A of sequences from another collection S of sequences by a series of recombinations in minimum number of steps.

1.1 Problem and example De nition 1. Let be an alphabet (e.g.,= fa; c; g; tg, etc) and collection of all sequences of length n over . For any s= a a aj aj1 1 2

+1

n the an,

?

Research supported in part by NIH Grant RO1 GM62118 (to X.G) and NSF of China (19771025). Wu is on leave from Math Dept,N.U.D.T.,Hunan 410073,China.