Fixed topology alignment with recombination

In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it cannot be approxima ted within any constant ratio unless P = NP. For a restricted version, we s how that the problem is MAX-SNP-hard. This implies that there is no PTAS fo r this version unless P = NP. We also propose approximation algorithms for a special case, where each internal node has at most one recombination chil d and any two merge paths for different recombination nodes do not share an y common node. (C) 2000 Elsevier Science B.V. All rights reserved.