Optimal recombination algorithms for generalized chains
The problem of sequence recornbination has important applications in computational molecular biology. Recently, a distance problem involving recornbination consisting of a single crossover was proposed. The problem is to generate a given set of sequences A from a given pair of sequences S in a minimum number of recombination (i.e., crossover) operations. For an arbitrary class A of sequences, the computational complexity of the problem has not yet been settled so it is interesting to find polynornially solvable cases for this kind of recornbination distance problem. In recent papers [Y. He and T. Chen, Optimatalgorithms for recombination distance problem, Optim. Methods and Soft. 18 (2003), pp. 647-655], [S. Wu and X. Gu, A greedy algorithm for optimal recombination. Proceedings of COCOON2001, Lecture Notes in Computer Science 2108, 2001, 86-90], special classes of sequences called 'tree' and 'chain' were proposed, and polynomial time algorithms were designed for optimally generating tree and chain classes, respectively. In this paper, we define a new class A of sequences, called generalized chain, which greatly extends the definition of chain class by ignoring some restrictive conditions. We distinguish a generalized chain into three cases: continuous chain, discontinuous chain and mixed chain. Then we present optimal algorithms for dealing with all cases of a generalized chain. All algorithms run in polynomial time.
generalized chain recombination distance problem optimal algorithm computational biology