Fixed Topology Alignment with Recombination
1998
In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it can not be approximated within any constant ratio unless P = NP. For a more restricted version, we show that the problem is MAX-SNP-hard. This implies that there is no PTAS for this version unless P = NP. We also propose approximation algorithms for a special case, where each internal node has at most one recombination child and any two merge paths for different recombination nodes do not share any common node.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
32
References
8
Citations
NaN
KQI