Fixed topology alignment with recombination
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 281-300 |
| Journal / Publication | Discrete Applied Mathematics |
| Volume | 104 |
| Issue number | 1-3 |
| Online published | 3 Aug 2000 |
| Publication status | Published - 15 Aug 2000 |
Link(s)
Abstract
In this paper, we study a new version of multiple sequence alignment, fixed topology alignment with recombination. We show that it cannot be approximated within any constant ratio unless P=NP. For a 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.
Research Area(s)
- Approximation algorithm, Computational biology, Evolutionary tree, Multiple sequence alignment, Phylogeny, Recombination
Citation Format(s)
Fixed topology alignment with recombination. / Wang, Lusheng; Ma, Bin; Li, Ming.
In: Discrete Applied Mathematics, Vol. 104, No. 1-3, 15.08.2000, p. 281-300.
In: Discrete Applied Mathematics, Vol. 104, No. 1-3, 15.08.2000, p. 281-300.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
